私はpython dictに約10,000,000のアイテムを入れています。dict (またはハッシュテーブル) についての私の理解では、要素が多すぎるとサイズ変更が必要になり、操作にかなりの時間がかかります。
最初からメモリを割り当てることができるように、少なくとも n 個のアイテムを格納することを python dict に伝える方法はありますか? それとも、この最適化は私の走行速度に何の役にも立ちませんか?
（いいえ、私の小さなスクリプトの遅さがこれによるものであることを確認していません。実際にそれを行う方法はわかりません。ただし、これはJavaで行うことであり、HashSetの初期容量を正しく設定します）
最初に、初期化時に辞書のサイズを設定できるという噂を聞いたことがありますが、これがどのように行われるかを説明しているドキュメントや PEP を見たことがありません。
これを念頭に置いて、以下に説明するように、アイテムの数量を分析しました。辞書のサイズを変更するたびに時間がかかる場合がありますが、少なくともパフォーマンスをテストできるようになるまでは、気にせずに先に進むことをお勧めします。
サイズ変更を決定する際に関係する 2 つのルールは、要素の数とサイズ変更の要因です。辞書は、2/3 マークの上に配置する要素の追加で 2/3 いっぱいになると、サイズが変更されます。50,000 要素未満では 4 倍に増加し、その量を超えると 2 倍になります。10,000,000 要素 (2^23 から 2^24 の間) の見積もりを使用すると、辞書は 15 倍 (50k 未満では 7 倍、上記の8回）。別のサイズ変更は、11,100,000 を少し過ぎたところで発生します。
ハッシュテーブル内の現在の要素のサイズ変更と置換には時間がかかりますが、近くのコードで実行していることに気付くでしょうか。辞書サイズ 2^3 から 2^24 までの各境界に沿った 5 つの場所での挿入を比較するタイミング スイートをまとめました。「境界」の追加は、「非境界」の追加より平均 0.4 ナノ秒長くなります。これは 0.17% 長いです...おそらく許容範囲です。すべての操作の最小値は 0.2085 マイクロ秒で、最大値は 0.2412 マイクロ秒でした。
これが洞察に満ちていることを願っています。コードのパフォーマンスを確認する場合は、編集してフォローアップしてください! ディクショナリの内部に関する私の主なリソースは、PyCon 2010 での Brandon Rhodes による素晴らしい講演でした: The Mighty Dictionary
はい、できます。これは、あなたの質問にも関連する別の人の質問で見つけた解決策です。
d = {}
for i in xrange(4000000):
d[i] = None
# 722ms
d = dict(itertools.izip(xrange(4000000), itertools.repeat(None)))
# 634ms
dict.fromkeys(xrange(4000000))
# 558ms
s = set(xrange(4000000))
dict.fromkeys(s)
# Not including set construction 353ms
これらは、特定のサイズで辞書を初期化するさまざまな方法です。