List.Sort以及快速排序ZZ
经常看到有人因为使用.net中的集合类处理海量数据时性能不够理想,就武断的得出.net不行,c#也不行这样的结论。对于.net framework这样的类库来说,除了性能以外,通用性和安全性同样重要,而为了后者,有时就不得不牺牲性能。如果你的程序核心就是处理大量数据集合,并且对.net内置类库性能不满意,那么这时候就应该考虑为特定类型实现一个优化的版本了。
事情的由来是我需要对若干个(<10)集合进行排序,每个集合中的元素不会超过2k,老实说,所要处理的数据并不多,但我希望在1ms之内完成所有操作,这就成了挑战。也许有人觉得1ms的要求有些苛刻,但对我的应用来说,1ms已经很些奢侈了. 所要处理的数据非常简单,大部分都是一些数据集对象,每个对象都有一个uint类型的id,并以此为key进行排序:
- public class KeyValuePair
- {
- public uint id;
- public string s = string.Empty;
- public float d;
- public double c;
- }
复制代码
集合大小是不固定的,List自然就是最合适的容器,并且有现成的方法用于排序List.Sort()。我使用了以Comparison委托为参数的版本,并定义了如下函数:
- public static int Compare(KeyValuePair v1,KeyValuePair v2)
- {
- return v1.id.CompareTo(v2.id);
- }
复制代码
我知道,这是一个非常不规范的Comparison定义,应该先检查对象是否为null等等。不过这里只是测试而已,我只想看看List.Sort最快能到什么程度。测试数据为一个有5k元素的List,和5个每个有1k元素的List。通过多次测试,以减少噪音干扰,结果都在2~3ms之间,令人印象非常深刻,足以满足大部份应用的需求。可惜对我的目标来说,还是差了一点。
于是我决定自己写一个函数。List.Sort内部使用了Array.Sort,而后者的实现则是传统快速排序(quicksort)算法。在众所周知的几种排序算法中,quicksort是平均情况下最好的,因此我将仍旧使用这一算法,只是删除List.Sort内一些不必要的检查。代码如下:
- public static void QuickSort(List<KeyValuePair> list, int start,int end)
- {
- if (end <= start)
- return;
- int pivotIndex = FindPivot(list, start, end);
- swap(list, pivotIndex, end);
- int k = Partition(list, start, end, list[end].id);
- swap(list, k, end);
- QuickSort(list, start, k - 1);
- QuickSort(list, k + 1, end);
- }
- public static int Partition(List<KeyValuePair> list, int start, int end, uint piovtValue)
- {
- start--;
- while (true)
- {
- do { start++; }
- while (list[start].id < piovtValue);
- if (start > end)
- break;
- do { end--; }
- while (end > 0 && list[end].id > piovtValue);
- if (start > end)
- break;
- swap(list, start, end);
- }
- return start;
- }
- public static int FindPivot(List<KeyValuePair> list, int start, int end)
- {
- int a = (int)list[start].id;
- int b = (int)list[end].id;
- int middle = (start+end)/2;
- int c = (int)list[middle].id;
- if ((a - b) * (a - c) < 0)
- return start;
- if ((b - a) * (b - c) < 0)
- return end;
- return middle;
- }
- public static void swap(List<KeyValuePair> list, int a, int b)
- {
- KeyValuePair temp = list[a];
- list[a] = list;
- list = temp;
- }
复制代码
这里并没有使用任何特别的技巧,几乎是按数据结构书中的例子照搬过来。它的性能如何呢?以下是测试结果:
list size list.sort myQuickSort
5k 2ms 4ms
10k 6ms 5ms
100k 58ms 26ms
200k 132ms 58ms
非常有趣,当列表元素小于10k时,list.sort比myQuickSort快,而随着元素的增加,myQuickSort将快2~4倍。第二种情况是意料之中的,用reflector查看list.sort的源码就能发现,我的quickSort实现显然要简洁很多。但为什么当元素不多时,会出现如此明显的反差呢?起初我尝试用DotTrace分析两个函数所执行的时间,不幸的是由于此时数据太少,排序执行的太快,DotTrace分析的结果是完全错误的: 总是显示quickSort比list.sort所用的时间少。看来只有查看IL了,于是以下代码引起了我的注意:
IL_0002: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<class Console4Test.KeyValuePair>::get_Item(int32)
这是swap函数中,访问列表元素所产生的代码。过去,我一直认为访问list元素和访问数组元素是相同的,此时,我开始有所怀疑了。居然出现了callvirt这样的指令,虽然在IL中,callvirt并不意味着一定是虚函数调用,reflector也证明List.get_item并不是一个虚方法。直觉告诉我应该对这行代码深究下去,看看JIT究竟把它编译为了什么样的指令:
- swap(list, k, end);
- 000000c7 cmp eax,dword ptr [esi+0Ch]
- 000000ca jb 000000D1
- 000000cc call 787E9A3C
- 000000d1 mov eax,dword ptr [ebp-14h]
- 000000d4 mov edx,dword ptr [esi+4]
- 000000d7 cmp eax,dword ptr [edx+4]
- 000000da jae 0000015E
- 000000e0 mov eax,dword ptr [edx+eax*4+0Ch]
- 000000e4 mov dword ptr [ebp-20h],eax
- 000000e7 cmp edi,dword ptr [esi+0Ch]
- 000000ea jb 000000F1
- 000000ec call 787E9A3C
- 000000f1 mov eax,dword ptr [esi+4]
- 000000f4 cmp edi,dword ptr [eax+4]
- 000000f7 jae 0000015E
- 000000f9 mov eax,dword ptr [eax+edi*4+0Ch]
- 000000fd mov dword ptr [ebp-24h],eax
- 00000100 mov eax,dword ptr [ebp-14h]
- 00000103 cmp eax,dword ptr [esi+0Ch]
- 00000106 jb 0000010D
- 00000108 call 787E9A3C
- 0000010d mov ecx,dword ptr [esi+4]
- 00000110 push dword ptr [ebp-24h]
- 00000113 mov edx,dword ptr [ebp-14h]
- 00000116 call 78F1B384
- 0000011b inc dword ptr [esi+10h]
- 0000011e cmp edi,dword ptr [esi+0Ch]
- 00000121 jb 00000128
- 00000123 call 787E9A3C
- 00000128 mov ecx,dword ptr [esi+4]
- 0000012b push dword ptr [ebp-20h]
- 0000012e mov edx,edi
- 00000130 call 78F1B384
- 00000135 inc dword ptr [esi+10h]
复制代码
这段代码确实让人有些惊奇。首先,swap函数被内联了,这正是我们所希望的;其次,list元素访问也被正确内联了,没有发生我们之前担心的函数调用。这里确实有几条call指令,不过这是在发生异常才会调用的地址。另外,虽然这里没有列出,但值得一提的是FindPivot中的list元素访问则没有内联,每次访问list元素都意味着执行一次函数调用以及这个函数中的16条汇编指令。 最后,2个简单的list元素交换竟然产生了30条以上的汇编代码,我想这也是所有人所料未及的。
看来list元素访问确实是一个潜在的问题。为了证明这一点,我把quickSort中,所有list都改为了array。再次测试,果然,我自己的版本无论在任何情况下都比list.sort快,同时,也比array.sort快。这里不再列出实际的测试数据,只贴出array版本的swap汇编代码:
- swap(list, k, end);
- 00000070 cmp eax,dword ptr [esi+4]
- 00000073 jae 000000BE
- 00000075 mov eax,dword ptr [esi+eax*4+0Ch]
- 00000079 mov dword ptr [ebp-1Ch],eax
- 0000007c mov ecx,dword ptr [esi+edi*4+0Ch]
- 00000080 mov eax,dword ptr [ebp-10h]
- 00000083 lea edx,[esi+eax*4+0Ch]
- 00000087 call 78F11F98
- 0000008c push dword ptr [ebp-1Ch]
- 0000008f mov edx,edi
- 00000091 mov ecx,esi
- 00000093 call 78F1B384
复制代码
可以看到,代码减少为了原来的1/3。两个call同样是.net内部的一些安全检查代码。
好了,现在知道我的代码慢在哪里了,但这并不能解释list.sort为什么在元素少的时候比较快,难道它不受list元素访问效率的影响吗?是的,list本身并不会受到自身元素访问机制的影响,因为他调用Array.sort时,传递的是内部储存的私有元素数组成员,而不是他自己。因此,可以猜测,当元素较少时,排序算法执行的非常快,此时,元素访问方式的不同,就成了明显的瓶颈,而当处理元素较多时,大部分时间都用在排序上,元素访问的代价则逐渐变小。
以上手写的quickSort方法还能进一步优化吗?显然是可以的:
1,当quickSort中的分组元素小于10时,改用插入排序,可以带来大约5~10%的性能提升:
- public static void QuickSort(List<KeyValuePair> list, int start,int end)
- {
- if (end <= start)
- return;
- int pivotIndex = FindPivot(list, start, end);
- swap(list, pivotIndex, end);
- int k = Partition(list, start, end, list[end].id);
- swap(list, k, end);
- if (k - start <= 10)
- InsertSort(list, start, k - 1);
- else
- QuickSort(list, start, k - 1);
- if (end - k - 1 <= 10)
- InsertSort(list, start, k - 1);
- else
- QuickSort(list, k + 1, end);
- }
复制代码
2,把FindPivot函数手动内两到QuickSort中。
3. 用栈模拟递归,本人不是太推荐这种做法。
4. 也许还能用指针优化关键操作,不过似乎c#不允许对reference type使用指针L
小结:
在极端性能要求下,需要对元素进行排序时:
当n< ~5k时,用array代替list,或者为array写一个简单的wrapper,并且自己实现sort;或者直接使用list.sort
当 n > 10k时, 实现自己的sort方法,至少能得到2~4倍的提速。
最新文章
- Jquery 插件\Js 插件收集
- CxImage在VS2010下的配置
- ARC的原理详解
- Python3基础 int(input())输入数字并产生一个int类型变量
- ASP.NET 2.0 异步页面原理浅析 [1]
- 使用水晶报表更新后出现“值不能为 null。 参数名: inputString”
- 什么是Nib文件?(Nib文件是一种特殊类型的资源文件,它用于保存iPhone OS或Mac OS X应用程序的用户接口)
- struts2值栈分析
- 二,WPF的布局
- 【转载】MySQL被慢sql hang住了,用shell脚本快速清除不断增长的慢sql的办法
- MySQL如何选择float, double, decimal
- C# Obsolete
- CSS 最核心的几个概念
- CI 笔记 数据库
- 我终于解决UM编辑器了 泪......
- 教你wamp下多域名如何配置
- Android使用XML全攻略(1)
- linux c socket 并发 服务端
- 【 js 基础 】【 源码学习 】backbone 源码阅读(一)
- Centos7安装vsftpd (FTP服务器)
热门文章
- [Effective JavaScript 笔记]第21条:使用apply方法通过不同数量的参数调用函数
- NGUI的部分控件无法更改layer?
- iOS6.1完美越狱工具evasi0n1.3下载
- AMD64与IA64的区别
- Linux 磁盘的组成
- VC++ TinyXML
- codeforces B. Sereja and Stairs 解题报告
- cc.game
- JavaScript当离开页面时可以进行的操作
- July 19th, Week 30th Tuesday, 2016