WEB开发网
开发学院WEB开发ASP 数组排序方法的性能比较(1):注意事项及试验 阅读

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

 2010-01-27 10:46:56 来源:WEB开发网   
核心提示:昨天有朋友写了一篇文章,其中比较了List<T>的Sort方法与LINQ中排序方法的性能,数组排序方法的性能比较(1):注意事项及试验,而最终得到的结果是“LINQ排序方法性能高于List<T>.Sort方法”,这个结果不禁让我很疑惑,我们下次再来进行分析——这些方法的实现,尤其是LINQ排序的
昨天有朋友写了一篇文章,其中比较了List<T>的Sort方法与LINQ中排序方法的性能,而最终得到的结果是“LINQ排序方法性能高于List<T>.Sort方法”。这个结果不禁让我很疑惑。因为List<T>.Sort方法是改变容器内部元素的顺序,而LINQ排序后得到的是一个新的序列。假如两个排序方法的算法完全一致,LINQ排序也比对方多出元素复制的开销,为什么性能反而会高?如果LINQ排序的算法/实现更为优秀,那为什么.NET Fx不将List<T>.Sort也一并优化一下呢?于是今天我也对这个问题进行了简单的试验。

注意事项
在后面的评论中有人说,List<T>.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中将<compilation />节点的debug属性设为false——考虑到原作者忽略了之前犯了很明显的忌讳,我强烈怀疑这点也没有满足。:)

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

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

static T[] CloneArray<T>(T[] source)
{
  var dest = new T[source.Length];
  Array.Copy(source, dest, source.Length);
  return dest;
}从试验结果上看,数组的复制操作应该并没有造成显著影响。还有便是,经过阅读List<T>.Sort方法的代码,我们可以发现它只是将实现简单地委托给Array.Sort<T>方法,因此我们可以认为它们的性能完全一致。

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

PRivate class Int32Comparer : IComparer<int>
{
  #region IComparer<int> 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:     49

SortWithCustomComparer
    Time Elapsed:  13,847ms
    Gen 0:     49
    Gen 1:     49
    Gen 2:     49

SortWithDelegate
    Time Elapsed:  19,625ms
    Gen 0:     49
    Gen 1:     49
    Gen 2:     49

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

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

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

Tags:数组 排序 方法

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接