java – 如何以最快的方式交叉两个排序的数组？
|
我有两个巨大的排序数组(每个~100K项).我需要非常快地交叉它们.现在我以标准的方式做到这一点： >如果a [i]< b [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缓存,并且不认为线程之间存在同步争用. 考虑到大小和同步约束,我认为混合方法对于迭代器方法来说并不是一个胜利,如果有的话.但如果你真的很绝望,你可以尝试一下. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |