timeitモジュールを使って経過時間を計測します.
研究室の後輩がlistからsetにしたら速くなった!と喜んでいたのでどれぐらい早くなるか検証.
参考
詳細
listとsetからin演算子を用いて要素の有無を調べる平均時間の比較.
listはおそらく線形探索なのでO(n),よってO(1)のsetの探索よりもかなり遅いはず.
結果
結果は以下のようになっています.
縦軸がsetの処理時間に対するlistの処理時間の比になっています.
100個のデータを持つデータ構造からinで探索する場合,listの方がsetよりも13,4倍遅いということがわかります
コード
import timeit import numpy as np import matplotlib.pyplot as plt MAX = 100000 l = range(MAX) s = set(l) def test_list(n): for i in xrange(n): i in l def test_set(n): for i in xrange(n): i in s def test(N, I = 1000000): assert N <= MAX t1 = timeit.Timer("test_list({0})".format(N), "from {0} import test_list".format(__name__)).timeit(I) t2 = timeit.Timer("test_set({0})".format(N), "from {0} import test_set".format(__name__)).timeit(I) return t1 / t2 if __name__ == '__main__': N = 100 t = np.empty(N) for i in xrange(N): t[i] = test(i, 10000) plt.plot(t) plt.show() plt.close()