为什么 std::sort() 比 std::make_heap() 更快?

Question

我拥有一个std::vector<Sequence>中的13721057个元素。我需要对这个向量进行排序并获取前25个元素。我认为，由于可以在O(N)中构建堆，因此弹出25个元素（每个元素都是O(logN)）一定比在O(NlogN)中对整个向量进行排序更快。

但是，当我计时代码时：

clock_t tStart = clock();
sort(mostFrequent.begin(), mostFrequent.end(), greater<Sequence>());
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

与

clock_t tStart = clock();
make_heap(mostFrequent.begin(), mostFrequent.end());
printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);

整个向量排序似乎更快。为什么呢？

- Murat Ayan

---

可能是隐藏的常量。同时尝试测试std::nth_element()函数。 - SashaMN

你有多次运行这个程序吗？你改变了哪一个先被调用了吗？你打开了优化编译吗？ - NathanOliver

大O符号表示忽略所有常数...例如，即使快速排序是O(n log n)，对于小数组来说O(n^2)算法通常更快。我不是说这就是我们在这里看到的情况，但是当推理渐近行为时，您必须牢记这一点。 - Matteo Italia

0.5秒处理13M个元素听起来速度太快了，有点让人怀疑。 - erip

为什么你没有为std::sort和std::make_heap同时提供相同的比较函数？ - Adrian McCarthy

Answer 1

这不是一个完整的答案，但如果需要从 13721057 个元素中获取前 25 个元素，最好使用 partial_sort。

如果只需要第 25 个元素，则使用 nth_element。

顺便提一下，如果要按排序顺序获取小于 X 的第一个元素，我会使用带有lambda的auto mid = std::partition，然后使用std::sort(begin,mid)。可能还有更好的方法。

- Johan Lundberg

---

啊，这就是我想要的！不是std::partition。 :) - erip

谢谢大家，partial_sort确实更快。但我仍然不明白为什么sort更快，因为最终我要用堆来实现partial_sort。 - Murat Ayan

@JohanLundberg nth_element的实现类似于快速排序（超级快），时间复杂度为O(N)。对25个元素进行排序：O(25 * log25)（只需要执行一次，不会太多）。抱歉，但我会选择O(13721057) + O(25 * log25)而不是O(13721057 * log25)。 - SashaMN

@SashaMN 一个带有常数的大O并没有太大意义。 - harold

@MuratAyan 实际上，partial_sort 是在 libstdc++ 中使用 make_heap 实现的，这是 GCC 的标准库。因此，如果 partial_sort 很快，那么 make_heap 也必须很快。 - Ilya Popov

Answer 2

编辑：根据评论的建议，我还尝试了使用预排序的输入，在这种情况下，对于我的“昂贵的复制”类型，我确实设法比使用make_heap更快地进行排序，但只有大约5-10%的差距。

无论我尝试什么，都无法在Solaris或Linux（gcc 4.4）上重现您的结果。 make_heap 的时间总是约为1/3。

• 没有优化与-O3之间的唯一区别是总时间，而不是相对顺序。
• 我使用了您精确的项目数。
• 首先尝试对int进行排序，然后是一个更大的“昂贵的复制”类。
• 猜测您使用的包含文件。
• 将计时调用移动到printf之外，以确保它们始终正确排序。

我认为这种差异的实际原因是，您的<和>运算符的复杂度不同，或者相对于在测试中无法复制的方式比较，复制您的对象某种程度上是昂贵的。

- Mark B

---

你尝试过使用预排序向量的“昂贵复制”类吗？（假设您正在使用 OP 的技术，即对于 sort 使用 std::less，对于 heap 使用 std::greater，这会产生相同的结果，那应该是接近最优的 sort 和最劣的 heap。） - rici

@rici 一个预排序的向量在概念上是快速排序的最坏情况，所以我没有尝试那种变体。如果我有一些时间，我会尝试测试那个情况。 - Mark B

这取决于识别枢轴的策略。如果使用中间元素作为枢轴，则是最优的。如果使用随机枢轴，它仍然相当不错，并且仍然具有在分区操作期间不进行任何交换的优点。（我没有使用昂贵的副本进行测试，但使用长整型将std::sort从1.22秒降低到0.30秒。它还大大增加了partial_sort的成本。） - rici

@Mark B：“一个预排序的向量在概念上是快速排序的最坏情况” - 只有当范围的第一个或最后一个元素被选择为枢轴时才会出现这种情况，而且几乎没有人会如此愚蠢。[好吧，我们说几乎没有人。] - Arne Vogel

@ArneVogel，这在很大程度上取决于使用的分区算法类型。3个中位数或随机分区算法倾向于在大多数已排序输入中工作得很好。 - erip