.NET内置集合排序器的性能表现

8
有人问如何对List进行排序,提供了几种方法,从基本的List.Sort()到List.OrderBy()。最可笑的是自己编写选择排序算法。我立即投票反对它,但这让我想到:不是Linq的OrderBy()应用于列表就可以做同样的事情吗?myList.OrderBy(x=>x.Property).ToList()将生成一个迭代器,在剩余的集合中找到投影的最小值并返回它。遍历整个列表时,这就是一种选择排序。
这让我想到:内置的排序器(Lists、SortedLists、Enumerables等)使用哪些算法,从而推断出是否应该避免使用其中的任何一种来处理大型集合?SortedList因为按键排序,可能会在每次添加时使用单趟插入排序;查找第一个值大于新值的索引,并在其前插入。Lists和Arrays可能会高效地MergeSort自己,但我不知道Sort()背后的实际算法。我们已经讨论过OrderBy。
以上内容表明,对于已知大小的列表,List.Sort()或Array.Sort()是最佳选项,不建议使用Linq对内存中的列表或数组进行排序。对于流,除了对可枚举对象进行OrderBy()排序外,没有其他方法;性能损失得到缓解,因为您可以将数据保留为流,而不必在排序之前全部获取数据。
编辑:
普遍的共识是:在具体实现List或Array时,Sort()更快。OrderBy是合理的,但速度较慢,因为它增加了从传递的可枚举对象中提取数组的O(N)复杂度。SortedList初始化最终变成了O(N^2),因为底层实现如此。故事的寓意是,在有实际列表时,请使用List.Sort()而不是List.OrderBy()。

2
我认为大多数内置排序算法使用快速排序。如果你想加速它,可以移除边界检查。List.Sort 也在内部使用 Array.Sort。 - Mikael Svenson
1
@Mikael 是正确的,OrderBy() 也使用快速排序。@KeithS,你可以愉快地浏览源代码,它是公开可用的(并集成到 VS 中)。EnumerableSorter.QuickSort 是 OrderBy 使用的方法名称。 - Kirk Woll
.Net Reflector 再次拯救了我们 - 真是太棒了! - Will A
@Mikael:在.NET中,您无法关闭边界检查。 - H H
@Henk:我的意思是,在集合长度上避免边界检查。所有的.Sort()方法都会在开头进行检查。对于时间关键型系统,您可以自己实现并跳过长度/索引检查来节省时间。 - Mikael Svenson
4个回答

7

Enumerable.OrderBy() 将 IEnumerable<> 读入到数组中,并使用快速排序。需要 O(n) 的存储空间。它由 System.Core.dll 中的内部类 EnumerableSort<TElement>.QuickSort() 完成。由于 List<> 可以原地排序,因此存储成本使其与简单排序列表不具竞争力。Linq 经常通过使用 is 运算符检查 IEnumerable 的真实能力来进行优化。这里不起作用,因为 List<>.Sort 是破坏性的。

List<>.Sort 和 Array.Sort 使用原地快速排序。

SortedList<> 在插入时具有 O(n) 的复杂度,支配着查找插入点的 O(log(n)) 复杂度。因此将 N 个未排序的项放入其中将花费 O(n^2)。SortedDictionary<> 使用红黑树,给出插入 O(log(n)) 复杂度。因此填充它需要 O(nlog(n)),与摊销的快速排序相同。


SortedList<>为什么插入的时间复杂度是O(n)?我想应该由于BinarySearch使它变成了O(log(N))。 - AndreasKnudsen
@Andreas - 它必须为要插入的元素腾出空间。这需要移动O(n)个元素。它在底层是一个数组。 - Hans Passant
嗯,现在我在想,如果SortedList使用带有“中心”引用的双向链表实现会怎样呢?索引单个元素的复杂度接近O(N)(您可以从任一端或中心开始并朝着实际的“索引”工作),但迭代的复杂度也是O(N)(“下一个”很便宜),并且插入,给定O(logN)二分搜索(您可以从中心开始),将是常数(重新分配两个指针),总插入复杂度为O(logN)。这将使排序的双向链表填充具有N个未排序元素的复杂度为O(NlogN)。 - KeithS
2
@Keith:大O符号对将算法分为两部分并不太关注。现代计算机CPU缓存的工作方式完全打败了链表所能提供的较小的O。CPU被高度优化以从RAM加载连续的字节内存。链表具有非常差的缓存局部性,会在缓存未命中时使CPU停顿数百个周期。这就是为什么List<>实际上是底层的数组,而不是传统数据结构教材中的链表。 - Hans Passant
如果你想在SortedList上进行O(lg n)操作,你可以使用SortedDictionary,因为SortedList实际上是一个KeyValuePair元素列表。 - Gabe

4

了解每种方法的性能表现的一种方式是对其进行测量:

List<int> createUnsortedList()
{
    List<int> list = new List<int>();
    for (int i = 0; i < 1000000; ++i)
        list.Add(random.Next());
    return list;
}

void Method1()
{
    List<int> list = createUnsortedList();
    list.Sort();
}

void Method2()
{
    List<int> list = createUnsortedList();
    list.OrderBy(x => x).ToList();
}

结果:

  • 方法1: 0.67秒(List.Sort)
  • 方法2: 3.10秒(OrderBy)

这表明,即使对于非常大的列表,使用 OrderBy 的性能也是合理的,但它并不像在列表上使用内置的 Sort 方法那样快。这可能是因为 OrderBy 的代码略微更加灵活 - 它需要对每个元素进行评估的键选择器。


4

是的,你的猜测听起来正确。我进行了一些测试以确认它。

对于5000000个整数,

data.Sort();                           //  500 ms
data = data.OrderBy(a => a).ToList();  // 5000 ms

这可能表明OrderBy不适用于大型集合,但可能不是我所说的原因。显然,使用OrderBy需要了解整个可枚举对象,这破坏了无序Linq迭代器的流式传输质量。 - KeithS

4
通过反射,我发现List Sort方法利用快速排序(http://en.wikipedia.org/wiki/Quicksort)通过System.Collections.Generic.GenericArraySortHelper进行排序。
SortedList使用Array.BinarySearch来确定每个Add的插入位置。
枚举器没有排序逻辑。
快速排序是大多数情况下的好选择,但如果输入数据非常不幸,则可能接近O(n ^ 2)。
如果您怀疑输入数据已按快速排序的不幸顺序排列,则一个技巧是先随机化数据(这总是便宜的),然后对随机化的数据进行排序。 快速排序算法可以实现一些技巧来减轻排序已经排序(或几乎排序)的输入数据的问题,我不知道BCL实现是否执行这些技巧。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接