algorithm - 如何从文件中删除重复项？

Question

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

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

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

有没有道理。还有其他选择吗？

Answer 1

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

查找多路合并(例如 here)和外部排序。