假设我们有一个字符串列表，但是我们无法将整个列表加载到内存中，而我们可以从文件中加载列表的部分。那么解决这个问题的最佳方法是什么？
2个回答
11
一种方法是使用外部排序对文件进行排序，然后在排序后的列表上进行单次迭代来删除重复项。这种方法需要很少的额外空间和对磁盘的O(nlogn)访问。
另一种方法基于哈希：使用字符串的哈希码，加载包含所有哈希码在特定范围内的字符串的子列表。如果已加载x并且它有一个重复项，则重复项也会加载到相同的桶中。
这需要对磁盘的O(n*#buckets)访问，但可能需要更多的内存。如有需要，可以递归调用该过程（使用不同的哈希函数）。
- amit
2
1在外部排序中，您可以在算法的第二个（即合并）传递期间删除重复项。 - Jim Mischel
@JimMischel：在第一遍中删除可以在批处理中找到的重复项，可以让您制作更少的批次，节省合并工作。您还可以通过在读取输入时构建Trie或甚至DAWG来对更大的pass1批次进行排序，以紧凑地表示到目前为止已经看到的字符串集（在此过程中查找重复项）。请参见我在https://dev59.com/gY_ea4cB1Zd3GeqPIwnA#32537772上的答案。 - Peter Cordes
0
我的解决方案是使用归并排序，这允许使用外部内存。排序后，查找重复项就像只比较两个元素一样容易。
例如：
0：猫 1：狗 2：鸟 3：猫 4：大象 5：猫
归并排序
0：鸟 1：猫 2：猫 3：猫 4：狗 5：大象
然后简单地比较0和1->没有重复项，所以继续向前。 1和2->重复，删除1（这可以简单地用空字符串填充来跳过稍后的步骤） 比较2和3->删除2 等等。
之所以删除1和2而不是2和3，是因为它允许更有效的比较--您不必担心跳过已删除的索引。
- deckeresq
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
sort程序可以对大于内存的文件进行排序并删除重复项。如果文件已经排序，请参阅uniq程序。 - Jim Mischel