2

所以我们有大约 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 百万 * 5 百万 / 2 次迭代。即使我们将所有内容都放在 RAM 中，这也太多了。

不过有一个窍门。我们真的不需要知道所有的交叉口，我们只需要大约 20,000 个最大的交叉口。所以，我们可以省略那些只包含几个交集的数组（我们也可以称它们为“共享元素”）：

1st array intersection with Nth, Mth, Kth... (20,000 of the largest intersections).

大约有 1000 万个可能的元素，因此数组的每个元素都在 [1;1000 万] 范围内。

我们必须存储字符串和整数。但是是的，我们可以只使用索引作为整数，稍后再进行替换。1000 万个字符串并不算多，这就是我在示例中使用整数而不是字符串的原因。但实际的原始数据是字符串： ['abcdef', 'abc', 'def', 'fghf'...] （正如我所写的，有 1000 万个唯一字符串）。

有什么方法可以更快地做到这一点？特别是如果数据无法放入内存（我们可以将字符串存储为元素，而不仅仅是整数）？也许是一些棘手的 map\reduce 东西......甚至是 GPU 计算。欢迎任何解决方案 - 想法、算法、链接、代码片段。谢谢你们！

更新。我发现有趣的帖子可能会有所帮助：

4

2 回答 2

1

更好地了解数据的性质，然后尝试查看是否可以使用 map reduce 方法。原因如下：

我在想你应该从所有数组中所有元素的计数排序 O(n) 开始。这样你就可以找到高频的值。

我的理论是，您的长交叉点将有一些常见的元素出现在许多数组中，而其他一些元素则较少出现。

计数排序时，您将存储元素 X 出现的每个数组的地址。

下一步将从出现最多的元素开始，并尝试找出包含该元素的数组的交集。我不是在谈论仅查看共享最高元素的数组的交集，我只是在将 O(NxN) 过程减少到合理的 N 值而不是数百万。

这就是为什么我认为了解一些字符串元素的性质可能会有所帮助。例如，如果这些数组包含：City、Street、Race、Income 等，您可以在遍历经常显示的值时大量使用该信息。

另外，如果您确实有城市、街道、收入等类别，我认为您可以利用标准的 Mapr-Reduce 方法，将元组作为 Reducer 的键。

于 2013-09-07T17:12:30.000 回答
0

如果我们改变问题而不是交集，并说出每个字符串中有多少在其他字符串中，Aho-Corasick 算法可能会派上用场。它是内存密集型的。它的预处理时间为 O(n)。它的运行时间为 O(m)（m 是模式长度）。如果匹配太多，则性能会降低。由于您需要找到每个字符串与每个字符串的匹配，因此复杂性将是二次的。

于 2013-09-06T16:26:37.740 回答