圖解 | 從武俠角度探究STL排序算法的奧秘
本文轉(zhuǎn)載自微信公眾號(hào)「后端研究所」，作者大白斯基。轉(zhuǎn)載本文請(qǐng)聯(lián)系后端研究所公眾號(hào)。
前言
今天來(lái)看一下STL中的sort算法的底層實(shí)現(xiàn)和代碼技巧。
眾所周知STL是借助于模板化來(lái)支撐數(shù)據(jù)結(jié)構(gòu)和算法的通用化，通用化對(duì)于C++使用者來(lái)說(shuō)已經(jīng)很驚喜了，但是如果你看看STL開(kāi)發(fā)者強(qiáng)大的陣容就意識(shí)到STL給我們帶來(lái)的驚喜絕不會(huì)止步于通用化，強(qiáng)悍的性能和效率是STL的更讓人驚艷的地方。
STL極致表現(xiàn)的背后是大牛們爐火純青的編程技藝和追求極致的工匠精神的切實(shí)體現(xiàn)。
筆者能力所限，只能踏著前人的肩膀來(lái)和大家一起看看STL中sort算法的背后究竟隱藏著什么，是不是有種《走進(jìn)科學(xué)》的既視感，讓我們開(kāi)始今天的sort算法旅程吧!
內(nèi)省式哲學(xué)
在了解sort算法的實(shí)現(xiàn)之前先來(lái)看一個(gè)概念：內(nèi)省式排序，說(shuō)實(shí)話筆者的語(yǔ)文水平確實(shí)一般，對(duì)于這個(gè)詞語(yǔ)用在排序算法上總覺(jué)得不通透，那就研究一下吧!
內(nèi)省式排序英文是Introspective Sort，其中單詞introspective是內(nèi)省型的意思，還是不太明白，繼續(xù)搜索，看一下百度百科對(duì)這個(gè)詞條的解釋：
內(nèi)省(Introspection )在心理學(xué)中，它是心理學(xué)基本研究方法之一。內(nèi)省法又稱自我觀察法。它是發(fā)生在內(nèi)部的，我們自己能夠意識(shí)到的主觀現(xiàn)象。也可以說(shuō)是對(duì)于自己的主觀經(jīng)驗(yàn)及其變化的觀察。
正因?yàn)樗闹饔^性，內(nèi)省法自古以來(lái)就成為心理學(xué)界長(zhǎng)期的爭(zhēng)論。另外內(nèi)省也可看作自我反省，也是儒家強(qiáng)調(diào)的自我思考。從這個(gè)角度說(shuō)可以應(yīng)用于計(jì)算機(jī)領(lǐng)域，如Java內(nèi)省機(jī)制和cocoa內(nèi)省機(jī)制。
好家伙，原來(lái)內(nèi)省是個(gè)心理學(xué)名詞，到這里筆者有些感覺(jué)了，內(nèi)省就是自省、自我思考、根據(jù)自己的主觀經(jīng)驗(yàn)來(lái)觀察變化做出調(diào)整，而不是把希望寄托于外界，而是自己的經(jīng)驗(yàn)和能力。
通俗點(diǎn)說(shuō)，內(nèi)省算法不挑數(shù)據(jù)集，盡量針對(duì)每種數(shù)據(jù)集都能給定對(duì)應(yīng)的處理方法，讓排序都能有時(shí)間保證。
寫(xiě)到這里，讓筆者腦海浮現(xiàn)了《倚天屠龍記》里面張無(wú)忌光明頂大戰(zhàn)六大門派的場(chǎng)景，無(wú)論敵人多么強(qiáng)悍或者羸弱，我都按照自己的路子應(yīng)對(duì)。
他強(qiáng)由他強(qiáng)，清風(fēng)拂山崗;
他橫由他橫，明月照大江;
他自狠來(lái)他自惡，我自一口真氣足。
---《九陽(yáng)真經(jīng)》達(dá)摩
哲學(xué)啊，確實(shí)這樣的，我們切換到排序的角度來(lái)看看內(nèi)省是怎么樣的過(guò)程。
筆者理解的內(nèi)省式排序算法就是不依賴于外界數(shù)據(jù)的好壞多寡，而是根據(jù)自己針對(duì)每種極端場(chǎng)景下做出相應(yīng)的判斷和決策調(diào)整，從而來(lái)適應(yīng)多種數(shù)據(jù)集合展現(xiàn)出色的性能。
內(nèi)省式排序
俗話說(shuō)俠者講究刀、槍、劍、戟、斧、鉞、鉤、叉等諸多兵器，這也告訴我們一個(gè)道理沒(méi)有哪種兵器是無(wú)敵的，只有在某些場(chǎng)景下的明顯優(yōu)勢(shì)，這跟軟件工程沒(méi)有銀彈是一樣的。
回到我們的排序算法上，排序算法也可謂是百花齊放：冒泡排序、選擇排序、插入排序、快速排序、堆排序、桶排序等等。
雖然一批老一輩的排序算法是O(n^2)的，優(yōu)秀的算法可以到達(dá)O(nlogn)，但是即使都是nlogn的快速排序和堆排序都有各自的長(zhǎng)短之處，插入排序在數(shù)據(jù)幾乎有序的場(chǎng)景下性能可以到達(dá)O(n)，有時(shí)候我們應(yīng)該做的不是沖突對(duì)比而是融合創(chuàng)新。
內(nèi)省排序是由David Musser在1997年設(shè)計(jì)的排序算法。這個(gè)排序算法首先從快速排序開(kāi)始，當(dāng)遞歸深度超過(guò)一定深度(深度為排序元素?cái)?shù)量的對(duì)數(shù)值)后轉(zhuǎn)為堆排序,David Musser大牛是STL領(lǐng)域響當(dāng)當(dāng)?shù)娜宋铩?/p>
拋開(kāi)語(yǔ)境一味地對(duì)比孰好孰壞其實(shí)都沒(méi)有意義，內(nèi)省式排序就是集大成者，為了能讓排序算法達(dá)到一個(gè)綜合的優(yōu)異性能，內(nèi)省式排序算法結(jié)合了快速排序、堆排序、插入排序，并根據(jù)當(dāng)前數(shù)據(jù)集的特點(diǎn)來(lái)選擇使用哪種排序算法，讓每種算法都展示自己的長(zhǎng)處，這種思想確實(shí)挺啟發(fā)人的。
內(nèi)省排序的排兵布陣
前面提到了內(nèi)省式排序主要結(jié)合了快速排序、堆排序、插入排序，那么不禁要問(wèn)，這三種排序是怎么排兵布陣的呢?
知己知彼百戰(zhàn)不殆，所以先看下三種排序的優(yōu)缺點(diǎn)吧!
快速排序
在大量數(shù)據(jù)時(shí)無(wú)論是有序還是重復(fù)，使用優(yōu)化后的算法大多可以到達(dá)O(nlogn)，雖然堆排序也是O(nlogn)但是由于某些原因快速排序會(huì)更快一些，當(dāng)遞歸過(guò)深分割嚴(yán)重不均勻情況出現(xiàn)時(shí)會(huì)退化為O(n^2)的復(fù)雜度，這時(shí)性能會(huì)打折扣，這也就是快速排序的短處了。
堆排序
堆排序是快速排序的有力競(jìng)爭(zhēng)者，最大的特點(diǎn)是可以到達(dá)O(nlogn)并且復(fù)雜度很穩(wěn)定，并不會(huì)像快速排序一樣可能退化為O(n^2)，但是堆排序過(guò)程中涉及大量堆化調(diào)整，并且元素比較是跳著來(lái)的對(duì)Cache的局部性特征利用不好，以及一些其他的原因?qū)е露雅判虮瓤焖倥判蚋稽c(diǎn)，但是大O復(fù)雜度仍然是一個(gè)級(jí)別的。
插入排序
插入排序的一個(gè)特點(diǎn)是就像我們玩紙牌，在梳理手中的牌時(shí)，如果已經(jīng)比較有序了，那么只需要做非常少的調(diào)整即可，因此插入排序在數(shù)據(jù)量不大且近乎有序的情況下復(fù)雜度可以降低到O(n)，這一點(diǎn)值得被應(yīng)用。
優(yōu)缺點(diǎn)也大致清楚了，所以可以猜想一下內(nèi)省式排序在實(shí)際中是如何調(diào)度使這三種排序算法的：
- 啟動(dòng)階段 面對(duì)大量的待排序元素，首先使用快速排序進(jìn)行大刀闊斧排序，復(fù)雜度可以在O(nlogn)運(yùn)行
- 深入階段 在快速排序使用遞歸過(guò)程中，涉及棧幀保存切換等諸多遞歸的操作，如果分區(qū)切割不當(dāng)遞歸過(guò)深可能造成棧溢出程序終止，因此如果快速排序過(guò)程中退化為O(n^2)，此時(shí)會(huì)自動(dòng)檢測(cè)切換為堆排序，因?yàn)槎雅判驔](méi)有惡化情況，都可以穩(wěn)定在O(nlogn)
- 收尾階段 在經(jīng)過(guò)快排和堆排的處理之后，數(shù)據(jù)分片的待排序元素?cái)?shù)量小于某個(gè)經(jīng)驗(yàn)設(shè)定值(可以認(rèn)為是遞歸即將結(jié)束的前幾步調(diào)用)時(shí)，數(shù)據(jù)其實(shí)已經(jīng)幾乎有序，此時(shí)就可以使用插入排序來(lái)提高效率，將復(fù)雜度進(jìn)一步降低為O(n)。
寫(xiě)到這里，筆者又天馬行空地想到了一個(gè)場(chǎng)景：
2005年春晚小品中黃宏和鞏漢林出演的《裝修》中黃宏作為裝修工人手拿一大一小兩把錘子，大錘80小錘40，大小錘頭切換使用。
其實(shí)跟內(nèi)省排序切換排序算法是一個(gè)道理，所以技術(shù)源于生活又高于生活，貼圖一張大家一起體會(huì)一下：
用了很多篇幅來(lái)講內(nèi)省思想和內(nèi)省式排序，相信大家也已經(jīng)get到了，所以我們具體看下實(shí)現(xiàn)細(xì)節(jié)，這個(gè)才是本文的重點(diǎn)，我們繼續(xù)往下一起分析吧!
sort算法的實(shí)現(xiàn)細(xì)節(jié)
本文介紹的sort算法是基于SGI STL版本的，并且主要是以侯捷老師的《STL源碼剖析》一書(shū)為藍(lán)本來(lái)進(jìn)行展開(kāi)的，因此使用了不帶仿函數(shù)的版本，讓我們來(lái)一起領(lǐng)略大牛們的杰作吧!圖為筆者買了很久卻一直壓箱底的STL神書(shū)：
sort函數(shù)的應(yīng)用場(chǎng)景
SGI STL中的sort的參數(shù)是兩個(gè)隨機(jī)存取迭代器RandomAccessIterator，sort的模板也是基于此種迭代器的，因此如果容器不是隨機(jī)存取迭代器，那么可能無(wú)法使用通用的sort函數(shù)。
- 關(guān)聯(lián)容器 map和set底層是基于RB-Tree，本身就已經(jīng)自帶順序了，因此不需要使用sort算法
- 序列容器 list是雙向迭代器并不是隨機(jī)存取迭代器，vector和deque是隨機(jī)存取迭代器適用于sort算法
- 容器適配器 stack、queue和priority-queue屬于限制元素順序的容器，因此不適用sort算法。
綜上我們可以知道，sort算法可以很好的適用于vector和deque這兩種容器。
sort總體概覽
前面介紹了內(nèi)省式排序，所以看下sort是怎么一步步來(lái)使用introsort的，上一段入口代碼：
- template <class RandomAccessIterator>
- inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
- if (first != last) {
- __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
- __final_insertion_sort(first, last);
- }
- }
從代碼來(lái)看sort使用了first和last兩個(gè)隨機(jī)存取迭代器，作為待排序序列的開(kāi)始和終止，進(jìn)一步調(diào)用了__introsort_loop和__final_insertion_sort兩個(gè)函數(shù)，從字面上看前者是內(nèi)省排序循環(huán)，后者是插入排序。其中注意到__introsort_loop的第三個(gè)參數(shù)__lg(last - first)*2，憑借我們的經(jīng)驗(yàn)來(lái)猜(蒙)一下吧，應(yīng)該遞歸深度的限制，不急看下代碼實(shí)現(xiàn)：
- template <class Size>
- inline Size __lg(Size n){
- Size k;
- for(k = 0;n > 1;n >>= 1) ++k;
- return k;
- }
這段代碼的意思就是n=last-first，2^k<=n的最大整數(shù)k值。
所以整體看當(dāng)假設(shè)last-first=20時(shí)，k=4,最大分割深度depth_max=4*2=8，從而我們就可以根據(jù)first和last來(lái)確定遞歸的最大深度了。
快速排序和堆排序的配合 __introsort_loop函數(shù)中主要封裝了快速排序和堆排序，來(lái)看看這個(gè)函數(shù)的實(shí)現(xiàn)細(xì)節(jié)：
- //sort函數(shù)的入口
- template <class RandomAccessIterator, class T, class Size>
- void __introsort_loop(RandomAccessIterator first,
- RandomAccessIterator last, T*,
- Size depth_limit) {
- while (last - first > __stl_threshold) {
- if (depth_limit == 0) {
- partial_sort(first, last, last);//使用堆排序
- return;
- }
- --depth_limit;//減分割余額
- RandomAccessIterator cut = __unguarded_partition
- (first, last, T(__median(*first, *(first + (last - first)/2),
- *(last - 1))));//三點(diǎn)中值法分區(qū)過(guò)程
- __introsort_loop(cut, last, value_type(first), depth_limit);//子序列遞歸調(diào)用
- last = cut;//迭代器交換 切換到左序列
- }
- }
- //基于三點(diǎn)中值法的分區(qū)算法
- template <class RandomAccessIterator, class T>
- RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
- RandomAccessIterator last,
- T pivot) {
- while (true) {
- while (*first < pivot) ++first;
- --last;
- while (pivot < *last) --last;
- if (!(first < last)) return first;
- iter_swap(first, last);
- ++first;
- }
各位先不要暈更不要蒙圈，一點(diǎn)點(diǎn)分析肯定可以拿下的。
- 先看參數(shù)兩個(gè)隨機(jī)存取迭代器first和last，第三個(gè)參數(shù)是__lg計(jì)算得到的分割深度;
- 這時(shí)候我們進(jìn)入了while判斷了last-first的區(qū)間大小，__stl_threshold為16，侯捷大大特別指出__stl_threshold的大小可以是5~20，具體大小可以自己設(shè)置，如果大于__stl_threshold那就才會(huì)繼續(xù)執(zhí)行，否則跳出;假如現(xiàn)在區(qū)間大小大于__stl_threshold，判斷第三個(gè)參數(shù)depth_limit是否為0，也就是是否出現(xiàn)了分割過(guò)深的情況，相當(dāng)于給了一個(gè)初始最大值，然后每分割一次就減1，直到depth_limit=0，這時(shí)候調(diào)用partial_sort，從《stl源碼剖析》的其他章節(jié)可以知道，partial_sort就是對(duì)堆排序的封裝，看到這里有點(diǎn)意思了主角之一的heapsort出現(xiàn)了;
- 繼續(xù)往下看，depth_limit>0 尚有分割余額，那就燥起來(lái)吧!這樣來(lái)到了__unguarded_partition，這個(gè)函數(shù)從字眼看是快速排序的partiton過(guò)程，返回了cut隨機(jī)存取迭代器，__unguarded_partition的第三個(gè)參數(shù)__median使用的是三點(diǎn)中值法來(lái)獲取的基準(zhǔn)值Pivot，至此快速排序的partition的三個(gè)元素集齊了，最后返回新的切割點(diǎn)位置;
- 繼續(xù)看馬上搞定啦，__introsort_loop出現(xiàn)了，果然遞歸了，特別注意一下這里只有一個(gè)遞歸，并且傳入的是cut和last，相當(dāng)于右子序列，那左子序列怎么辦啊?別急往下看，last=cut峰回路轉(zhuǎn)cut變成了左子序列的右邊界，這樣就開(kāi)始了左子序列的處理;
快速排序的實(shí)現(xiàn)對(duì)比
前面提到了在sort中快速排序的寫(xiě)法和我們之前見(jiàn)到的有一些區(qū)別，看了一下《STL源碼剖析》對(duì)快排左序列的處理，侯捷老師是這么寫(xiě)的："寫(xiě)法可讀性較差，效率并沒(méi)有比較好"，看到這里更蒙圈了，不過(guò)也試著分析一下吧!
圖為：STL源碼剖析中侯捷老師對(duì)該種寫(xiě)法的注釋
常見(jiàn)寫(xiě)法：
- //快速排序的常見(jiàn)寫(xiě)法偽代碼
- quicksort(arr,left,right){
- pivoit = func(arr);//使用某種方法獲取基準(zhǔn)值
- cut = partition(left,right,pivot);//左右邊界和基準(zhǔn)值來(lái)共同確定分割點(diǎn)位置
- quicksort(arr,left,cut-1);//遞歸處理左序列
- quicksort(arr,cut+1,right);//遞歸處理右序列
- }
SGI STL中的寫(xiě)法:
- stl_quicksort(first,last){
- //循環(huán)作為外層控制結(jié)構(gòu)
- while(ok){
- cut = stl_partition(first,last,_median(first,last));//分割分區(qū)
- stl_quicksort(cut,last);//遞歸調(diào)用 處理右子序列
- last = cut;//cut賦值為last 相當(dāng)于切換到左子序列 再繼續(xù)循環(huán)
- }
- }
網(wǎng)上有一些大佬的文章說(shuō)sgi stl中快排的寫(xiě)法左序列的調(diào)用借助了while循環(huán)節(jié)省了一半的遞歸調(diào)用，是典型的尾遞歸優(yōu)化思路。
這里我暫時(shí)還沒(méi)有寫(xiě)測(cè)試代碼做對(duì)比，先占坑后續(xù)寫(xiě)個(gè)對(duì)比試驗(yàn)，再來(lái)評(píng)論吧，不過(guò)這種sgi的這種寫(xiě)法可以看看哈。
堆排序的細(xì)節(jié)
- //注：這個(gè)是帶自定義比較函數(shù)的堆排序版本
- //堆化和堆頂操作
- template <class RandomAccessIterator, class T, class Compare>
- void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
- RandomAccessIterator last, T*, Compare comp) {
- make_heap(first, middle, comp);
- for (RandomAccessIterator i = middle; i < last; ++i)
- if (comp(*i, *first))
- __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
- sort_heap(first, middle, comp);
- }
- //堆排序的入口
- template <class RandomAccessIterator, class Compare>
- inline void partial_sort(RandomAccessIterator first,
- RandomAccessIterator middle,
- RandomAccessIterator last, Compare comp) {
- __partial_sort(first, middle, last, value_type(first), comp);
- }
插入排序上場(chǎng)了
__introsort_loop達(dá)到__stl_threshold閾值之后，可以認(rèn)為數(shù)據(jù)集近乎有序了，此時(shí)就可以通過(guò)插入排序來(lái)進(jìn)一步提高排序速度了，這樣也避免了遞歸帶來(lái)的系統(tǒng)消耗，看下__final_insertion_sort的具體實(shí)現(xiàn)：
- template <class RandomAccessIterator>
- void __final_insertion_sort(RandomAccessIterator first,
- RandomAccessIterator last) {
- if (last - first > __stl_threshold) {
- __insertion_sort(first, first + __stl_threshold);
- __unguarded_insertion_sort(first + __stl_threshold, last);
- }
- else
- __insertion_sort(first, last);
- }
來(lái)分析一下__final_insertion_sort的實(shí)現(xiàn)細(xì)節(jié)吧:
- 引入?yún)?shù)隨機(jī)存取迭代器first和last
- 如果last-first > __stl_threshold不成立就調(diào)用__insertion_sort，這個(gè)相當(dāng)于元素?cái)?shù)比較少了可以直接調(diào)用，不用做特殊處理;
- 如果last-first > __stl_threshold成立就進(jìn)一步再分割成兩部分，分別調(diào)用__insertion_sort和__unguarded_insertion_sort，兩部分的分割點(diǎn)是__stl_threshold，不免要問(wèn)這倆函數(shù)有啥區(qū)別呀?
__insertion_sort的實(shí)現(xiàn)
- //逆序?qū)Φ恼{(diào)整
- template <class RandomAccessIterator, class T>
- void __unguarded_linear_insert(RandomAccessIterator last, T value) {
- RandomAccessIterator next = last;
- --next;
- while (value < *next) {
- *last = *next;
- last = next;
- --next;
- }
- *last = value;
- }
- template <class RandomAccessIterator, class T>
- inline void __linear_insert(RandomAccessIterator first,
- RandomAccessIterator last, T*) {
- T value = *last;
- if (value < *first) {
- copy_backward(first, last, last + 1);//區(qū)間移動(dòng)
- *first = value;
- }
- else
- __unguarded_linear_insert(last, value);
- }
- //__insertion_sort入口
- template <class RandomAccessIterator>
- void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
- if (first == last) return;
- for (RandomAccessIterator i = first + 1; i != last; ++i)
- __linear_insert(first, i, value_type(first));
- }
在插入函數(shù)中同樣出現(xiàn)了__unguarded_xxx這種形式的函數(shù)，unguarded單詞的意思是無(wú)防備的，無(wú)保護(hù)的，侯捷大大提到這種函數(shù)形式是特定條件下免去邊界檢驗(yàn)條件也能正確運(yùn)行的函數(shù)。
copy_backward也是一種整體移動(dòng)的優(yōu)化，避免了one by one的調(diào)整移動(dòng)，底層調(diào)用memmove來(lái)高效實(shí)現(xiàn)。
__unguarded_insertion_sort的實(shí)現(xiàn)
- template <class RandomAccessIterator, class T>
- void __unguarded_insertion_sort_aux(RandomAccessIterator first,
- RandomAccessIterator last, T*) {
- for (RandomAccessIterator i = first; i != last; ++i)
- __unguarded_linear_insert(i, T(*i));
- }
- template <class RandomAccessIterator>
- inline void __unguarded_insertion_sort(RandomAccessIterator first,
- RandomAccessIterator last) {
- __unguarded_insertion_sort_aux(first, last, value_type(first));
- }
關(guān)于插入排序的這兩個(gè)函數(shù)的實(shí)現(xiàn)和目的用途，展開(kāi)起來(lái)會(huì)很細(xì)致，所以后面想著單獨(dú)在寫(xiě)插入排序時(shí)單獨(dú)拿出了詳細(xì)學(xué)習(xí)一下，所以本文就暫時(shí)先不深究了，感興趣的讀者可以先行閱讀相關(guān)資料，后續(xù)我們?cè)俟餐q駁哈!
總結(jié)
本文主要闡述了內(nèi)省式排序的思想和基本實(shí)現(xiàn)思路，并且以此為切入點(diǎn)對(duì)sgi stl中sort算法的實(shí)現(xiàn)來(lái)進(jìn)行了一些解讀。
stl的作者們?yōu)榱俗非髽O致性能所以使用了大量的技巧，對(duì)此本文并沒(méi)有過(guò)多展開(kāi)，也主要是段位不太高怕解讀錯(cuò)了，聰明的讀者們可以嘗試來(lái)剖析一探大牛們的巔峰技藝。
