4

现在，现代机器都是多核的，并且我们在带有 SSE 指令的 Windows 和 Linux 机器上支持 SIMD 指令，例如，我是否应该在我的 C/C++ 代码中切换到合并排序而忘记快速排序？从理论上讲，这样做的原因是合并排序会更好地并行化并更节省地使用内存/磁盘，因此比 QuickSort 的内存密集型操作更快，但我不知道。实践经验说明了什么？

我不想在每次排序时都进行分析和测试。我想使用一种标准方法。目前这种方法是快速排序，因为这是默认的库排序例程。我想知道是否还有其他人已经切换到 MergeSort 并通过切换获得了更好的结果。

更新 - - - - - -

Graham.Reeds 回答std::sort 和 std::stable_sort 在实践中的性能差距有多大？表明我上面的猜测是正确的，切换到 MergeSort/stablesort 可能是正确的。

4

5 回答 5

2

在得到很多非答案后，我花了几个小时自己研究。这样做的结果是，是的，合并排序（和其他相关排序）由于内存使用较少以及更好的并行化/多核利用而将显着加快。此外，英特尔有一个标准的高性能库，称为 IPP，它为 x86 机器实现合并类型的排序。通过切换到这个库，对于我所做的编程类型，我似乎可以大大提高排序性能（和其他向量类型操作）。

于 2012-12-14T00:01:01.997 回答
1

我不认为有一个确定的答案。在某些情况下，可并行化的蛮力排序可能会更快。分析您的特定情况总是很重要的。还要考虑双调排序，例如，如果您有多个内核和 SIMD。

于 2012-12-12T15:57:26.470 回答
1

我应该在我的 C/C++ 代码中切换到合并排序并忘记快速排序吗？

很抱歉这么说，但这个问题听起来像是过早优化的尝试。

从理论上讲，这样做的原因是合并排序会更好地并行化并更节省地使用内存/磁盘，因此比 QuickSort 的内存密集型操作更快，但我不知道。实践经验说明了什么？

实际上，您应该始终先进行分析，然后根据结果决定优化领域。

很可能您甚至不必更改您使用的排序算法，除非您在足够大的数据集上执行此操作以使结果很重要（或者在您的处理流程中足够关键的区域中）。

我通常使用 std::sort，如果这还不够（这还没有发生std::sort），我会优化我的应用程序流程和算法。

于 2012-12-12T16:13:43.323 回答
0

事实是您必须自己对其进行分析，并查看它对您的应用程序、数据、环境等的行为方式。本质上，这是对 SO 上 99% 的所有分析/性能/优化问题的答案。

于 2012-12-12T15:56:13.063 回答
0

有一些并行排序包可以根据处理器中的内核数量进行扩展，旨在利用/优化每个处理器上的处理。我知道 TBB（线程构建块）有一个 parallel_sort 函数，它是一个平均时间复杂度为 0(n log n) 的比较排序。

您还可以在快速排序中实现一些线程。在 TBB 中使用 parallel_for 可以轻松地将递归函数转换为并行性，或者您可以查看 Cilk Plus，网上有很多线程示例。

于 2012-12-12T17:34:53.060 回答