2 つの変数で構成されるキーを使用して辞書を何度も呼び出すスクリプトがあります。私のプログラムは逆の順序で 2 つの変数に再び遭遇することを知っています。これにより、キーをタプルとして格納することが可能になります。(行と列に同じラベルを付けたマトリックスの作成)
したがって、辞書のキーにfrozensetよりもタプルを使用することでパフォーマンスの違いがあるかどうか疑問に思っていました.
2 つの変数で構成されるキーを使用して辞書を何度も呼び出すスクリプトがあります。私のプログラムは逆の順序で 2 つの変数に再び遭遇することを知っています。これにより、キーをタプルとして格納することが可能になります。(行と列に同じラベルを付けたマトリックスの作成)
したがって、辞書のキーにfrozensetよりもタプルを使用することでパフォーマンスの違いがあるかどうか疑問に思っていました.
簡単なテストでは、明らかに無視できるほどの違いがあります。
python -m timeit -s "keys = list(zip(range(10000), range(10, 10000)))" -s "values = range(10000)" -s "a=dict(zip(keys, values))" "for i in keys:" " _ = a[i]"
1000 loops, best of 3: 855 usec per loop
python -m timeit -s "keys = [frozenset(i) for i in zip(range(10000), range(10, 10000))]" -s "values = range(10000)" -s "a=dict(zip(keys, values))" "for i in keys:" " _ = a[i]"
1000 loops, best of 3: 848 usec per loop
私は本当にあなたのコードの他の場所で最高のものを使いたいと思います.
テストを行っていないので、いくつかの推測があります。s の場合frozenset
、cpythonは計算後にハッシュを格納します。さらに、データがまばらに格納されるため、あらゆる種類のセットを反復処理すると、余分なオーバーヘッドが発生します。2 項目セットでは、最初のハッシュのパフォーマンスが大幅に低下しますが、おそらく 2 番目のハッシュは非常に高速になります (少なくともオブジェクト自体が同じ場合)。(つまり、新しいものではありませんが、同等のフリーズセットです。)
s の場合tuple
、cpython はハッシュを保存するのではなく、毎回計算します。したがって、frozenset を使用すると、ハッシュを繰り返す方がわずかに安くなる可能性があります。しかし、そのような短いタプルの場合、おそらくほとんど違いはありません。非常に短いタプルの方が高速になる可能性さえあります。
Lattywareの現在のタイミングは、ここでの私の推論とほぼ一致しています。下記参照。
新しい凍結セットと古い凍結セットのハッシュの非対称性に関する私の直感をテストするために、次のことを行いました。タイミングの違いは、もっぱら余分なハッシュ時間によるものだと思います。ちなみに、これはかなり重要ではありません。
>>> fs = frozenset((1, 2))
>>> old_fs = lambda: [frozenset((1, 2)), fs][1]
>>> new_fs = lambda: [frozenset((1, 2)), fs][0]
>>> id(fs) == id(old_fs())
True
>>> id(fs) == id(new_fs())
False
>>> %timeit hash(old_fs())
1000000 loops, best of 3: 642 ns per loop
>>> %timeit hash(new_fs())
1000000 loops, best of 3: 660 ns per loop
以前のタイミングが間違っていたことに注意してください。を使用and
すると、上記の方法で回避されるタイミングの非対称性が作成されます。この新しいメソッドは、タプルに対して期待される結果を生成します -- ごくわずかなタイミングの違い:
>>> tp = (1, 2)
>>> old_tp = lambda: [tuple((1, 2)), tp][1]
>>> new_tp = lambda: [tuple((1, 2)), tp][0]
>>> id(tp) == id(old_tp())
True
>>> id(tp) == id(new_tp())
False
>>> %timeit hash(old_tp())
1000000 loops, best of 3: 533 ns per loop
>>> %timeit hash(new_tp())
1000000 loops, best of 3: 532 ns per loop
そして、事前構築済みのfrozensetのハッシュ時間を、事前構築済みのタプルのハッシュ時間と比較する、とどめの一撃です。
>>> %timeit hash(fs)
10000000 loops, best of 3: 82.2 ns per loop
>>> %timeit hash(tp)
10000000 loops, best of 3: 93.6 ns per loop
Lattyware の結果は、新旧のフリーズ セットの結果の平均であるため、このように見えます。(各タプルまたはフリーズセットを、辞書の作成時に 1 回、辞書にアクセスするときに 1 回、2 回ハッシュします。)
これらすべての結果として、Python の内部構造を掘り下げてテストすることを楽しんでいる私たち以外は、おそらく問題にはならないでしょう。
を使用timeit
して調べることはできますが (それがどのように機能するかを学ぶ以外の理由がない場合は、そうすることをお勧めします)、最終的にはほとんど問題になりません。
frozenset
はハッシュ可能になるように特別に設計されているため、ハッシュ方法が線形時間である場合はショックを受けます。この種のマイクロ最適化は、リアルタイム アプリケーションで一定の (多数の) ルックアップを非常に短い時間で処理する必要がある場合にのみ問題になります。
更新: Lattywareの回答に対するさまざまな更新とコメントを見てください.交絡因子を取り除き、2つのアプローチのパフォーマンスがほぼ同じであることを示すには、(まあ、比較的)多くの集合的な努力が必要でした. パフォーマンス ヒットは、想定されていた場所ではなく、独自のコードでも同じです。
機能するコードを記述し、プロファイリングしてホットスポットを見つけ、アルゴリズムの最適化を適用してから、マイクロ最適化を適用します。