在两个集合中查找重复项的有效方法是什么？

Question

我设置了A和B

集合A有1亿个数字(每个数字为64位)

集合B有1亿个数字(每个数字为64位)

两组大小相同。

数据都是随机的，没有排序。

你会推荐什么算法来寻找两个集合之间的重复数字？

(我可以利用大约4G内存和100~200 Gb的磁盘空间)

提前谢谢你。

Answer 1

假设第一个arr是arr1，第二个是arr2；

sort arr1//max O(n*log_n)
for(int i = 0; i < arr2.length; i++){ //n
    binarySearch(arr1, arr2[i]) //log_n
}

总计O(n logn)

Answer 2

64位=8字节。2*8*100,000,000字节=1.6 as =>你可以将你的数字保存在内存中(你可能需要两倍于节点结构的内存...)。我会选择平衡二叉树(只需在维基上搜索AVL，AB...树)。只需将一个集合中的数字添加到一棵树中，将另一个集合中的数字添加到另一棵树中，然后进行交集。

您可能只需要对两个数组进行排序并使它们相交。这应该是最简单的解决方案。

如果您无法处理内存中的所有数字，请使用数据库(MySQL，PostgreSQL...)。两个排序表和交集。它应该是相当快的，最重要的是易于实现。

Answer 3

由于整个数据集可以(轻松地)放入RAM中，因此不需要对其进行任何巧妙的排序，也不需要使用磁盘空间(除了首先加载数据之外)。

我假设每个元素在每个列表中最多只能存在一次。

哑巴(蛮力)方法，O(n^2)：

foreach a in A (this could be as you read it from disk)
    foreach b in B
        if a is b
            increase count
            break out of inner loop

预排序方法：(2*n*log(n)+n)，so O(n*log(n))

sort A
sort B
B_ind = 0
foreach a in A
    foreach b in B from B_ind
        if a is b
            increase count
            B_ind = current b index + 1
            break out of inner loop
        else if b > a
            B_ind = current b index
            break out of inner loop

我推荐使用前者，但使用并行处理。很容易将外部循环拆分成块，以便在处理器/工作站之间拆分。后者也可以在一定程度上并行化(同时执行两种排序)，但远远不能并行化。

同样在前者的情况下，您可以通过将b循环拆分成缓存大小的块来获得一些性能提升。例如，检查A与B0...1023，然后检查A1，...最终，然后对照B1024...2047检查A，等等。