java - 如何以最快的方式将两个排序数组相交？

Question

我有两个巨大的排序数组(每个约 10 万个项目)。我需要非常快将它们相交。现在我正在以标准方式进行操作:

• 如果 a[i] < b[j] 则 i++
• 如果 a[i] > b[j] 则 j++
• else:将a[i]添加到交集，i++，j++

但是它需要很长时间(~ 350 微秒)才能完成，这导致整体性能很差。有没有更快的方法？

P.S. 交集大小不超过 1000 个项目(平均)，我只需要其中的 25 到 100 个。

Answer 1

并行运行 2 个 100k 数组需要大约 200k 次比较。您目前正在 350 微秒 = 350k 纳秒内完成它。因此，您的每次比较时间不到 2 纳秒。如果您的 CPU 大约是 4 GHz，那么就是 8 个时钟周期。

这很好。您可以尝试变得复杂，检测运行等，但您可能会因流水线停顿而伤害自己，而不是节省工作。

只有两种方法可以加快速度。做更少的工作，或增加更多的 worker 。

您表示减少工作量是可行的，这就是 Tamas Hegedus 建议的原因。不是创建交集，而是创建一个 Iterator 来返回交集中的下一个事物。这将要求您重写使用所述迭代器的逻辑，但您将完成当前计算的 10% 以下。这将快近 10 倍。

至于添加工作线程，您需要在工作线程之间分配工作，并防止它们相互踩踏。对于 k 小(不大于您的 CPU 数量!)，在数组大小的对数工作量下，您可以快速选择以找到 k-1 将组合数组分成 k 偶数 block 的值(oops 适应 http://www.geeksforgeeks.org/median-of-two-sorted-arrays/ 而不是快速选择...)，以及每个数组中这些值的索引.这会产生 k 个偶数难度的问题，每个问题都可以指定为 4 个数字。启动 k 线程，让每个线程都得到一大块答案。这将比您当前的操作快大约 k 倍。

以很多更多的努力为代价，这些方法可以结合起来。你所做的是让迭代器创建，比如说，4 个 worker 并向每个 worker 分发 block 。当您调用 iter.next() 时，迭代器将给您一个下一个值，如果它有的话。如果没有，它将等待正在生成其下一个 block 的 worker 完成，捕获该 block ，如果准备好，则将另一个 block 交给该 worker ，然后分发该 block 中的第一个值。你可以玩 block 大小。您希望它足够大，以便 CPU 能够很好地确定它应该从 RAM 流式传输到 CPU 缓存，并且不认为线程之间存在同步争用。

考虑到大小和同步限制，我的猜测是混合方法不会比迭代器方法更胜一筹(如果有的话)。但如果你真的很绝望，你可以试试。