用于检测数据集中的重复项的算法,该数据集太大而不能完全加载到存储器中

Question

这个问题有最佳解决方案吗？

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

我的'天真'解决方案是一个O(n ^ 2)解决方案,它迭代值并只是一次性加载文件而不是全部.

对于i = 0到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个块,每个块都足够大,可以在内存中进行排序.在内存中排序它们.

对于每组两个块,我们将在两个块上执行mergesort的最后一步,以生成一个更大的块(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提到的一个快速而肮脏的解决方案是制作一个尽可能大的内存过滤器.然后,您可以列出未通过布隆过滤器的每个元素的索引,并第二次循环遍历该文件,以便测试这些成员是否有重复.

Answer 2

如果可以存储临时文件，则可以分块加载文件，对每个块进行排序，将其写入文件，然后迭代这些块并查找重复项。通过将某个数字与文件中的下一个数字以及每个块中的下一个数字进行比较，您可以轻松判断该数字是否重复。然后移动到所有块的下一个最小编号并重复，直到用完编号。

由于排序，你的运行时间是 O(n log n)。