两者merge sort和quick sort可以并行工作。每次我们将一个问题拆分为两个子问题时，我们都可以并行运行这些子问题。但是它看起来不是最理想的。
假设我们有 4 个 CPU。在第 1 次迭代中，我们仅将问题拆分为 2 个子问题，并且两个 CPU 处于空闲状态。在第 2 次迭代中，所有 CPU 都很忙，但在第 3d 次迭代中，我们没有足够的 CPU。因此，我们应该针对 时的情况调整算法CPUs << log(N)。
是否有意义？您将如何使排序算法适应这些情况？
问问题
2215 次
1 回答
6
首先，最好的并行实现很大程度上取决于环境。需要考虑的一些因素：
- 共享内存（一台 4 核计算机）与非共享内存（4 台单核计算机）
- 要排序的数据大小
- 比较两个元素的速度
- 交换/移动两个元素的速度
- 可用内存
- 每台计算机/核心是否相同，或者在速度、部件之间通信的网络延迟、缓存效果等方面是否存在差异？
- 容错：如果一台计算机/核心在操作过程中发生故障怎么办。
等等
现在回到理论：
假设我有 1024 张卡片，还有 7 个人帮我整理它们。
合并排序
我很快将堆栈分成大小相等的 8 个部分。它不会完全相等，因为我走得很快。实际上，因为我的朋友们一拿到他们的部分就可以开始整理他们的部分，我应该给我的第一个朋友一个比其他朋友大的堆栈，并在最后变得更小。
每个人按照他们喜欢的顺序对他们的部分进行排序。（基数排序、快速排序、归并排序等）
现在是困难的部分......合并。
在现实生活中，我可能会让前两个准备好形成一对并开始将他们的套牌合并在一起的人。也许他们可以一起工作，一个人从前面合并，另一个人从后面合并。也许他们都可以在前线工作，同时喊出他们的号码。
很快其他人将完成各自的排序，并可以开始合并。我会让他们成对，因为他们觉得方便，然后继续前进，直到所有卡片都合并为止。
快速排序
这里真正的技巧是尝试并行化分区，因为其余的很容易做到。
我将首先将堆栈分成 8 个部分，然后将一个部分分发给每个朋友。在执行此操作时，我将选择一张看起来可能最终会出现在已排序套牌中间的牌。我拨出那个号码。
我的每个朋友都会将他们的小筹码分成三堆，小于被叫数，等于被叫数，大于被叫数。如果一个朋友比其他朋友快，他/她可以从邻居朋友那里偷一些卡。
当他们完成后，我将所有小于号收集到一堆并将其交给朋友 0 到 3，我将等号放在一边，并将较大的给朋友 4 到 7。
朋友 0 到 3，将他们的堆栈分成四个大致相等的部分，将选择一张卡片进行分区，并在他们之间重复这个过程。
如此重复，直到每个朋友都有自己的堆栈。
（注意如果分区卡选得不好，与其按50-50分工，不如只分配2个朋友做小于号，让其他6个做大于号。）
最后，我只是按照正确的顺序收集所有的堆栈以及分区卡。
结论
虽然确实有些方法在计算机上比在现实生活中更快，但我认为前面是一个好的开始。不同的计算机或内核或线程将以不同的速度执行它们的工作，除非您在硬件中实现排序。（如果你是，你可能想看看“排序网络”和/或“最优排序网络”）。
如果要对数字进行排序，则需要通过并行化来帮助大型数据集。
但是，如果您通过比较相应像素红绿蓝值之间的总曼哈顿距离来对图像进行排序。您会发现使用 k 个 cpu 获得不到 k 倍的加速并不困难。
最后，您需要对顺序版本进行计时，并在进行过程中进行比较，因为缓存效果、内存使用、网络成本等可能会有所不同。
于 2013-08-01T09:21:30.487 回答