非常に大規模な辞書のパフォーマンスをPythonで改善する

Question

空の辞書を最初に初期化し、forループの要素を辞書に追加すると（約110,000個のキー、各キーの値もリストになりますループ内で増加する）、ループが進むにつれて速度が低下する。

辞書には初期化時のキーの数がわからず、非常にスマートなことがないので、おそらくストレージの衝突が頻繁になり、速度が遅くなる可能性があります。

私がキーの数と正確にそれらのキーを知っているなら、dict（またはハッシュテーブル）をより効率的に動作させる方法はありますか？あなたが鍵を知っていれば、ハッシュ関数をスマートに（完全なハッシュ？）設計し、あらかじめ空間を割り当てることができることをぼんやりと覚えています。

Answer 1

私はキーの数を知っていて、これらのキーは、正確に何している場合は、辞書（またはハッシュテーブル）を作るためにPythonでどのような方法があり され、効率的に より多くの仕事？あなたが鍵を知っているならば、 はスマートに（完全なハッシュ？）ハッシュ関数を設計し、事前に の領域を割り当てることができることをぼんやりと覚えています。

Pythonは、辞書の「成長段階」をスピードアップするためのサイズ変更オプションを公開しておらず、辞書内の「配置」に対する直接のコントロールも提供していません。

つまり、キーは常に事前にわかっている場合は、setに保存し、dict.fromkeys()を使用して辞書から辞書を作成できます。 ）（__つまりクラスメソッドはoptimized to pre-size the dictionary based on the set sizeあり、それは__hashする任意の新しいコールせずに辞書を移入することができます

>>> keys = {'red', 'green', 'blue', 'yellow', 'orange', 'pink', 'black'} 
>>> d = dict.fromkeys(keys) # dict is pre-sized to 32 empty slots 

衝突を低減することがあなたの目標であるならば、あなたはパイルアップを最小限に抑えるために、辞書に挿入順序で実験を実行することができます。 （KnuthのTAOCPでBrent's variation on Algorithm Dを見て、これがどのように行われているかを知る）。

辞書用の純粋なPythonモデル（this oneなど）を装備することで、代替の挿入注文のプローブの加重平均数を数えることができます。たとえば、dict.fromkeys([11100, 22200, 44400, 33300])を挿入すると、ルックアップごとに平均1.75のプローブが得られます。これは、dict.fromkeys([33300, 22200, 11100, 44400])のルックアップごとに2.25平均プローブを上回ります。

もう一つの「トリック」はincreasing its size without adding new keyの中にそれをだますことにより、完全装備の辞書にsparenessを高めることである。

d = dict.fromkeys(['red', 'green', 'blue', 'yellow', 'orange']) 
d.update(dict(d))  # This makes room for additional keys 
         # and makes the set collision-free. 

最後に、独自のカスタム__hashの__を導入することができます（）なくすことを目標に、あなたの鍵のためにすべての衝突（おそらくgperfなどの完全なハッシュジェネレータを使用して）。