登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

学无止境

一点积累,与大家分享

 
 
 

日志

 
 

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

2010-05-14 15:17:25|  分类: C#技术 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
比较了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排序的实现,似乎还是挺有趣的。

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

  评论这张
 
阅读(503)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018