更高效的HashMap（Dictionary）for Python在大數據中使用

我正在創建一個程序，用於統計大文件中字符串的出現次數。爲此，我使用了字符串作爲鍵和計數作爲值的Python字典。更高效的HashMap（Dictionary）for Python在大數據中使用

該程序適用於最多10000個字符串的較小文件。但是當我在我的實際文件〜2-3 mil字符串上進行測試時，我的程序在達到其原始速度的50％至約50％時開始減速。

我懷疑這是因爲內置的字典並不是要處理如此大量的數據，並且會發生更多的衝突。我想知道是否有任何有效的方法來解決這個問題。我正在尋找替代hashmap實現，甚至製作hashmaps列表（它進一步減慢了它）。

詳情：

字符串不事先知道的。
字符串的長度範圍是約10 - 200
有跡象表明，只出現一次（和將在年底被丟棄）許多字符串
我已經執行併發加快它。
大約需要1小時完成一個文件
- 我做的其他計算過，而這需要時間，它不小的filesizes放緩。所以我懷疑這是一個hashmap或內存問題。
我有足夠的內存，運行時只佔用8GB的32GB。

來源

2017-08-11 CJX3711

正如你注意到沒有，做一個更復雜的數據結構並不會讓情況變得更快。 Python的字典經過精心設計和調整，在大多數情況下，你會很難做得更好。 – dimo414

我懷疑這是因爲內置的字典是不是意味着要處理如此大量的數據，並得到了很多更多的碰撞。

高碰撞率不是可能的原因。 Python字典隨着它們的增長而調整大小，所以它們不會超過三分之二。無論大小如何，這都可以保持合理的速度。

可能的原因是數據增長量大於L3緩存（通常約6Mb）。除此之外，常規的DRAM訪問速度將會降低一倍左右（請參閱下面的ExtremeTech的內存延遲圖）。

鑑於這是一個硬件問題，替代字典實現將不會幫助。

來源

2017-08-11 04:43:28

在這種情況下，有什麼我可以做的，而不是購買具有更多緩存的新CPU？我正在考慮將文件分割成更小的文件，然後分別處理它們。最終有一個最終傳球合併所有哈希。 – CJX3711

@ CJX3711一個極端的措施是編輯CPython的字典對象，以假定散列匹配意味着相等。這將節省昂貴的重複字符串比較。編輯在Objects/dictobject.c lookdict（）和它的親屬中，如'if（ep-> me_hash == hash）{return ix; }''。這並不完美，但是誤報的可能性是1比2 ** 64。 –

如何通過相關條件來分割文件，如字符串長度或字符串的第一個字符？選擇「正確」的標準（我不能在沒有看到數據分佈的情況下猜測），結果塊將小得多，並且來自不同塊的字符串不可能相等。 –

更高效的HashMap（Dictionary）for Python在大數據中使用

回答

相關問題