コードが遅いのを解決！Pythonで学ぶパフォーマンスチューニング術の基本。

実際のプログラムでよく見かけるO(n2)の例として、2重のループを用いて、2つのリスト間で共通の要素を探すものがあります。これを高速化する一つの方法は、ハッシュセットを使用して探索時間をO(1)に減少させることです。この変更によって、全体の時間複雑度はO(n)になります。

1. 2重ループを使用した例 O(n2)

import time
import numpy as np

# 2重ループを使用した関数の定義
def find_common_elements_list(list1, list2):
    common_elements = []
    for element1 in list1:
        for element2 in list2:
            if element1 == element2:
                common_elements.append(element1)
    return common_elements

# サンプルデータ（1000件）
sample_list1 = np.random.randint(0, 10000, 1000).tolist()  # ランダムな整数のリストを生成
sample_list2 = np.random.randint(0, 10000, 1000).tolist()  # ランダムな整数のリストを生成


# 2重ループを使用した関数の実行と実行時間の計測
start_time_double_loop = time.time()
common_elements_list = find_common_elements_list(sample_list1, sample_list2)
end_time_double_loop = time.time()

# 結果の出力
print(f"Common elements (Double Loop): {common_elements_list}")
print(f"Execution Time (Double Loop): {end_time_double_loop - start_time_double_loop} seconds")

2. ハッシュセットを使用した例 O(n)

import time
import numpy as np

# ハッシュセットを使用した関数の定義
def find_common_elements_set(list1, list2):
    set1 = set(list1)
    set2 = set(list2)
    return list(set1.intersection(set2))

# サンプルデータ（1000件）
sample_list1 = np.random.randint(0, 10000, 1000).tolist()  # ランダムな整数のリストを生成
sample_list2 = np.random.randint(0, 10000, 1000).tolist()  # ランダムな整数のリストを生成

# ハッシュセットを使用した関数の実行と実行時間の計測
start_time_hash_set = time.time()
common_elements_set = find_common_elements_set(sample_list1, sample_list2)
end_time_hash_set = time.time()

print(f"Common elements (Hash Set): {common_elements_set}")
print(f"Execution Time (Hash Set): {end_time_hash_set - start_time_hash_set} seconds")

100件ぐらいのデータだとたいして変わりませんが、1000件ぐらいから一桁ぐらいの明らかな差が出てきます。10000万件だと体感が劇的に違います。

上記のグラフは、2重ループを使用したアプローチとハッシュセットを使用したアプローチの実行時間の比較を示しています。このグラフから、ハッシュセットを使用したアプローチの方が、2重ループを使用したアプローチよりも、大きく効率的であることが確認できます。

もう基本です。

プログラマの数学 第2版

以下は思わず「頭いい！」と思った大好きな本です。ぜひ読んでみてください。

珠玉のプログラミング 本質を見抜いたアルゴリズムとデータ構造

合わせてどうぞ！