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

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

  注意事项

  在后面的评论中有人说,List.Sort是“内部排序”,而LINQ排序是“外部排序”。但是根据外部排序的定义,这个说法是不正确的。“外部排序”是指在排序目标规模太大,导致主存相对太小(如内存)而不够放,不得不利用外部存储(如硬盘)做一些“过渡”的排序方式。因此,LINQ排序虽然生成了新的序列,但还是内部排序。事实上,从定义中我们也可以很容易推断出,如果数据规模相同,外部排序的性能一般总是比内部排序要差——不过事实上我们不太好做这样的比较,因为如果是能够进行内部排序的情况下,谁会利用麻烦的外部排序呢?

  那篇文章中得到的结果是不对的,那么问题究竟出在什么地方呢?在我看来,问题主要出在以下两点。

  首先,原文作者使用了ASP.NET作为测试环境。值得注意的是,ASP.NET执行.NET代码的时候,使用的是IIS进程中托管的CLR,它的配置和直接运行.NET应用程序时不同(不同的CLR托管方式配置很可能不一样——例如SQL Server里托管的CLR)。例如,ASP.NET中每个线程的调用栈为250K,而直接运行.NET应用程序时这个大小为1M。根据我的经验(也就是说我无法确切地“证明”这个说法),在ASP.NET中执行此类性能测试得到的结果可能很不稳定。因此,一般我建议使用一个最普通的Console应用程序来进行性能测试。

  其次,也是更重要的原因,便是原作者只测试了一次排序的性能。这是性能测试中的大忌讳,因为这么做的话误差实在太大。例如,会不会在进行某一个方法的测试时,忽然系统起了一个后台进程进行维护,动用了一部分CPU和内存资源,从而导致测试消耗的时间很冤枉地增加。而且,.NET程序是有一个“预热”过程的,这导致代码在第一次执行时需要有一个生成本机代码的过程(俗称“预热”)。这个过程和代码的执行效率是无关的,因为它无论如何只会产生一次消耗,而代码是会被执行无数次的。因此,在进行测试的时候,一定要将测试目标反复执行N次,至少要让执行耗时到达“秒”级别,这样的结果才有一定参考价值。如果执行时间太少的话测试也可能不准确——要知道“计时器”也是有开销,也是有误差的,我们要得到尽量准确的结果。

  最后,我强烈建议使用CodeTimer进行计时,因为在它的Initialize方法中会将当前进程及线程的优先级设置到最高,以此减少其他无关因素所造成的干扰。如果可以的话,其实也应该尽量关闭系统中其他应用程序或服务,并且最好可以断开网络(也是一个道理)。当然Release编译也是一定需要的。而且,如果您一定需要使用ASP.NET进行性能测试的话,也千万记得要在web.config中将节点的debug属性设为false——考虑到原作者忽略了之前犯了很明显的忌讳,我强烈怀疑这点也没有满足。:)

  因此,我认为那篇文章中的测试结果是不准确的,参考价值很低。

重新测试

  既然如此,我们来重新进行一次试验吧。不过我现在来比较的是Array.Sort方法与LINQ排序的性能。这么做的主要原因是,由于我们要执行多次排序操作,因此每次都应该使用乱序的序列。但是,每次生成新的序列也会带来开销,如果使用List的话,填充元素的开销会很大,但如果是普通数组的话,就可以用性能很高的Array.Copy方法了:

static T[] CloneArray(T[] source){    var dest = new T[source.Length];    Array.Copy(source, dest, source.Length);    return dest;}

  从试验结果上看,数组的复制操作应该并没有造成显著影响。还有便是,经过阅读List.Sort方法的代码,我们可以发现它只是将实现简单地委托给Array.Sort方法,因此我们可以认为它们的性能完全一致。

  Array.Sort方法其实有两“类”重载,一类是使用IComparer对象进行比较,而另一类则使用了Comparison这个委托对象进行比较。为此,我们构造一个Int32Comparer类来实现IComparer接口:

private class Int32Comparer : IComparer<int>{    #region IComparer Members    public int Compare(int x, int y)    {        return x - y;    }    #endregion}

  于是,两“类”重载的测试方法分别为:

static void SortWithCustomComparer(int[] array){    Array.Sort(array, new Int32Comparer());}static void SortWithDelegate(int[] array){    Array.Sort(array, (x, y) => x - y);}

  但是,我在这里还是再补充一个排序“方法”(原因以后再谈)。因为int类型是框架知道该如何比较的类型,因此我们其实也可以这么写:

static void SortWithDefaultComparer(int[] array){    Array.Sort(array, Comparer<int>.Default);}

  最后,参加活动的自然还有LINQ排序:

static void SortWithLinq(int[] array){    var sorted =        (from i in array         orderby i         select i).ToList();}

  这里我使用的是ToList方法而不是ToArray方法来生成新序列,这是因为ToList的方法性能更高一些,我还是想尽可能将关注点放在“排序”而不是其他方面。

  比较代码如下:

static void Main(string[] args){    var random = new Random(DateTime.Now.Millisecond);    var array = Enumerable.Repeat(0, 1000 * 500).Select(_ => random.Next()).ToArray();    CodeTimer.Initialize();    CodeTimer.Time("SortWithDefaultComparer", 100,        () => SortWithDefaultComparer(CloneArray(array)));    CodeTimer.Time("SortWithCustomComparer", 100,        () => SortWithCustomComparer(CloneArray(array)));    CodeTimer.Time("SortWithDelegate", 100,        () => SortWithDelegate(CloneArray(array)));    CodeTimer.Time("SortWithLinq", 100,        () => SortWithLinq(CloneArray(array)));    Console.ReadLine();}

  首先,我们生成一个拥有50万个随机元素的数组,以此进行排序方法的性能比较。每次比较的时候我们都使用CloneArray方法来生成一个新的数组。

试验结果

  试验结果如下:

SortWithDefaultComparer        Time Elapsed:   7,662ms        Gen 0:          49        Gen 1:          49        Gen 2:          49SortWithCustomComparer        Time Elapsed:   13,847ms        Gen 0:          49        Gen 1:          49        Gen 2:          49SortWithDelegate        Time Elapsed:   19,625ms        Gen 0:          49        Gen 1:          49        Gen 2:          49SortWithLinq        Time Elapsed:   31,785ms        Gen 0:          99        Gen 1:          99        Gen 2:          99

  从结果上来,四种做法的性能区别还是非常明显的:使用Comparer.Default进行排序的耗时只有LINQ排序的1/4。有趣的是,从GC次数上来看,LINQ排序也刚好是其他三种的一倍,和“理论值”几乎完全吻合。

  经过测试后发现,其实LINQ排序的性能并不会比Array.Sort要高,甚至还有明显的劣势。由于排序算法都已经被用到滥了,而且几乎已经成为了一个“标准”,因此从算法上来看它们不应该会有那么大的差距。所以,我们这里应该可以得出一个比较靠谱的推测:这几种排序方法的性能差距,完全是由于具体实现上的细节引起的。

  至于其中的原因,我们下次再来进行分析——这些方法的实现,尤其是LINQ排序的实现,似乎还是挺有趣的。

  本文代码:http://gist.github.com/281857

相关文章

  1. 数组排序方法的性能比较(1):注意事项及试验
  2. 数组排序方法的性能比较(2):Array.Sort实现分析
  3. 数组排序方法的性能比较(3):LINQ排序实现分析

NET技术数组排序方法的性能比较(上):注意事项及试验,转载需保留来源!

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。