Python: リストと辞書にin演算子を使った時の速さ

リストにinを使った場合

ソースコード

# listin.py
n = 10**5
l = range(n)
newlist = []
for i in range(n):
    if i*2 in l:
        newlist.append(i)

実行結果

$ time python listin.py 

real    2m32.296s
user    2m31.573s
sys     0m0.132s

辞書にinを使った場合

ソースコード

# dictin.py
n = 10**5
l = dict(zip(range(n), range(n)))
newlist = []
for i in range(n):
    if i*2 in l:
        newlist.append(i)

実行結果

$ time python dictin.py 

real    0m0.122s
user    0m0.088s
sys     0m0.032s

速さが違う理由(予想)

リストにin演算子を使うと、リストがその要素を持っているかを調べる。辞書にinを使う場合は、辞書がその要素をキーに持っているかを調べることになる。
リストの要素には数値、文字列以外のオブジェクトも存在する。そのためinをつかって要素を調べるためには要素をひとつずつ順に比較する必要がある。一方、辞書にinをつかう場合は辞書の要素を調べるのではなく、辞書のキーを調べる。キーは数値と文字列以外は存在しないためハッシュを使って探索できる。このような違いによってリストにin演算子を使うと辞書にin演算子を使った場合よりも遅くなる。

リストが数値や文字列しか持たない場合にin演算子を使うときは一度辞書に変換したほうが高速。