什么使gcc std :: listsorting实现如此之快?

我有一个链表实现,我正在试验Mergesort和QuickSortalgorithm

我不明白的是为什么std :: list中的sorting操作如此之快。 看看在Linux下的std ::列表,它似乎也是链接列表,而不是一个基于数组的列表。

我尝试的合并sorting几乎与Dave Gamble的版本相同: 合并sorting链接列表

另外,我想我会尝试一个简单的快速sorting基于这个代码: http ://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

令人惊讶的是,使用std :: listsorting一千万个随机数,sorting比其他任何一个快十倍左右。

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

Solutions Collecting From Web of "什么使gcc std :: listsorting实现如此之快?"

我一直在看看有趣的列表::排序 ( 源代码 )的GLibC实现,它似乎并没有实现一个传统的合并排序算法(至少不是我以前见过)。

基本上它是做什么的:

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

小提示:将桶X合并到桶Y将移除桶X中的所有元素,并将其添加到桶Y同时保持所有的排序。 另请注意,一个存储桶中元素的数量是02^i

现在为什么这是一个传统的合并排序呢? 那么我不能肯定地说,但是这里有一些想到的东西:

  • 它永远不会遍历列表找到一个中间点,这也使得算法更容易缓存。
  • 由于较早的存储桶较小且使用频率较高,因此merge调用较少频繁地清除缓存。
  • 编译器能够更好地优化这个实现。 将需要比较生成的程序集以确保这一点。

我很确定实施这个算法的人对它进行了彻底的测试,所以如果你想要一个明确的答案,你可能不得不在GCC邮件列表上询问。