用于检测数据集中重复项的算法，该数据集太大而无法完全加载到内存中

Question

这个问题有最优解吗？

描述一种在包含一百万个电话号码的文件中查找重复项的算法。该算法在运行时只有 2 兆字节的可用内存，这意味着您无法一次将所有电话号码加载到内存中。

我的“天真”解决方案是 O(n^2) 解决方案，它遍历值并只加载文件 block 而不是一次加载所有文件。

For i = 0 to 999,999

string currentVal = get the item at index i

for j = i+1 to 999,999
  if (j - i mod fileChunkSize == 0)
    load file chunk into array
  if data[j] == currentVal
    add currentVal to duplicateList and exit for

肯定还有另一种情况，您可以以真正独特的方式加载整个数据集并验证数字是否重复。有人有吗？

Answer 1

将文件分成M个 block ，每个 block 都足够大，可以在内存中排序。在内存中对它们进行排序。

对于每组两个 block ，我们将对两个 block 执行合并排序的最后一步，以生成一个更大的 block (c_1 + c_2) (c_3 + c_4) .. (c_m-1 + c_m)

指向磁盘上 c_1 和 c_2 的第一个元素，并创建一个新文件(我们称之为 c_1+2)。

如果c_1指向的元素比c_2指向的元素小，则复制到c_1+2并指向c_1的下一个元素。
否则，将c_2的指向元素复制到并指向c_2的下一个元素。

重复上一步，直到两个数组都为空。您只需要使用存储两个指向的数字所需的内存空间。在此过程中，如果您遇到 c_1 和 c_2 指向的元素相等，则您发现了重复项 - 您可以将其复制两次并递增两个指针。

生成的 m/2 数组可以以相同的方式递归合并——这些合并步骤需要 log(m) 次才能生成正确的数组。每个数字将以找到重复项的方式与其他数字进行比较。

或者，@Evgeny Kluev 提到的一个快速而肮脏的解决方案是制作一个尽可能大的布隆过滤器，它可以合理地容纳在内存中。然后，您可以列出每个未能通过布隆过滤器的元素的索引，并再次循环文件以测试这些成员是否重复。