数组排序方法的性能比较(2):Array.Sort<T>实现分析

昨天我们比较了Array.Sort<T>方法与LINQ排序的性能,知道了LINQ排序的性能以较大幅度落后 于Array.Sort<T>方法。而对于Array.Sort<T>来说,性能最高的是其中使用 Comparer<int>.Default作为比较器的重载方法。在前文的末尾我们做出了推测:由于排序算法已 经近乎一个标准了(快速排序),因此从算法角度来说,Array.Sort<T>方法和LINQ排序上不应该 有那么大的差距,因此造成两者性能差异的原因,应该是具体实现方式上的问题。

下载.NET框架的代码

既然是比较实现的区别,那么阅读代码是很直接的选择。谈到阅读.NET代码,我们往往会使用.NET Reflector将框架的程序集反编译为C#代码——不排除有朋友喜欢观察IL,并认为它们更直接,更底层。 不过我倒觉得在绝大部分情况下,IL能看出的东西从C#也能看出,而C#无法了解的IL也帮不上忙,因此许 多“由IL发现问题”的文章其实只是自己和自己在爽。

不过,虽然.NET Reflector将程序集反编译成非常优秀的C#代码,但是还是无法恢复之前的不少信息 。例如,局部变量名无法得知,这就给理解代码意图造成了困难。再例如,为了可读性我们可能会将一些 条件语句分开写,而C#编译器则可能把它们连做一块儿。至于注释等明显会被去除的东西就更不用说了。 因此,在能直接读到代码的情况下,我并不倾向于使用.NET Reflector。

您可能会说:这不是废话么,不过有些类库——如.NET框架并没有提供源代码,这又有什么办法呢? 其实微软也已经公布了.NET框架相当部分程序集的源代码(几乎所有v2.0的程序集,如 mscrolib, System,System.Web等等),而且它们其实都可以使用NetMassDownloader直接下载到本地。随员代码发 布的还有方便调试的pdb文件,不过这是另一个话题了,我们现在只关心源代码。

因此,我建议您将所有微软提供的源代码都下载到本地。在看不懂.NET Reflector的反编译结果时, 不妨参考一下源代码——还是包含注释的源代码。

Array.Sort<T>方法实现

各Array.Sort<T>方法的重载最终都会委托给下面这个重载来执行:

public static void Sort<T>(T[] array, int index, int length,  IComparer<T> comparer)
{
   ...

   if (length > 1)
   {
     // <STRIP>
     // TrySZSort is still faster than the generic implementation.
     // The reason is Int32.CompareTo is still expensive than just using  "<" or ">".
     // </STRIP>
     if (comparer == null || comparer == Comparer<T>.Default)
     {
       if (TrySZSort(array, null, index, index + length - 1))
       {
         return;
       }
     }

     ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
   }
}

时间: 2024-10-14 21:25:24

数组排序方法的性能比较(2):Array.Sort&lt;T&gt;实现分析的相关文章

一起谈.NET技术,数组排序方法的性能比较(3):LINQ排序实现分析

上次我们分析了Array.Sort方法的实现方式,并了解到类库会为一些特例而使用高性能的排序方式--int数组便是这样一例,因此从测试结果上来看其性能特别高.不过从数据上看,即便是在普通的情况下,Array.Sort的性能也比LINQ排序要高.不过也有朋友从测试中得出的结论正好相反,这又是为什么呢?那么现在,我们再来分析一下LINQ排序的实现方式吧,希望这样可以了解到两者性能差别的秘密. 只可惜,LINQ排序的代码在System.Core.dll程序集中,微软没有发布这部分源代码,我们只得使用.

数组排序方法的性能比较(3):LINQ排序实现分析

上次我们分析了Array.Sort<T>方法的实现方式,并了解到类库会为一些特例而使用高性能的排 序方式--int数组便是这样一例,因此从测试结果上来看其性能特别高.不过从数据上看,即便是在普 通的情况下,Array.Sort<T>的性能也比LINQ排序要高.不过也有朋友从测试中得出的结论正好相 反,这又是为什么呢?那么现在,我们再来分析一下LINQ排序的实现方式吧,希望这样可以了解到两者性 能差别的秘密. 只可惜,LINQ排序的代码在System.Core.dll程序集中,微软没

数组排序方法的性能比较(中):Array.Sort 实现分析

