所以我们有大约 500 万个数组：
1) [1, 2, 3, 4, 5, 6]
2) [1, 4, 5]
3) [1, 4, 6, 9, 10]
4) ...
几乎。我们需要找到每个数组之间的交集：
1st array intersection with 2nd: [1, 4, 5]; with 3rd: [1, 4, 6]...
2nd array intersection with 1st: [1, 4, 5]; with 3rd: [1, 4]...
3rd array intersection with 1st: [1, 4, 6]; with 2nd: [1, 4]...
所以看起来显而易见的算法是 2 个嵌套循环，它给出了复杂性 O（n*n） 或围绕它的东西。即使我们存储已经计算好的交集（由于内存限制，这可能是不可能的），它也会给我们类似 ~O（n*n/2） 的东西。这是一个非常粗略的复杂度计算，但无论如何它需要 5 mlns * 5 mlns/2 次迭代。即使我们将所有内容都放在RAM中，这也太多了。
然而，有一个技巧。我们真的不需要知道所有的十字路口，我们只需要大约20，000个最大的十字路口。因此，我们可以省略那些只包含几个交集的数组（我们也可以称它们为"共享元素"）：
1st array intersection with Nth, Mth, Kth... (20,000 of the largest intersections).
大约有 1000 万个可能的元素，因此数组的每个元素都将在 [1;10 mln] 范围内。
我们必须存储字符串和整数。但是，是的，我们可以只使用索引作为整数，稍后执行替换。10 数百万个字符串并不算太多，这就是为什么我在示例中使用整数而不是字符串。但实际的原始数据是字符串：['abcdef'， 'abc'， 'def'， 'fghf'...]（正如我所写的，有 1000 万个唯一的字符串）。
有没有办法做得更快？特别是如果数据无法放入内存（我们可以将字符串存储为元素，而不仅仅是整数）？也许一些棘手的地图\减少的东西...甚至是 GPU 计算。欢迎任何解决方案 - 想法、算法、链接、代码片段。谢谢你们！
更新。我发现了有趣的帖子，可能会有所帮助：
- http://www.dr-josiah.com/2012/03/why-我们-没有使用-bloom-filter.html
- http://www.dr-josiah.com/2011/09/improving-performance-by-1000x.html
更多地了解数据的性质，然后尝试查看是否可以使用mapreduce方法。原因如下：
我认为您应该从所有数组中所有元素的计数排序 O（n） 开始。这样，您就可以以高频率找到值。
我的理论是，你的长交集将有一些常见元素出现在许多数组中，而其他一些元素则显示较少。
在计数排序时，您将存储元素 X 显示的每个数组的地址。
下一步是从显示最多的元素开始，并尝试找出包含该元素的数组的交集。我不是在谈论只查看共享最高元素的数组的交集，我只是在考虑将 O（NxN） 过程减少到合理的 N 值而不是数百万。
这就是为什么我认为了解一些字符串元素的性质可能会有所帮助。例如，如果这些数组包含：城市、街道、种族、收入等，则在浏览显示大量的值时，您可以大量使用该信息。
另外，如果您确实有城市，街道，收入等类别，我认为您可以利用标准的Mapr-Reduce方法，使该元组成为化简器的键。
而不是交集，如果我们改变问题并说出这些字符串中的每一个有多少个在其他字符串中，Aho-Corasick 算法可能会派上用场。它是内存密集型的。它的预处理时间为 O（n）。它的运行时间为O（m）（m是图案长度）。如果匹配过多，则性能会降低。由于您需要找到每个字符串与每个字符串的匹配项，因此复杂性将是二次的。