在一个大文件中最省时的搜索 - 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

回答

相关问题