昨天我们比较了Array.Sort方法与LINQ排序的性能,知道了LINQ排序的性能以较大幅度落后于Array.Sort方法.而对于Array.Sort来说,性能最高的是其中使用Comparer.Default作为比较器的重载方法.在前文的末尾我们做出了推测:由于排序算法已经近乎一个标准了(快速排序),因此从算法角度来说,Array.Sort方法和LINQ排序上不应该有那么大的差距,因此造成两者性能差异的原因,应该是具体实现方式上的问题. 下载.NET框架的代码 既然是比较实现的区别,那么阅读代

一起谈.NET技术,数组排序方法的性能比较(中):Array.Sort&lt;T&gt; 实现分析

昨天我们比较了Array.Sort方法与LINQ排序的性能,知道了LINQ排序的性能以较大幅度落后于Array.Sort方法.而对于Array.Sort来说,性能最高的是其中使用Comparer.Default作为比较器的重载方法.在前文的末尾我们做出了推测:由于排序算法已经近乎一个标准了(快速排序),因此从算法角度来说,Array.Sort方法和LINQ排序上不应该有那么大的差距,因此造成两者性能差异的原因,应该是具体实现方式上的问题. 下载.NET框架的代码 既然是比较实现的区别,那么阅读代

艾伟_转载:数组排序方法的性能比较(中):Array.Sort&lt;T&gt; 实现分析

昨天我们比较了Array.Sort方法与LINQ排序的性能,知道了LINQ排序的性能以较大幅度落后于Array.Sort方法.而对于Array.Sort来说,性能最高的是其中使用Comparer.Default作为比较器的重载方法.在前文的末尾我们做出了推测:由于排序算法已经近乎一个标准了(快速排序),因此从算法角度来说,Array.Sort方法和LINQ排序上不应该有那么大的差距,因此造成两者性能差异的原因,应该是具体实现方式上的问题. 下载.NET框架的代码 既然是比较实现的区别,那么阅读代

数组排序方法的性能比较(上):注意事项及试验

昨天有朋友写了一篇文章,其中比较了List的Sort方法与LINQ中排序方法的性能,而最终得到的结果是"LINQ排序方法性能高于List.Sort方法".这个结果不禁让我很疑惑.因为List.Sort方法是改变容器内部元素的顺序,而LINQ排序后得到的是一个新的序列.假如两个排序方法的算法完全一致,LINQ排序也比对方多出元素复制的开销,为什么性能反而会高?如果LINQ排序的算法/实现更为优秀,那为什么.NET Fx不将List.Sort也一并优化一下呢?于是今天我也对这个问题进行了简

艾伟_转载:数组排序方法的性能比较(上):注意事项及试验

昨天有朋友写了一篇文章,其中比较了List的Sort方法与LINQ中排序方法的性能,而最终得到的结果是"LINQ排序方法性能高于List.Sort方法".这个结果不禁让我很疑惑.因为List.Sort方法是改变容器内部元素的顺序,而LINQ排序后得到的是一个新的序列.假如两个排序方法的算法完全一致,LINQ排序也比对方多出元素复制的开销,为什么性能反而会高?如果LINQ排序的算法/实现更为优秀,那为什么.NET Fx不将List.Sort也一并优化一下呢?于是今天我也对这个问题进行了简

数组排序方法的性能比较(4):LINQ方式的Array排序

经过前两篇文章的分析,我们已经了解了Array.Sort<T>与LINQ排序两种实现方式的差别:前者 直接比较两个元素的大小,而后者先选出每个元素的"排序依据"再进行比较.因此,虽然后者需要相对 较多的"周边工作",但由于每次比较时都可以仅仅使用高效的基础类型(如int),因此从整体来看, 两者的性能高低难以辨别.不过,既然我们已经了解LINQ排序"高效"的原因,又能否将其利用在数组排 序上呢?程序是人写的,此类问题大都有肯定的答案.

数组排序方法的性能比较(5):对象大小与排序性能

在我公开测试结果之后,有朋友也进行了其他测试.在测试中我使用的是int数组,经过分析之后我们 了解到Array.Sort<T>对于int数组有特殊的优化.于是,某些朋友使用了一些引用类型的数组进行 排序,得到Array.Sort<T>方法的性能落后于LINQ排序--虽然由于测试方式的问题,这个结果和 结论都不太妥当.不过在讨论的过程中,我们都意识到了一个问题:在其他条件不变的情况下,引用类型 的字段越多,Array.Sort<T>方法所需时间就越久.这次我们就来讨论一下