PythonのListとDictionaryの検索機能の速さ

"in"を使って要素の有無を判定する時、ListとDictionaryで速いのはどちらなのだろうと疑問に思ったので調べた。

with Python 2.7.11

l = [1,2,3,4,5]
for i in range(10000000):
        if 1 in l:
                pass

real 0m1.017s
user 0m0.853s
sys 0m0.141s
 

d = {1:"", 2:"", 3:"", 4:"", 5:""}
for i in range(10000000):
        if 1 in d:
                pass

real 0m1.053s
user 0m0.888s
sys 0m0.143s
 

単純に検索するだけならList型のほうが速い。(何に使うかは知らない)

ただ、普通は検索したあとそのindexに対してカウントしたり何かしらアクションを加えるので、結局Dictionaryの方が速い。

l = [1,2,3,4,5]
for i in range(10000000):
        if 1 in l:
                index = l.index(1)
                l[index] = l[index]

real 0m4.239s
user 0m4.074s
sys 0m0.139s
 

d = {1:"", 2:"", 3:"", 4:"", 5:""}
for i in range(10000000):
        if 1 in d:
                d[1] = d[1]

real 0m2.105s
user 0m1.938s
sys 0m0.144s

追記
要素の数が大きくなったときはDictionaryの方が早いようだった。

#d = {i:True for i in range(10000000)}
d = range(10000000)
for i in range(100000000):
  1 in d

real 0m15.324s
user 0m13.374s
sys 0m1.961s

d = {i:True for i in range(10000000)}
#d = range(10000000)
for i in range(100000000):
  1 in d

real 0m14.133s
user 0m11.922s
sys 0m2.220s

Dictionary objectはListに比べて作るのに時間がかかるため、本来ならforの回数を変化させて線形近似しなければいけないが、速さがDictionary＞Listの例が取れたのでそこは割愛した。
ちなみにDictionaryに於いて"d[1]"と"i in d"の検索速度に差はないようである。