你还在这样写快排?

/ 2评 / 0

排序永远是数据结构里永恒的话题,快排、归并排序这样基于分治思想排序的提出,极大的优化了插入排序、冒泡排序这样的O(N^2)排序算法。对于这样基于分治思想的排序,都可以写成多线程算法,但在C/C++下,很少有人把快排写成多线程,因为就pthread线程库来说其实现是与内核线程1:1的模型,一方面创建与调度开销并不小,另一方面用于其线程间同步的POSIX 信号量开销也并不小,且非常不方便。但在go里就完全不一样了,N:N协程不仅开销小且调度做的非常轻便,最重要的是同步起来非常方便。


下面我们来研究一下一个合适的多线(协)程快排到底比普通的快排快了多少

机器:16GDDR4 8核i7-6700HQ

先看看常规快排的性能,我们生成一千万个随机数与一亿个随机数,分别测试三组,记录每组时间(忽略每次随机产生的源数据之间的固有差异带来的影响)

image.png

三组测试结果如下

一千万随机数 一亿随机数
第一组 1.287144 s 14.45144 s
第二组 1.264827 s 14.53373 s
第三组 1.254869 s 14.28627 s

快排的稳定性当然是没有问题的,速度当然也还算可以的,下面我们开始充分利用我们的8核CPU,看看到底多线(协)程快排比常规快排快了多少。

多线(协)程快排思路:每次分治问题完成必须是其下两个子问题的完成,因此每次子问题完成应通过chan通知父问题,父问题在两个子问题都完成后才可通过chan通知上一级祖先(爷爷)问题

image.png

我们来测一把

一千万随机数 一亿随机数
第一组 6.5759626 s oom
第二组 6.4370456 s oom
第三组 7.0409691 s oom

非常尴尬,这时不仅一千万随机数的速度比普通的快排还慢了七八倍,一亿随机数更是直接内存溢出了。

事实上这是很多人对于多线(协)程的应用场景理解不到位时会犯的错误,并不是多线(协)程一定就性能高,这之间的权衡就是:处理这个问题如果我用多线(协)程,带来的速度提升程度是否远远大于线(协)程调度本身的开销,如果确实远远大于,那么就适合用多线(协)程来充分利用多核。

分析一下我们到底哪里存在调度的消耗会大于问题本身的耗时,不难意识到,但分治后的子问题区间只剩下少量数的时候,这是如果仍然起协程去处理分治的子问题就不合适了,因此完全可以在区间小于某一阈值时使用普通的快排去完成剩下的工作

image.png

再来测一把(10000作为阈值时经过测试后,选取的一个还算不错的平衡点,再增大会导致速度下降)

一千万随机数 一亿随机数
第一组 0.262879 s 3.161468 s
第二组 0.272799 s 3.237872 s
第三组 0.280205 s 3.253718 s

可以看到,非常快,比普通的快排提高了四倍的速度,肯定你会关心内存的消耗如何呢,答案多线(协)程快排是和普通快排几乎一样,这当然是得益于go协程的轻量与良好的设计。

以后把你的快排写成多线(协)程把!

  1. KKK说道:

    快排不是不稳定么,有相同大小元素的时候会打断已经排好的顺序

发表评论

电子邮件地址不会被公开。 必填项已用*标注