java – 如何以最快的方式交叉两个排序的数组?

前端之家收集整理的这篇文章主要介绍了java – 如何以最快的方式交叉两个排序的数组?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

我有两个巨大的排序数组(每个~100K项).我需要非常快地交叉它们.现在我以标准的方式做到这一点:

>如果a [i]< b [j]然后我
>如果a [i]> b [j]然后j
>否则:将一个[i]添加到交集,i,j

但是完成时间太长(~350微秒),导致整体性能相当差.有没有办法更快地做到这一点?

附:交叉口大小不大于1000件(平均而言),我只需要25到100件.

最佳答案
并行运行2个100k阵列需要大约200k比较.您目前正在以350微秒= 350k纳秒的速度完成它.所以你的每个比较时间不到2纳秒.如果你的cpu大约是4 GHz,那么这是8个时钟周期.

非常好.你可以尝试复杂,检测跑步等等,但是你可能会因为管道失速而伤害自己,而不是节省工作.

只有两种方法可以加快速度.减少工作量,或增加更多工人.

你已经表明减少工作是可行的,这就是为什么Tamas Hegedus建议的.而不是创建交集,创建一个迭代器,它将返回交集中的下一个东西.这将要求您重写使用所述迭代器的逻辑,但是您将在当前计算的10%以下进行.这将快接近10倍.

至于添加工作者,你需要在工作线程之间划分工作并防止它们彼此踩踏.对于小k(不大于你的cpu数量!),在数组大小的对数工作量,你可以快速选择找到k-1值,将组合数组分成k个偶数块(oops Adapt) http://www.geeksforgeeks.org/median-of-two-sorted-arrays/而不是做一个quickselect …),以及每个数组中这些值的索引.这会产生甚至困难的k个问题,每个问题都可以指定为4个数字.旋转k个线程,让每个线程获得答案的一部分.这将比您目前所做的快约k倍.

以更多的努力为代价,这些方法可以结合起来.你做的是让迭代器创建4个工人,然后分配给每个工人.当你调用iter.next()时,迭代器会给你一个下一个值,如果它有一个值.如果它没有,它将等待正在生成其下一个块的worker完成,抓取该块,如果一个就准备好,将该另一个块交给该worker,然后分发该块中的第一个值.您可以使用块大小.您希望它足够大以至于cpu可以很好地确定它应该从RAM流式传输到cpu缓存,并且不认为线程之间存在同步争用.

考虑到大小和同步约束,我认为混合方法对于迭代器方法来说并不是一个胜利,如果有的话.但如果你真的很绝望,你可以尝试一下.

原文链接:https://www.f2er.com/java/437381.html

猜你在找的Java相关文章