Mic*_*ael 3 language-agnostic sorting algorithm parallel-processing
双方merge sort并quick sort可以并行工作.每次我们在两个子问题中分解问题时,我们可以并行运行这些子问题.然而,它看起来不是最佳的.
假设我们有4个CPU.在第一次迭代中,我们仅在2个子问题中拆分问题,并且两个CPU处于空闲状态.在第二次迭代中,所有CPU都很忙,但在3d迭代中我们没有足够的CPU.因此,我们应该针对具体情况调整算法CPUs << log(N).
是否有意义？您如何使排序算法适应这些情况？
首先,最佳的并行实现将在很大程度上取决于环境.需要考虑的一些因素:
等等
现在回到理论上:
假设我有1024张卡,还有7个人帮我排序.
我迅速将堆栈分成8个大小相等的部分.因为我要快速行动,所以不会完全平等.实际上,因为我的朋友可以在他们获得他们的部分后立即开始整理他们的部分,我应该给我的第一个朋友比其他朋友更大的堆栈并且在结束时变小.
每个人按顺序排序他们的部分.(基数排序,快速排序,合并排序等)
现在是困难的部分...... 合并.
在现实生活中,我可能会有前两个人准备成对并开始合并他们的套牌.也许他们可以一起工作,一个人从前面合并,另一个从后面合并.也许他们可以同时从前面开始工作,同时调出他们的数字.
很快其他人将完成他们的个人排序,并可以开始合并.我会让他们成对,因为他们觉得方便,并继续前进,直到所有卡合并.
这里真正的技巧是尝试并行化分区,因为其余的很容易.
我将首先将堆栈分成8个部分,然后将一部分分配给每个朋友.在这样做时,我会选择其中一张看起来可能最终朝向排序甲板中间的卡片.我打电话给那个号码.
我的每个朋友都会将他们较小的堆栈分成三堆,小于被叫号码,等于被叫号码,并且大于被叫号码.如果一个朋友比其他朋友快,他/她可以偷走邻居朋友的一些卡片.
当他们完成了这一点后,我将所有较少的东西收集到一堆并将其交给0到3的朋友,我将等于的东西放在一边,然后将更多的东西交给朋友4到7.
朋友0到3,将他们的筹码分成四个相等的部分,将选择一张牌来分区,并在他们之间重复这个过程.
重复这一过程,直到每个朋友都有自己的堆栈.
(请注意,如果没有很好地选择分区卡,而不是将工作分成50-50,也许我只会分配2个朋友来处理较少的工作,并让其他6个工作在更大的工作上.)
最后,我只是以正确的顺序收集所有堆栈以及分区卡.
虽然有些方法在计算机上比在现实生活中更快,但我认为前面是一个好的开始.除非您在硬件中实现排序,否则不同的计算机或核心或线程将以不同的速度执行其工作.(如果您愿意,您可能需要查看"排序网络"和"最佳排序网络").
如果要对数字进行排序,则需要通过对其进行并行化来帮助处理大型数据集.
但是,如果您通过比较相应像素红绿蓝值之间的曼哈顿总和距离来排序图像.你会发现用k cpu来加速不到k次就不那么困难了.
最后,您需要对顺序版本进行计时,并在进行比较时进行比较,因为缓存效果,内存使用情况,网络成本等可能会产生影响.