Pythonのさまざまなデータ構造における 'in'演算の効率

Question

Pythonを使用していたときに、 'in'演算のパフォーマンスが異なることがわかりました。たとえば、次のように

a=list_a######list_a and list_b both are lists,data scale:300,000 
b=set(list_b) 
t1=time() 
s=0 
for entry in a: 
    if entry in b: 
     s+=1 
t2=time() 
print t2-t1 

と私が設定したデータ構造に

a=list_a 
b=list_b 
t1=time() 
s=0 
for entry in a: 
    if entry in b: 
     s+=1 
t2=time() 
print t2-t1 

、これを変更することなく、list_b検索するとき、私は、しかし

0.0699999332428 

非常にeffiecientである、このような結果で終わりました結果は約10分かかった。

539.641000032 

私はインターネットを検索しましたが、これは何とかハッシュマップに関連していますが、まだ混乱しています。誰もこれを詳細に説明してもらえますか？これに類似したPythonの他のデータ構造がありますか？

ありがとうございます。

Answer 1

リストにはリニアタイムルックアップがあります。これは、アイテムがリストにあるかどうかを調べるために、Pythonは一致するものが見つかるまで各アイテムをスキャンする必要があるからです。その時間はリストの長さに比例します。リストが長ければ長いほど、それは長くかかります。コンピュータ科学の用語では、これはO(n)時間の複雑さと呼ばれます。

セットとディクショナリには一定の時間検索があります。位置だけで索引付けされた一連の要素を格納する代わりに、値のハッシュを格納します。一致する項目があるかどうかを調べるために、Pythonは値をハッシュして一致するインデックスに移動します。どんなに大きなセットであっても、常に同じ時間量がかかるでしょう - これは複雑さO(1)として知られています。