我想实现一个快速的算法来完成作业，但是希望使用并行处理来完成这个任务。我听说并行版本的快速排序是最好的选择，但我不确定...也许堆排序是一个不错的选择。您认为哪种算法是最适合并行化环境的，为什么？
7个回答
6
快速排序可以将未排序的列表分成两半，但不幸的是，这两半不能保证非常均匀。因此，一台机器（或一半集群中的机器）可能得到20个条目，而另一半可能得到200亿个。
我想不出一个好方法使堆排序并行工作。虽然它是可以做到的，但感觉真的很反直觉。
归并排序是我认为你需要的。
每个拆分恰好是列表的50％，因此在处理器之间拆分很容易。
您可以在两组磁带驱动器上实现归并排序，这意味着它不需要整个列表同时存在于内存中。对于大型列表，特别是比您可用内存更大的列表，这是必须的。
如果有必要，归并排序在并行实现中也是稳定的。
我想不出一个好方法使堆排序并行工作。虽然它是可以做到的，但感觉真的很反直觉。
归并排序是我认为你需要的。
每个拆分恰好是列表的50％，因此在处理器之间拆分很容易。
您可以在两组磁带驱动器上实现归并排序，这意味着它不需要整个列表同时存在于内存中。对于大型列表，特别是比您可用内存更大的列表，这是必须的。
如果有必要，归并排序在并行实现中也是稳定的。
- Dean J
3
归并排序是一种很好的第一种并行排序技术。最佳排序方法始终取决于机器，通常涉及不同大小输入的排序技术的组合。
- Nick Larsen
2
正如Dean J所提到的，归并排序是一个很好的选择。但它有一个缺点，就是需要在两个线程都完成后进行同步（合并过程）。
虽然快速排序在分区时不可预测，但可以做的是有意识地使第一个分区（决定处理器负载）更或多或少地均匀分配负载，然后让算法自行处理。
优点是，在处理器完成工作后，您无需进行任何类型的同步。完成后，您已经准备好了排序数组，无需额外的合并步骤，这可能会很昂贵。
- Lazer
1
您应该考虑使用比特位排序(Bitonic Sort)算法：
该算法与归并排序有些相似，但有一个有趣的变化：不是将数组的两半从低到高排序，然后合并，而是将数组的一半按相反的方向排序，以获得一个比特位(bitonic)数组：由两个单调部分组成，方向相反。
比特位数组可以以非常好的并行方式合并为排序后的数组：虽然其总时间复杂度为O(n log(n))，但所有的比较和交换都是独立的，即选择要比较的元素不依赖于先前的比较结果，不像通常的合并。因此，它允许完全并行化。
这个Youtube视频演示了比特位排序。
PS-我猜测提问者的作业已经过期了...三年前。
该算法与归并排序有些相似，但有一个有趣的变化：不是将数组的两半从低到高排序，然后合并，而是将数组的一半按相反的方向排序，以获得一个比特位(bitonic)数组：由两个单调部分组成，方向相反。
比特位数组可以以非常好的并行方式合并为排序后的数组：虽然其总时间复杂度为O(n log(n))，但所有的比较和交换都是独立的，即选择要比较的元素不依赖于先前的比较结果，不像通常的合并。因此，它允许完全并行化。
这个Youtube视频演示了比特位排序。
PS-我猜测提问者的作业已经过期了...三年前。
- einpoklum
2
如果这能让你感觉更好，你的回答让我重新审视了我两年前写的一些WebGL应用程序。 - Jefferey Cave
@JeffereyCave：如果你给我点赞，那么我会感觉更好 :-P - einpoklum
1
怎么样考虑分成两步呢。
第一步。将我的数据分成N个块，其中N是我的处理器/节点/核心数。对每个块进行排序。
第二步。将我的N个块组合在一起。
对于排序N个块，您可以根据您的数据使用任何您想要的方法。快速排序、堆排序，我不在乎。对于第二步，归并排序很好地处理了两个已排序列表的组合，所以这可能是您最好的选择。
- Peter Recore
0
快速排序是递归的，使任何递归算法并行化的简单方法（仅当它涉及两个或更多递归调用时，如快速排序所做的那样）是为递归调用生成两个新线程，并等待它们完成，然后完成您的函数。这绝不是最优的方法，但这是一种相当快速和简单的递归调用并行化的方法。
- aepurniet
0
我曾经为一个并行化库工作过，开发了一个并行排序算法，但最终得出结论：这样做不值得。对于小数据集，即使只有几个同步原语的成本也会使并行排序比常规排序更慢。对于大数据集，你主要受到共享内存带宽的限制，获得的速度提升很小。在排序大量（我记得是1000万）整数的情况下，我只能在双核处理器上使用并行快速排序获得不到1.5倍的加速。
编辑：
我所做的大部分编程都是数字计算，因此我倾向于按照简单基元进行排序。我仍然认为对于这些情况，使用并行排序是一个坏主意。但如果你正在排序昂贵的比较对象，则此答案不适用。
- dsimcha
8
3你的问题在于你试图对已经很快的东西进行并行化。对整数进行排序是微不足道的，因为比较操作会被掩盖。试着对包含50,000个项目，每次比较需要1毫秒的数据进行排序并行化，然后告诉我这样做不值得。 - Gabe
@Gabe：你的观点很有意思。我想不出我曾经使用过的任何对象，比较都需要那么长时间，但如果比较确实需要这么长时间，并且不受内存带宽限制，那么你是对的，并行排序可能会非常有效。 - dsimcha
对于给定处理器而言，比较任何非原子操作的排序方式可以在并行处理大数据集时获得显著的加速效果。即使是一个128位的小值也是如此。 - Nick Larsen
@dsimcha：我理解这一点，这也是我今天早些时候回答的原因，我指出排序算法优化通常是基于机器的。我只是在扩展Gabe的评论。 - Nick Larsen
直觉上，你是正确的。但令我惊讶的是，最新的Matlab具有用于共享内存的并行排序功能，并且对于排序双精度或整数数组非常有效。我与glibc qsort进行了一些比较，Matlab在两个核心上的表现几乎要好两倍。我知道这不是很公平的比较，可能是因为qsort速度较慢。但这真的很令人惊讶。 - angainor
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接