是什么让 gcc std::list 排序实现如此之快? [英] What makes the gcc std::list sort implementation so fast?

问题描述

我有一个链表实现，我正在试验合并排序和快速排序算法.

I have a linked list implementation and I'm experimenting with both Mergesort and QuickSort algorithms.

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

What I don't understand is why the sort operation in std::list is so fast. Looking at the std::list under linux and it appears to be linked list as well, not an array based list.

我在这里尝试的合并排序与 Dave Gamble 的版本几乎相同:合并排序链接列表

The merge sort I tried almost identical to Dave Gamble's version here: Merge Sort a Linked List

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

Also, I thought I'd try a simple quicksort based on this code: http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

令人惊讶的是，使用 std::list 对 1000 万个随机数进行排序，排序速度比其他任何一个都快 10 倍左右.

Suprisingly, to sort 10 million random numbers using std::list and sort was around 10 times quicker than either of those others.

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

And for those that are asking, yes I need to use my own list class for this project.

推荐答案

我一直在研究 list::sort (源代码)，而且它似乎没有实现传统的归并排序算法(至少我以前没有见过).

I've been taking a look at the interesting GLibC implementation for list::sort (source code) and it doesn't seem to implement a traditional merge sort algorithm (at least not one I've ever seen before).

基本上它的作用是:

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

1. Creates a series of buckets (64 total).
2. Removes the first element of the list to sort and merges it with the first (i=0th) bucket.
3. If, before the merge, the ith bucket is not empty, merge the ith bucket with the i+1th bucket.
4. Repeat step 3 until we merge with an empty bucket.
5. Repeat step 2 and 3 until the list to sort is empty.
6. Merge all the remaining non-empty buckets together starting from smallest to largest.

小提示:合并一个桶X和一个桶Y会移除桶X中的所有元素，并添加到桶Y，同时保持一切有序.另请注意，存储桶中的元素数为 0 或 2^i.

Small note: merging a bucket X with a bucket Y will remove all the elements from bucket X and add them to bucket Y while keeping everything sorted. Also note that the number of elements within a bucket is either 0 or 2^i.

现在为什么这比传统的归并排序更快?好吧，我不能肯定地说，但我想到了一些事情:

Now why is this faster then a traditionnal merge sort? Well I can't say for sure but here are a few things that comes to mind:

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

• It never traverses the list to find a mid-point which also makes the algorithm more cache friendly.
• Because the earlier buckets are small and used more frequently, the calls to merge trash the cache less frequently.
• The compiler is able to optimize this implementation better. Would need to compare the generated assembly to be sure about this.

我很确定实现该算法的人对其进行了彻底的测试，所以如果你想要一个明确的答案，你可能不得不在 GCC 邮件列表中询问.

I'm pretty sure the folks who implemented this algorithm tested it thoroughly so if you want a definitive answer you'll probably have to ask on the GCC mailing list.

这篇关于是什么让 gcc std::list 排序实现如此之快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！