文字列キーに対する整数キーとの辞書のアクセス速度の比較

Question

私は大量の辞書を取得しており、そこから多くの値を検索する必要があります。私のキーは整数ですが、ラベルを表すので、追加、減算などは必要ありません。文字列キーと整数キー辞書の間のアクセス時間を評価しようとしましたが、結果はここにあります。実行間のわずかな変化を生じ

from timeit import Timer 

Dint = dict() 
Dstr = dict() 

for i in range(10000): 
    Dint[i] = i 
    Dstr[str(i)] = i 


print 'string key in Dint', 
print(Timer("'7498' in Dint", "from __main__ import Dint").timeit(100000000)) 
print 'int key in Dint', 
print(Timer("7498 in Dint", "from __main__ import Dint").timeit(100000000)) 
print 'string key in Dstr', 
print(Timer("'7498' in Dstr", "from __main__ import Dstr").timeit(100000000)) 
print 'int key in Dstr', 
print(Timer("7498 in Dstr", "from __main__ import Dstr").timeit(100000000)) 

は毎回再現：

string key in Dint 4.5552944017 
int key in Dint 7.14334390267 
string key in Dstr 6.69923791116 
int key in Dstr 5.03503126455 

それがキーとして文字列と辞書を使用すると、キーとして整数よりもアクセスが高速であることを証明していますか？

Answer 1

CPythonのdictの実装は、実際には文字列キールックアップに最適化されています。 2つの異なる関数、lookdictとlookdict_string（Python 3ではlookdict_unicode）があり、ルックアップの実行に使用できます。 Pythonは文字列に最適化されたバージョンを非文字列データの検索まで使用します。その後、より一般的な関数が使用されます。実際の実装を見るには、CPythonのソースをダウンロードし、dictobject.cから読んでください。

dictにすべての文字列キーがある場合、この最適化の結果、検索が高速になります。

Answer 2

あなたの時間は本当に大したことを証明していないことは恐れています。

Dintの文字列のテストは最も速いです：一般に、辞書にないもののテストは非常に高速ですが、それはあなたが幸運で最初に空のセルにヒットしたためです終了する。あなたが不運で、1つ以上の完全なセルに当たる値を選択した場合、実際に何かを見つける場合よりも遅くなる可能性があります。

辞書内の任意の文字列をテストするには、文字列のハッシュコードを計算する必要があります。それは文字列の長さに比例した時間がかかりますが、Pythonはきちんとしたトリックを持ち、各文字列に対して一度だけ計算します。あなたのタイミングテストで同じ文字列を繰り返し使用するので、ハッシュを計算するのにかかる時間は、それが最初にしか起こらず、他の99999999回ではなく失われます。毎回異なる文字列を使用していた場合、非常に異なる結果が得られます。

Pythonはキーが文字列である辞書用のコードを最適化しています。全体的に見ると、同じキーを複数回使用する場合は文字列キーを使用するほうがやや高速ですが、ルックアップ前に整数を文字列に変換する必要がある場合は、その利点を失います。