linux - 是什么让 gcc std::list 排序实现如此之快？

Question

我有一个链表实现，我正在试验 Mergesort 和 QuickSort 算法。

我不明白的是为什么std::list中的排序操作这么快。 查看 linux 下的 std::list ，它似乎也是链表，而不是基于数组的列表。

我在这里尝试的合并排序与 Dave Gamble 的版本几乎相同: Merge Sort a Linked List

另外，我想我会尝试基于这段代码的简单快速排序: http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

令人惊讶的是，使用 std::list 对 1000 万个随机数进行排序并排序比其他任何一个快大约 10 倍。

对于那些提问的人，是的，我需要为这个项目使用我自己的列表类。

Answer 1

我一直在查看有趣的 GLibC 实现 list::sort ( source code ) 而且它似乎没有实现传统的合并排序算法(至少我以前从未见过)。

基本上它的作用是:

1. 创建一系列存储桶(总共 64 个)。
2. 删除列表的第一个元素进行排序并将其与第一个(i=0)桶合并。
3. 如果在合并之前，第i桶不为空，则将第i桶与第i+1桶合并.
4. 重复第 3 步，直到我们与一个空桶合并。
5. 重复步骤 2 和 3，直到要排序的列表为空。
6. 将所有剩余的非空桶从小到大合并在一起。

小提示:将桶 X 与桶 Y 合并将删除桶 X 中的所有元素并将它们添加到桶 Y 同时保持一切有序。另请注意，存储桶中的元素数量为 0 或 2^i。

为什么这比传统的归并排序更快？好吧，我不能肯定地说，但我想到了以下几点:

• 它从不遍历列表来寻找中点，这也使算法对缓存更友好。
• 由于较早的存储桶较小且使用频率较高，因此调用 merge 会降低缓存垃圾的频率。
• 编译器能够更好地优化这个实现。需要比较生成的程序集才能确定这一点。

我很确定实现该算法的人已经对其进行了彻底的测试，因此如果您想要一个明确的答案，您可能必须在 GCC 邮件列表上询问。