使用字符串鍵整數鍵字典訪問速度比較

我有一個很大的字典，我必須從中查找很多次的值。我的鍵是整數，但代表標籤，因此不需要添加，減少等等。我最終試圖評估字符串鍵和整數鍵字典之間的訪問時間，這是結果。使用字符串鍵整數鍵字典訪問速度比較

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

是否證明使用詞典與字符串作爲鍵是更快地訪問比用整數作爲鍵？

來源

2011-12-06 fallino

如果您使用多個鍵，它會更好。 – Marcin

CPython的dict實現實際上針對字符串鍵查找進行了優化。有兩個不同的函數，lookdict和lookdict_string（Python 3中的lookdict_unicode），可用於執行查找。 Python將使用字符串優化版本，直到搜索非字符串數據，之後使用更通用的函數。您可以通過下載CPython的源代碼並通過dictobject.c來閱讀實際實現。

作爲此優化的結果，當dict具有所有字符串鍵時，查找速度更快。

來源

2011-12-06 17:00:52 zeekay

恐怕你的時代並不真正證明很多。

你在Dint中的字符串測試是最快的：一般來說，對於不在字典中的任何東西的測試很可能是快速的，但那只是因爲你很幸運，並且第一次打到空單元格以便查找可能終止。如果你不走運並選擇了一個或多個完整單元格的值，那麼它最終可能比實際找到的東西慢。

測試字典中的任意字符串必須計算字符串的哈希碼。這需要與字符串長度成正比的時間，但Python有一個巧妙的技巧，並且只爲每個字符串計算一次。由於您在計時測試中反覆使用相同的字符串，所以計算散列所用的時間會丟失，因爲它只發生在第一次，而不是其他99999999次。如果每次使用不同的字符串，都會得到非常不同的結果。

Python已經優化了密鑰爲字符串的字典的代碼。總的來說，你會發現使用多次使用相同鍵的字符串鍵會稍微快一點，但如果在查找之前必須不斷將整數轉換爲字符串，那麼將失去這種優勢。

來源

2011-12-06 17:05:09 Duncan

使用字符串鍵整數鍵字典訪問速度比較

回答

相關問題