我有两个巨大的排序数组(每个~100K项).我需要非常快地交叉它们.现在我以标准的方式做到这一点：
>如果a [i]< b [j]然后我
>如果a [i]> b [j]然后j
>否则：将一个[i]添加到交集,i,j
但是完成时间太长(~350微秒),导致整体性能相当差.有没有办法更快地做到这一点？
附：交叉口大小不大于1000件(平均而言),我只需要25到100件.
非常好.你可以尝试复杂,检测跑步等等,但是你可能会因为管道失速而伤害自己,而不是节省工作.
你已经表明减少工作是可行的,这就是为什么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缓存,并且不认为线程之间存在同步争用.
