在一個大文件中最省時的搜索 - Python

我在大文本文件中搜索匹配，但是我覺得它太慢了。這是文件的結構：在一個大文件中最省時的搜索 - Python

word1 5752 
word2 96332 
word3 137

我試圖匹配第一列文字，我想提取在第二列中的值。這些列由\ t分隔，並且有大約1000萬行。該文件用不同的詞搜索多次。什麼樣的搜索方法具有最佳的時間效率？

編輯：該文件是129 Mb，至少將搜索數千次。 EDIT2：文件按字母順序排序，只有當它們有不同的大寫字母時，纔會出現多次字，例如：Word WORD word WOrd將全部是不同的條目。

來源

2017-02-17 mandatory

如何，您在搜索，以及如何你加載數據？例如，如果您將整個文件加載到內存中，那麼這可能是性能不佳的原因。或者，你可能會更好地使用不同的算法，你可以在再次閱讀之前搜索每行上的不同單詞嗎？ – cdarke

根據您搜索數據的次數，您可以將整個文件加載到內存中並將其轉換爲字典。雖然這可能會消耗一些內存。 – voidpointercast

「什麼方法的搜索有最好的時間效率？」 - 「這取決於」 - 這取決於你的機器有多少內存，單詞的長度，如果'word1'在文件中有多個實例，我忘了提及的其他內容。總而言之，我會與[voidpointercast]（http://stackoverflow.com/users/2242806/voidpointercast）建議（現在已被提升爲[答案]（http://stackoverflow.com/a/42301043/2749397）），一切都在字典和測試.. – gboffi

with open('myfile.dat','r') as src: 
    mapping = dict((line.strip().split('\t') for line in src if line))

根據文件和內存的大小，這可能是一個解決方案。如果您在程序運行期間必須多次執行此類搜索算法。

來源

2017-02-17 15:00:44 voidpointercast

該文件是129 Mb，將被搜索數千 - 數萬次。所以我想內存要求並不高，我對時間效率更感興趣。 – mandatory

從字典鍵獲取值應該非常有效。我想他們是用二叉樹實現的，但我不知道。 – voidpointercast

我會先按字母順序對文件進行排序，然後執行對數搜索（https://en.wikipedia.org/wiki/Binary_search_algorithm）。您有關於如何使用Python在這裏做一個很好的例子： http://programarcadegames.com/index.php?chapter=searching&lang=en#section_16.5

來源

2017-02-17 14:50:52 Numlet

如果文件被程序的幾次運行「感動」，這是一種很好的方法。 – voidpointercast

這是用於作業還是工作/項目？我不知道人們對重新實現核心算法的感覺如何，但是你的文本文件有多大？

使用熊貓的易用性和底層優化的另一種方法：

In [61]: df = pd.read_csv(r'C:\temp\data.txt', header=None, sep=' ') 

In [62]: df 
Out[62]: 
     0  1 
0 word1 5752 
1 word2 96332 
2 word3 137 

In [63]: df[df[0] == 'word2'] 
Out[63]: 
     0  1 
1 word2 96332 

In [64]: df[df[0] == 'word2'][1] 
Out[64]: 
1 96332 
Name: 1, dtype: int64

2個問題爲您提供：

1）可以這樣在內存中，而不是重新加載每次舉行？（可能是一個小時的TTL？）

2）您的文件是否已排序？我相信二進制搜索需要先排序數據。每次讀取數據時，對性能的影響是什麼？

來源

2017-02-17 15:04:44 Kelvin

1.它可以在內存中保存，當然 2.它是排序 – mandatory

如果你可以保存在內存中，你如何閱讀它變得不那麼重要。我認爲你的最佳表現將來自於將其留在數據框中並且只是查詢它。 – Kelvin

如果您將數據存儲在散列表（一種Python字典結構）中，那麼執行此操作將非常快速。你的'鑰匙'是名字，每個鑰匙都有一個'數值'，這個數字。如下圖所示這個代碼利用哈希以獲得更快的數據檢索：

yourDict = {'name0':number0,'name1':number1,...,'nameN':numberN} 
if 'checkName' in yourDict: 
    #It exists! 
    theNumber = yourDict['checkName'] 
else: 
    #It doesn't exist :/

*注：如果你使用：

if 'checkName' in yourDict.keys():

，你實際上是在創建關鍵字的列表，然後通過他們尋找。該操作不使用哈希表（非常慢）。

這是HandTable數據結構是如何工作的一個位： https://www.youtube.com/watch?v=MfhjkfocRR0

這是表示將蟒蛇的行爲像一個哈希表的字典答案： Is a Python dictionary an example of a hash table?

來源

2017-02-17 15:23:30

如何：theNumber = yourDict.get（'checkName'）？如果值不存在，則Number將爲None。任何有關性能的見解？ – voidpointercast

我只是看着它，它看起來你是對的！這對我來說似乎有點不直觀，但是這個人在非常大的文件上測試了它，並得到了顯着的改進。所以代碼應該是：yourDict.get（'checkName'） https://partofthething.com/thoughts/?p=513 –

在一個大文件中最省時的搜索 - Python

回答

相關問題