algorithm - 如果数组大小大于可用内存，则查找两个数组的公共(public)元素

Question

有几种方法可以解决此问题，使用排序 O(mlog(n)) 或使用额外空间 O(m) 或 O(n) 的哈希 O(m+n) 或 O(m+n) 中的索引增量方法).

但如果内存有限并且我的数组大小在数百万范围内，我会更感兴趣。

我们可以将数组 A 或 B 分成段并加载到内存中，但我想知道是否有更好的方法。

Answer 1

element distinctness问题(至少和你的问题一样难)是 O(nlogn) 而不使用任何额外的空间。

但是，使用哈希解决方案实际上可以在平均情况下得到改进。

您建议的方法实际上是实现 intersection 的方法之一在数据库系统中:

创建 k 个桶(在磁盘上)，并遍历列表，并将每个元素 e 添加到 bucket[hash(e)]。
一旦你完成了，假设有足够的空间，所以每个桶足够小，可以加载到内存¹，你只需要加载bucket[i]对于每个列表 - 并为每个桶做内存交集(基于排序和迭代)。
结果将为您提供交集的答案 - 这是公共(public)元素。

---

另一种在数据库系统中完成(交集)的方法是使用 external sort (通常是合并排序的一种变体)并迭代或创建针对磁盘优化的索引(例如 B+ trees )。

---

(1) 通常是这种情况，如果不是 - 对每个桶重复该过程(使用不同的哈希函数)，直到您有足够小的桶。