免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: sublx

[函数] 请教大家一个关于快速排序的问题。 [复制链接]

论坛徽章:
1
天蝎座
日期:2013-12-06 18:23:58
发表于 2012-12-10 23:18 |显示全部楼层
回复 10# sublx


    inpput size:1000000
input times:6
t1 = 0.23seconds
t2 = 0.2seconds
two arrays is the same.diff = -30000
t1 = 0.23seconds
t2 = 0.2seconds
two arrays is the same.diff = -30000
t1 = 0.24seconds
t2 = 0.19seconds
two arrays is the same.diff = -50000
t1 = 0.23seconds
t2 = 0.2seconds
two arrays is the same.diff = -30000
t1 = 0.24seconds
t2 = 0.19seconds
two arrays is the same.diff = -50000


还是qsort快点撒,就单从你写的是递归的,性能也要打点折扣呐

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 23:27 |显示全部楼层
回复 21# crazyhadoop

我察!难道是我用VS2008的问题?你是用我贴的代码吗?我刚在linux下运行了下,好像两个比较接近了。
  1. [root@bogon _ping]# vim test.cpp
  2. [root@bogon _ping]# gcc -lstdc++ -o t test.cpp
  3. [root@bogon _ping]# ./t
  4. inpput size:1000000
  5. input times:5
  6. t1 = 0.23seconds
  7. t2 = 0.46seconds
  8. two arrays is the same.diff = 230000
  9. t1 = 0.63seconds
  10. t2 = 0.97seconds
  11. two arrays is the same.diff = 340000
  12. t1 = 0.74seconds
  13. t2 = 1.15seconds
  14. two arrays is the same.diff = 410000
  15. t1 = 0.79seconds
  16. t2 = 1.33seconds
  17. two arrays is the same.diff = 540000
复制代码

论坛徽章:
1
天蝎座
日期:2013-12-06 18:23:58
发表于 2012-12-10 23:32 |显示全部楼层
回复 22# sublx


    是滴,你没看错字都一样么

论坛徽章:
0
发表于 2012-12-10 23:33 |显示全部楼层
回复 20# sublx

别拿 Debug 库测性能……尤其是 VS 的……

论坛徽章:
1
天蝎座
日期:2013-12-06 18:23:58
发表于 2012-12-10 23:34 |显示全部楼层
还有你能用g++ 编译么~

论坛徽章:
0
发表于 2012-12-10 23:36 |显示全部楼层
回复 21# crazyhadoop

忘记开优化了吧?

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 23:43 |显示全部楼层
回复 23# crazyhadoop

让你见笑了^_^。我写了个非递归的,怎么比递归的还慢?
  1. void x_qsort(int *array, int low, int high)
  2. {
  3.         if (low < high)
  4.         {
  5.                 queue<int> q;
  6.                 q.push(low);
  7.                 q.push(high);
  8.                 while(!q.empty())
  9.                 {
  10.                         int low = q.front();
  11.                         q.pop();
  12.                         int high = q.front();
  13.                         q.pop();
  14.                         if (low < high)
  15.                         {
  16.                                 int p = partition(array, low, high);
  17.                                 q.push(low);
  18.                                 q.push(p - 1);
  19.                                 q.push(p + 1);
  20.                                 q.push(high);
  21.                         }
  22.                 }
  23.         }
  24. }
复制代码
[root@bogon _ping]# ./t
inpput size:1000000
input times:5
t1 = 1.17seconds
t2 = 0.83seconds
two arrays is the same.diff = -340000
t1 = 1.22seconds
t2 = 1.02seconds
two arrays is the same.diff = -200000
t1 = 1.29seconds
t2 = 1.1seconds
two arrays is the same.diff = -190000
t1 = 1.37seconds
t2 = 1.25seconds
two arrays is the same.diff = -120000



   

论坛徽章:
1
天蝎座
日期:2013-12-06 18:23:58
发表于 2012-12-10 23:47 |显示全部楼层

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 23:48 |显示全部楼层
回复 25# crazyhadoop

g++ -o1 -lstdc++ -o t test.cpp
gcc -o1 -lstdc++ -o t test.cpp


这两个方式都编译过,好像结果跟没加优化结果一样,o1是不是最高级别的优化了?我忘记了。

   

论坛徽章:
1
2015年亚洲杯之巴林
日期:2015-02-05 20:34:47
发表于 2012-12-10 23:51 |显示全部楼层
回复 28# crazyhadoop

原来qsort可以写得这么复杂,受教了,谢谢!


   
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP