使并行排序算法比朴素优化的快速排序算法更快？

Question

正如标题所暗示的，我需要一个比快速排序更快的算法。所讨论的快速排序是经过优化的，并在一个简单的并行系统中使用，因此单个线程完全执行每个快速排序，但多个线程同时执行快速排序。我需要做一个比这个过程更快的算法。通过让额外的线程执行透视图的每一条边的排序来并行每个快速排序会不会更快，或者这个过程会不会有太多的开销并最终导致速度变慢？对算法有什么建议吗？

Answer 1

如果我理解正确的话，您目前有一个由N个线程执行N个排序的系统。每个单独的排序由单个线程完成，但可以同时运行多个排序。您可能会问，如果编写一个并行排序算法，使每个排序由多个线程执行，是否会更快。

假设你有四个处理器，你必须做10个排序。假设每个排序花费相同的时间(不切实际，但对讨论很有用)，那么如果每个排序都在单个线程中运行，那么您可以同时运行四个排序。调用一个时间周期执行单线程排序的时间。

因此，执行所有排序的时间将是三个时间段。在两个周期中，您有四个排序并发运行，在一个周期中，您有两个并发排序。在最后一段时间内，您有过剩的容量(两个空闲的处理器)。

如果您有一个使用四个线程的并行排序算法，那么最好的情况是每次排序所需的时间是单线程排序的四分之一。所以从理论上讲，你可以在10/4个时间段内执行10个排序，这意味着只需要2.5个时间段。

因此，从理论上讲，通过使用并行排序算法，可以节省一半的时间。但是您不会意识到这样的性能提升，因为快速排序不是100%可并行化的；有时只涉及少于四个线程。在每次排序过程中，您都会在随机的时间拥有空闲的处理器。使用并行版本很有可能会整体上变慢，因为这些小的空闲时间加起来。

这样想:你有四个人，他们需要做10项工作。他们可以通过各自拿一个单独完成这10个工作，或者通过合作，使四个人中的每个人都完成每个工作的四分之一的工作。完成的工作量没有区别。在第一种情况下，您有两个空闲的工作人员，而最后两个工作正在完成。在第二种情况下，您在完成最后一个作业时有一些空闲时间；worker 1空闲了该时间段的3/4，worker 2空闲了该时间段的1/2，worker 3空闲了该时间段的1/4。所以从理论上讲，你的员工总空闲时间是6/4，或者说1.5个时间段。

但是，在将作业从worker 1移动到worker 2等过程中也会有空闲时间。这种转换时间会使两个worker都短暂空闲。这些很小的时间(每个作业3次转换，加上worker 1获得下一个作业并开始的时间，worker 4交付成品的时间)加在一起，很可能会超过表面上节省的.5时间段。

不过你可以试一试。快速排序的并行化非常容易。例如，请参见http://reedcopsey.com/2010/02/26/parallelism-in-net-part-11-divide-and-conquer-via-parallel-invoke/。

Answer 2

这取决于数据的大小和性质。QS在排序数据上的性能最差(如果内存服务的话)。正如您所建议的，您可以为pivot的每一侧提供一个线程，但您可能希望限制分区不会变得太小。请跟进并让我们知道它的进展，我有兴趣知道，我相信其他人也会知道。