内置.NET集合分拣机的性能

Question

有一个问题询问如何对List进行排序.从基本的List.Sort()到List.OrderBy()给出了几种方法.最可笑的是一个自己动手的Se​​lectionSort.我立刻投了票,但它让我思考; 不会的LINQ的排序依据(),适用于清单,做同样的事情？myList.OrderBy(X => x.Property).ToList()将产生基本上发现在什么剩下集合的投影的最小值和产量返回它的迭代器.在浏览整个列表时,这是一种选择排序.

这让我想到了; Lists,SortedLists,Enumerables等内置分类器使用什么算法,并且通过扩展,它们是否应该避免大型集合中的任何一个？SortedList,因为它按键排序,可能会在每次添加时使用单次传递InsertionSort; 找到第一个索引,其值大于新索引,并在其之前插入.列表和数组可能MergeSort本身非常有效,但我不知道Sort()背后的实际算法.我们已经讨论过OrderBy.

我上面所知的似乎表明List.Sort()或Array.Sort()是已知大小列表的最佳选项,并且不鼓励使用Linq对内存列表或数组进行排序.对于一个流,那么OrderBy()确实没有任何其他方法可枚举; 由于您可以将数据保存为流而不必在排序之前完成所有操作,因此可以减轻性能损失.

编辑:

普遍的共识是,给定List或Array的具体实现,Sort()更快.OrderBy是合理的但速度较慢,因为它增加了从传递的可枚举中提取数组的O(N)复杂性.SortedList初始化最终为O(N ^ 2),因为它的内幕是什么.故事的道德,当你有一个实际的List时,使用List.Sort()而不是List.OrderBy().

Answer 1

Enumerable.OrderBy()将IEnumerable <>包含到数组中并使用快速排序.O(n)存储要求.它由System.Core.dll中的内部类完成EnumerableSort<TElement>.QuickSort().由于List <>就地排序,因此存储成本使得它只是简单地对列表进行排序(如果有的话)就没有竞争力.Linq经常通过使用is运算符检查IEnumerable的真实功能来优化.自List <>以来不会在这里工作.排序是破坏性的.

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

SortedList <>具有插入的O(n)复杂度,主导O(log(n))查找插入点的复杂性.因此,将N个未分类的项目放入其中将花费O(n ^ 2).SortedDictionary <>使用红黑树,给出插入O(log(n))的复杂性.因此O(nlog(n))填充它,与摊销快速排序相同.