1

如何从大数字的大文件中删除重复项？这是一个关于算法和数据结构的面试问题，而不是sort -u诸如此类的问题。

我假设该文件不适合内存并且数字范围足够大，因此我不能使用内存计数/桶排序。

唯一的选择是对文件进行排序（例如merge sort）并再次传递排序后的文件以过滤掉重复项。

是否有意义。还有其他选择吗？

4

3 回答 3

3

如果您在合并排序中使用“合并”（又名“联合”）的重复删除变体，您甚至不需要单独传递已排序的数据。哈希表应该是空的以表现良好，即比文件本身还要大 - 我们被告知文件本身很大。

查找多路合并（例如此处）和外部排序。

于 2012-07-20T16:16:11.583 回答
2

是的，解决方案是有道理的。

另一种方法是构建基于文件系统的哈希表，并将其作为一个集合进行维护。首先迭代所有元素并将它们插入到您的集合中，然后 - 在第二次迭代中，打印集合中的所有元素。

就大 O 复杂性而言，执行和数据相关的性能更好，哈希提供O(n)时间平均情况和O(n^2)最坏情况，而合并排序选项提供更稳定的O(nlogn)解决方案。

于 2012-07-20T14:05:37.697 回答
1

Mergesort 或 Timsort（这是一种改进的合并排序）是一个好主意。例如：http : //stromberg.dnsalias.org/~strombrg/sort-comparison/

您可能还可以从布隆过滤器中获得一些里程。它是一种概率数据结构，对内存的要求很低。您可以使用布隆过滤器调整错误概率。EG：http ://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/ 您可以使用一个来丢弃绝对唯一的值，然后通过其他方法更仔细地检查可能不是唯一的值. 如果您的输入数据集有很多重复项，这将特别有价值。它不需要直接比较元素，它只是使用可能大量的散列函数对元素进行散列。

您还可以使用磁盘 BTree 或 2-3 树或类似的。这些通常存储在磁盘上，并按键顺序保持键/值对。

于 2012-07-20T21:20:57.437 回答