从两个非常大的数组中查找公共元素

Question

有两个整数数组,每个都在非常大的文件中(每个文件的大小都大于RAM).如何在线性时间内找到数组中的公共元素.

我找不到解决这个问题的合适方案.有任何想法吗？

Answer 1

对一个文件进行一次传递构建一个位图(如果整数范围对于内存中的位图来说太大,则为Bloom过滤器).

另一个文件中的一个传递找到重复项(或者如果使用Bloom过滤器则为候选项).

如果使用Bloom过滤器,则结果是概率性的.新的通行证可以减少误报(布隆过滤器没有假阴性).

Answer 2

假设整数大小为4个字节.现在我们可以有最多2 ^ 32个整数,即我可以有一个2 ^ 32位(512 MB)的位向量来表示每个位重复1个整数的所有整数.1.使用全零初始化此向量2.现在浏览一个文件,如果找到整数,则将此向量中的位设置为1.3.现在浏览其他文件并查找位Vector中的任何设置位.

时间复杂度O(n + m)空间复杂度512 MB