[自转] 几种排序算法的性能的统计图

rednaxela 发表于 2008-3-20 12:49:24

原帖：http://rednaxelafx.javaeye.com/blog/174063

好久没发点有趣的东西了，今天发个来看看。

上个星期raven给了我一组有趣的统计图。跟大家分享下吧～

下面是对几种排序算法的性能的统计图。
x轴是输入数组的大小，从1000到10000；y轴是消耗的时间，单位为ms。
每条统计线所代表的排序算法如底部的图例所示。

每张图代表一种输入类型的状况。
Sorted表示输入是已经排好序的（按照从小到大），
almost-sorted表示大约有20%的元素是不符合顺序的，
reverse表示顺序是颠倒的（按照从大到小排序），
random表示随机的输入。

http://rednaxelafx.javaeye.com/upload/picture/pic/9808/e985119c-70ed-3eb1-8349-544df38f9984.jpg

http://rednaxelafx.javaeye.com/upload/picture/pic/9810/f52a965b-8688-3193-8d73-25db60841cc6.jpg

http://rednaxelafx.javaeye.com/upload/picture/pic/9812/c81beebc-e20d-31e7-9ff4-1f4aeabf3d8f.jpg

http://rednaxelafx.javaeye.com/upload/picture/pic/9814/59c5395c-808c-39d1-82c9-9b5a88785e8a.jpg

可以看到，有好几种排序算法在这个统一坐标上都看不出什么端倪（相对来说太快了……），
而selection sort则很稳定的呈现出平方级的增长。

把坐标轴重新设定一次，再看看状况如何：
（注释：
Shellsort-A采用的是Shell提出的数列，从floor(N/2)开始每次除以2；
Shellsort-B采用的是另一种数列，从floor(N/2)开始每次除以3。
Quicksort-A是采用输入数组在中间位置的元素为分隔点；
Quicksort-B是采用median-of-three为分隔点；
Quicksort-C是采用median-of-five为分隔点；
Quicksort-D是采用输入数组的实际中值为分隔点
）

http://rednaxelafx.javaeye.com/upload/picture/pic/9816/3dcb3329-6a45-3eef-870f-4ad0537c1f05.jpg

http://rednaxelafx.javaeye.com/upload/picture/pic/9818/22b6b230-b39f-3063-9bd4-19b009df854d.jpg

http://rednaxelafx.javaeye.com/upload/picture/pic/9820/4bd2e645-8c68-37a8-a74f-27677ca5a16d.jpg

http://rednaxelafx.javaeye.com/upload/picture/pic/9822/b03f5d84-fecb-3f2f-85f9-4810be660c5f.jpg

raven同学或许过段时间会把题目和代码都放出来吧。这家伙最近也是忙。

统计实验是在这样的配置上：
Pentium 4 HT 3.20GHz
1GB DDR
JRE 1.6.0 update 3
不知道为什么，无论怎么调节实验次数的参数，出来的结果都会很“抖”。
我在我的老笔记本上也跑过这个实验，就一点都不“抖”，但是比这里的图要慢多了。

P.S. 统计图是用JFreeChart画的。呼，这库我2年前用得快吐血了……源码开放，文档要卖钱，这算盘打得真是响当当的。

shawind 发表于 2008-3-21 08:08:48

多半是测试时机子上的其他程序影响了CPU的使用。关掉其他所有程序，或是多次采样使用平均值会比较准吧。

rednaxela 发表于 2008-3-21 11:05:28

这个我当然也想到了。把机器上后台运行的程序调到最精简——关了杀毒软件，拔了网线，关了SQL Server，关了spoolsv，关了IIS；能管的我都关上了。
至于采样，我在每个点用的是2000次采样取平均值，每隔50做一个采样。这不算少了……
raven同学自己才用了每个点10次的采样呢，那抖得更厉害了。

我怀疑的是，我在我的老本上测的时候，它没有HT所以得到的采样曲线很平滑；而学院的机器有HT。不知道有没有关系呢。除开HT，CPU应该没差那么多吧……都是单核的。

shawind 发表于 2008-3-21 21:42:02

原来是这样，2000次的平均，数值应该是在可信范围中了。
波动的原因说不定是因为波罗波卡超星爆发的磁暴对CPU中的电子产生了影响....

john_he 发表于 2008-3-23 22:33:04

嘛，平时就用BUBBLE多，主要是算法容易背。速度要求比较严格就用QuickSort-A……容易想嘛，不想动脑子的飘过

HT对单线程程序没影响的吧，是不是其他因素呢？例如驱动程序。

rednaxela 发表于 2008-3-24 00:25:59

JVM本身可以是在多线程模式下运行的：GC的问题。在并行收集器开启的时候，GC线程可以与用户程序一起运行（而不会总以stop-the-world的方式来进行GC）。
不过我没特别开并行收集器(-XX:+UseParallelGC)，这也不该有什么影响才对。

以后有空还是把raven的Java代码换回C来跑一次看看结果如何好了，那样不会有GC的干扰。

ravenex 发表于 2008-3-24 20:54:25

小的把源代码发在这里了 http://ravenex.javaeye.com/blog/175557
请大大们多拍砖

页: [1]

幻想森林's Archiver

[自转] 几种排序算法的性能的统计图