数码控科技猎奇Iphone动漫星座游戏电竞lolcosplay王者荣耀攻略allcnewsBLOGNEWSBLOGASKBLOGBLOGZSK全部技术问答问答技术问答it问答代码软件新闻开发博客电脑/网络手机/数码笔记本电脑互联网操作系统软件硬件编程开发360产品资源分享电脑知识文档中心IT全部全部分类 全部分类技术牛文全部分类教程最新 网页制作cms教程平面设计媒体动画操作系统网站运营网络安全服务器教程数据库工具网络安全软件教学vbscript正则表达式javascript批处理更多»编程更新教程更新游戏更新allitnewsJava 新闻网络医疗信息化安全创业站长电商科技访谈域名会议专栏创业动态融资创投创业学院 / 产品经理创业公司人物访谈营销 开发数据库服务器系统虚拟化云计算 嵌入式移动开发作业作业1常见软件all电脑网络手机数码生活游戏体育运动明星影音休闲爱好文化艺术社会民生教育科学医疗健康金融管理情感社交地区其他电脑互联网软件硬件编程开发360相关产品手机平板其他电子产品摄影器材360硬件通讯智能设备购物时尚生活常识美容塑身服装服饰出行旅游交通汽车购房置业家居装修美食烹饪单机电脑游戏网页游戏电视游戏桌游棋牌游戏手机游戏小游戏掌机游戏客户端游戏集体游戏其他游戏体育赛事篮球足球其他运动球类运动赛车健身运动运动用品影视娱乐人物音乐动漫摄影摄像收藏宠物幽默搞笑起名花鸟鱼虫茶艺彩票星座占卜书画美术舞蹈小说图书器乐声乐小品相声戏剧戏曲手工艺品历史话题时事政治就业职场军事国防节日风俗法律法规宗教礼仪礼节自然灾害360维权社会人物升学入学人文社科外语资格考试公务员留学出国家庭教育学习方法语文物理生物工程学农业数学化学健康知识心理健康孕育早教内科外科妇产科儿科皮肤科五官科男科整形中医药品传染科其他疾病医院两性肿瘤科创业投资企业管理财务税务银行股票金融理财基金债券保险贸易商务文书国民经济爱情婚姻家庭烦恼北京上海重庆天津黑龙江吉林辽宁河北内蒙古山西陕西宁夏甘肃青海新疆西藏四川贵州云南河南湖北湖南山东江苏浙江安徽江西福建广东广西海南香港澳门台湾海外地区

实现分析" href="http://www.knowsky.com/542130.html" target="_blank">数组排序方法的性能比较(2):Array.Sort实现分析

日期:2016/7/19 9:48:00 来源:本网整理
/*学院显示页 左上*/ var cpro_id = "u2659916"; 昨天我们比较了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);
    }
}我们知道,从逻辑上说,Array.Sort<T>方法会使用IComparer<T>类型的比较器来判断两个元素的大小。不过在这里,.NET框架作了一个“特例”,它在用户没有提供比较器,或是直接使用默认比较器的时候利用TrySZSort方法进行排序。如果TrySZSort方法如果返回true,则表示排序完成,直接返回。如果它返回false,则继续使用内置的排序方法进行处理。那么TrySZSort又是如何实现的呢?

PRivate static extern bool TrySZSort(Array keys, Array items, int left, int right);这是一个extern方法,说明它是由CLR直接实现的,我们无法得知它的具体算法或是意图。不够从注释中可以得知,这个做法的目的是提高性能(明白注释的优势了吧)。每次使用IComparer<T>的Compare方法进行比较的时候相当于是一次虚方法的调用,CLR需要计算它的偏移量,也无法将其内联。这个细节相对于直接进行int的大小比较来说,也是有较大开销的。使用TrySZSort这种外部方法进行排序,有助于提高在特定情况下的执行效率。

因此,我们应该可以有足够信心来推断出TrySZSort的作用。TrySZSort方法的作用是对一些可以直接进行比较的原生类型(如int等)进行排序,如果它发现自己无法支持数组中元素的类型,那么就返回false,否则便排序后并返回true。如果TrySZSort返回false,便会使用ArraySortHelper进行排序。而其中的实现便是标准(真的很标准)的快速排序,如果您感兴趣的话可以自行阅读其中的代码。

值得注意的是,Array是定义在System命名空间下的类型,而ArraySortHelper则定义在System.Collections.Generic命名空间下。在阅读微软提供的源代码时有个麻烦之处便是不容易导航,例如ArraySortHelper类便让我一顿好找。不过,其实我们也可以配合.NET Reflector中强大的导航功能来快速定位到某个类的位置,然后直接去查找它对应的文件。当然,如果您索引了文件内容,也可以查找类似“class ArraySortHelper”这样的关键字,也可以很快找到特定文件。

Array.Sort<T>其他重载的性能
以上,我们已经知道为什么使用Comparer<int>.Default作为比较器时性能最高了,因为对于int类型来说,Array.Sort<T>方法会使用最快的TrySZSort方法进行排序。而如果我们使用自定义的Int32Comparer进行比较的话,Compare方法调用的开销是无可避免的,根据实验结果,使用Int32Comparer的执行时间比前者有80%的增加也可以接受。

那么使用委托进行排序的时候为什么比Int32Comparer更慢一些呢?且看其代码:

public static void Sort<T>(T[] array, Comparison<T> comparison)
{
    ...

    IComparer<T> comparer = new FunctorComparer<T>(comparison);
    Sort<T>(array, comparer);
}其实原因很简单,因为.NET框架使用了FunctorComparer封装了comparison委托。这样在每次比较时,它相对于Int32Comparer来说还增加了委托执行的开销——这又相当于一次虚方法的调用:需要寻址,无法内联。

至此,我们已经分析了Array.Sort<T>各重载的实现方式,也了解了三种Array.Sort<T>重载性能有别的原因。刚好,不久前姜敏兄又回应了我的文章,认为使用Person类,而不是int类型进行比较的时候,仍旧是LINQ排序比较快——由此他认为两种做法的性能和类型也有关系。您认为这个说法正确吗?其实从实现上看,Array.Sort<T>几乎已经是最优的做法了。相反,LINQ排序由于会生成额外的序列,性能想要超过Array.Sort<T>几乎是件不可能的事情。但事实真是如此吗?

那这测试结果……我也写了一个Person类的测试(http://gist.github.com/282796),还是Array.Sort<T>比较快。那么为什么两个结果会有所不同呢?这是一个值得探讨的问题。


  • 本文相关:
  • 详解ABP框架中的日志管理和设置管理的基本配置
  • asp控制xml数据库的经典代码
  • ASP网站中数据库被挂木马的解决方案
  • asp实现excel中的数据导入数据库
  • ASP的Error对象知识简析
  • ASP建立一个简单的聊天室
  • ASP开发基于XML的留言板
  • 利用ASP输出excel文件实例讲解
  • ASP提速五大技巧
  • Asp编码优化技巧
  • 免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
    Copyright © 2017 www.zgxue.com All Rights Reserved