唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

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

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

詳細

listとsetからin演算子を用いて要素の有無を調べる平均時間の比較.
listはおそらく線形探索なのでO(n),よってO(1)のsetの探索よりもかなり遅いはず.

結果

結果は以下のようになっています.
縦軸がsetの処理時間に対するlistの処理時間の比になっています.
100個のデータを持つデータ構造からinで探索する場合,listの方がsetよりも13,4倍遅いということがわかります
f:id:sucrose:20111124225710p:image

コード

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