在大型数据集中搜索
我想知道怎么在一个大约有500万个128位（或者256位，具体看你怎么理解）字符串的列表中快速查找重复的字符串（用Python）。我可以把这些字符串转换成数字，但我觉得这没什么帮助。因为我对信息理论了解不多，不知道这方面有没有相关的内容？
而且这些字符串已经是哈希值了，所以再哈希一次也没什么意义。
5 个回答
2
把这些数据加载到内存中（5百万条，每条64字节，总共320MB），然后对它们进行排序，再逐个检查，找出重复的部分。
4
如果数据量不大，能放进内存里，就用set()。我觉得这样会比排序快。对于500万条数据，O(n log n)的排序开销可不小。
如果数据量太大，超过500万条，建议用“分而治之”的方法。可以把数据在中间分开，比如1和2的127次方。然后用上面提到的方法处理。根据信息理论，一个好的哈希函数能把数据均匀分布，所以用中间分割的方法应该效果不错。
即使数据量能放进内存里，也可以用“分而治之”的方法。排序250万条记录比排序500万条记录要快。
1
这个数组是排好序的吗？
我觉得最快的解决办法可以用堆排序或者快速排序，先把数组整理好，然后再找出重复的元素。