Pythonでlistとsetを探索するときの速度比較

timeitモジュールを使って経過時間を計測します．
研究室の後輩がlistからsetにしたら速くなった！と喜んでいたのでどれぐらい早くなるか検証．

参考

• http://www.python.jp/doc/release/library/timeit.html
• http://morchin.sakura.ne.jp/effective_python/timeit.html

詳細

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()