python - Pythonでキーとしてタプルを使用した「in」演算子が遅いのはなぜですか?

Question

次のような辞書があります。

d=dict()
d[('1','2')] = 'value'

次に、キーをクエリします。

if (k1,k2) in d.keys():

100万レコードだと速度が落ちますが、in演算子に問題はありますか？

シーケンシャルサーチですか？

この問題を回避するには、str をキーとして連結する必要があります。

Answer 1

使用する必要があります

(k1,k2) in d

を呼び出す代わりにd.keys()。

自分のやり方で行うと、Python 2 では線形検索になり、むしろdict. Python 3 では、コードは効率的ですが (以下のコメントを参照)、私のバージョンはより明確です。

Answer 2

Nolen Royal の追加を考慮して、実際にはtimeitもう少し良い方法でテストを実行できることに注意してください。dictの構成をセットアップ関数に移動することで、 の操作のみの時間dictを計ることができ、簡単に比較できる結果が得られます。

3.2 では:

python -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d.keys()' '_ = (1, 2) in d.keys()'
1000000 loops, best of 3: 0.404 usec per loop

python -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d' '_ = (1, 2) in d'
1000000 loops, best of 3: 0.247 usec per loop

違いがわかります。3.x では、直接作業することでdict速度がほぼ 2 倍になりましたが、これは悪くありません。

2.7.3:

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d.keys(); _ = (1, 2) in d.keys()'
10 loops, best of 3: 36.3 msec per loop

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d' '_ = (1, 2) in d'
10000000 loops, best of 3: 0.197 usec per loop

2.x では、その違いは本当に驚異的です。の使用dict.keys()には 36,300 マイクロ秒かかりますが、 の使用にはdict0.2 マイクロ秒未満かかります。それは20 万倍近く高速です。

それは注目に値すると思っただけです。

編集：

Tim が興味深いコメントをしたので、葯のテストを行うことにしました。リストを作成してから、ハッシュルックアップを実行すると、次のようになります。

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' 'd.keys()' 'd.keys()'
100 loops, best of 3: 5.84 msec per loop

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' -s 'l=d.keys()' '_ = ("1", "2") in l' '_ = ("1", "2") in l'
10 loops, best of 3: 25.3 msec per loop

このような大きな dict では、リストの作成に約 1/6 の時間がかかり、リストの検索に 5/6 の時間がかかることがわかります。