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