12.25 理解 STL 的 Sort 算法

前言

今天來看一下STL中的sort算法的

底層實現和代碼技巧

眾所周知STL是藉助於模板化來支撐數據結構和算法的 通用化 ,通用化對於C++使用者來說已經很驚喜了,但是如果你看看STL開發者強大的陣容就意識到STL給我們帶來的驚喜絕不會止步於通用化, 強悍的性能和效率 是STL的更讓人驚豔的地方。

STL極致表現的背後是大牛們 爐火純青的編程技藝和追求極致的工匠精神 的切實體現。筆者能力所限,只能踏著前人的肩膀來和大家一起看看STL中sort算法的背後究竟隱藏著什麼,是不是有種《走進科學》的既視感,讓我們開始今天的sort算法旅程吧!

內省式哲學

在瞭解sort算法的實現之前先來看一個概念: 內省式排序 ,說實話筆者的語文水平確實一般,對於 這個詞語用在排序算法上總覺得不通透 ,那就研究一下吧!

內省式排序英文是 Introspective Sort ,其中單詞introspective是內省型的意思,還是不太明白,繼續搜索,看一下百度百科對這個詞條的解釋:

內省(Introspection )在心理學中,它是心理學基本研究方法之一。內省法又稱自我觀察法。它是發生在內部的,我們自己能夠意識到的主觀現象。也可以說是對於自己的主觀經驗及其變化的觀察。正因為它的主觀性,內省法自古以來就成為心理學界長期的爭論。另外內省也可看作自我反省,也是儒家強調的自我思考。從這個角度說可以應用於計算機領域,如Java內省機制和cocoa內省機制。

From 百度百科-內省-科普中國審核通過詞條

好傢伙,原來內省是個 心理學名詞 ,到這裡筆者有些感覺了,內省就是自省、自我思考、根據自己的主觀經驗來觀察變化做出調整,而不是把希望寄託於外界,而是自己的經驗和能力。

通俗點說,內省算法不挑數據集,儘量針對每種數據集都能給定對應的處理方法,讓排序都能有時間保證。寫到這裡,讓筆者腦海浮現了《 倚天屠龍記 》裡面張無忌光明頂大戰六大門派的場景,無論敵人多麼強悍或者羸弱,我都按照自己的路子應對。

他強由他強,清風拂山崗;

他橫由他橫,明月照大江;

他自狠來他自惡,我自一口真氣足。

---《九陽真經》達摩

哲學啊,確實這樣的,我們切換到排序的角度來看看內省是怎麼樣的過程。筆者理解的 內省式排序算法就是不依賴於外界數據的好壞多寡,而是根據自己針對每種極端場景下做出相應的判斷和決策調整,從而來適應多種數據集合展現出色的性能 。

內省式排序

俗話說俠者講究刀、槍、劍、戟、斧、鉞、鉤、叉等諸多兵器,這也告訴我們一個道理沒有哪種兵器是無敵的,只有在某些場景下的明顯優勢,這跟 軟件工程沒有銀彈 是一樣的。

回到我們的排序算法上,排序算法也可謂是 百花齊放 :冒泡排序、選擇排序、插入排序、快速排序、堆排序、桶排序等等。

雖然一批老一輩的排序算法是O(n^2)的,優秀的算法可以到達O(nlogn),但是即使都是nlogn的快速排序和堆排序都有各自的長短之處,插入排序在數據幾乎有序的場景下性能可以到達O(n),有時候我們應該做的 不是衝突對比而是融合創新 。

內省排序是由 David Musser 在1997年設計的排序算法。這個排序算法首先從快速排序開始,當遞歸深度超過一定深度(深度為排序元素數量的對數值)後轉為堆排序,David Musser大牛是STL領域響噹噹的人物。

理解 STL 的 Sort 算法

拋開語境一味地對比孰好孰壞其實都沒有意義,內省式排序就是 集大成者 ,為了能讓排序算法達到一個綜合的優異性能,內省式排序算法結合了快速排序、堆排序、插入排序,並根據當前數據集的特點來選擇使用哪種排序算法,讓每種算法都展示自己的長處,這種思想確實挺啟發人的。

理解 STL 的 Sort 算法

內省排序的排兵佈陣

前面提到了內省式排序主要結合了快速排序、堆排序、插入排序,那麼不禁要問,這三種排序是怎麼排兵佈陣的呢?知己知彼百戰不殆,所以先看下三種排序的 優缺點 吧!

  • 快速排序在大量數據時無論是有序還是重複,使用優化後的算法大多可以到達O(nlogn),雖然堆排序也是O(nlogn)但是由於某些原因快速排序會更快一些,當遞歸過深分割嚴重不均勻情況出現時會 退化為 O(n^2) 的複雜度,這時性能會打折扣,這也就是快速排序的短處了。
  • 堆排序堆排序是快速排序的有力競爭者,最大的特點是可以到達O(nlogn)並且複雜度很穩定,並不會像快速排序一樣可能退化為O(n^2),但是堆排序過程中涉及 大量堆化 調整,並且元素比較是跳著來的對 Cache的局部性特徵 利用不好,以及一些其他的原因導致堆排序比快速排序更慢一點,但是大O複雜度仍然是一個級別的。
  • 插入排序插入排序的一個特點是就像我們玩紙牌,在梳理手中的牌時,如果已經比較有序了,那麼只需要做非常少的調整即可,因此插入排序在數據量不大且近乎有序的情況下複雜度可以降低到 O(n) ,這一點值得被應用。

優缺點也大致清楚了,所以可以猜想一下內省式排序在實際中是 如何調度 使這三種排序算法的:

  • 啟動階段 面對大量的待排序元素,首先使用快速排序進行 大刀闊斧 排序,複雜度可以在O(nlogn)運行
  • 深入階段 在快速排序使用遞歸過程中,涉及棧幀保存切換等諸多遞歸的操作,如果分區切割不當遞歸過深可能造成棧溢出程序終止,因此如果快速排序過程中 退化 為O(n^2),此時會自動檢測切換為堆排序,因為堆排序沒有惡化情況,都可以穩定在O(nlogn)
  • 收尾階段 在經過快排和堆排的處理之後,數據分片的待排序元素數量小於某個經驗設定值(可以認為是遞歸即將結束的前幾步調用)時,數據其實已經幾乎有序,此時就可以使用插入排序來提高效率,將複雜度進一步降低為 O(n)
理解 STL 的 Sort 算法

寫到這裡,筆者又天馬行空地想到了一個場景:

2005年春晚小品中黃宏和鞏漢林出演的《裝修》中黃宏作為裝修工人手拿一大一小兩把錘子,大錘80小錘40,大小錘頭切換使用。

其實跟內省排序切換排序算法是一個道理,所以 技術源於生活又高於生活 ,貼圖一張大家一起體會一下:

理解 STL 的 Sort 算法

用了很多篇幅來講內省思想和內省式排序,相信大家也已經get到了,所以我們具體看下實現細節,這個才是本文的重點,我們繼續往下一起分析吧!

sort算法的實現細節

本文介紹的sort算法是基於SGI STL版本的,並且主要是以侯捷老師的《STL源碼剖析》一書為藍本來進行展開的,因此使用了不帶仿函數的版本,讓我們來一起領略大牛們的傑作吧! 圖為筆者買了很久卻一直壓箱底的STL神書:

理解 STL 的 Sort 算法

sort函數的應用場景

SGI STL中的sort的參數是兩個 隨機存取迭代器RandomAccessIterator ,sort的模板也是基於此種迭代器的,因此如果容器不是隨機存取迭代器,那麼可能無法使用通用的sort函數。

  • 關聯容器 map和set底層是基於RB-Tree,本身就已經自帶順序了,因此不需要使用sort算法
  • 序列容器 list是雙向迭代器並不是隨機存取迭代器,vector和deque是隨機存取迭代器適用於sort算法
  • 容器適配器 stack、queue和priority-queue屬於限制元素順序的容器,因此不適用sort算法。

綜上我們可以知道,sort算法可以很好的適用於vector和deque這兩種容器。

sort總體概覽

前面介紹了內省式排序,所以看下sort是怎麼一步步來使用introsort的,上一段入口代碼:

<code>template <class>
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);
}
}
/<class>/<code>

從代碼來看sort使用了first和last兩個隨機存取迭代器,作為待排序序列的開始和終止,進一步調用了__introsort_loop和__final_insertion_sort兩個函數,從字面上看前者是內省排序循環,後者是插入排序。其中注意到__introsort_loop的第三個參數 __lg(last - first)*2 ,憑藉我們的經驗來猜(蒙)一下吧,應該遞歸深度的限制,不急看下代碼實現:

<code>template <class>
inline Size __lg(Size n){
Size k;
for(k = 0;n > 1;n >>= 1) ++k;
return k;
}
/<class>/<code>

這段代碼的意思就是n=last-first,2^k<=n的最大整數k值。

所以整體看當假設last-first=20時,k=4,最大分割深度depth_max=4*2=8,從而我們就可以根據first和last來確定遞歸的最大深度了。

快速排序和堆排序的配合

__introsort_loop 函數中主要 封裝了快速排序和堆排序 ,來看看這個函數的實現細節:

<code>//sort函數的入口
template <class>
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))));//三點中值法分區過程
__introsort_loop(cut, last, value_type(first), depth_limit);//子序列遞歸調用
last = cut;//迭代器交換 切換到左序列
}
}

//基於三點中值法的分區算法
template <class>
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;
}
/<class>/<class>/<code>

各位先不要暈更不要蒙圈, 一點點分析肯定可以拿下的

  • 先看 參數兩個隨機存取迭代器first和last,第三個參數是__lg計算得到的分割深度;
  • 這時候 我們進入了while判斷了last-first的區間大小,__stl_threshold為16,侯捷大大特別指出__stl_threshold的大小可以是5~20,具體大小可以自己設置,如果大於__stl_threshold那就才會繼續執行,否則跳出;
  • 假如 現在區間大小大於__stl_threshold,判斷第三個參數depth_limit是否為0,也就是是否出現了分割過深的情況,相當於給了一個初始最大值,然後每分割一次就減1,直到depth_limit=0,這時候調用partial_sort,從《stl源碼剖析》的其他章節可以知道,partial_sort就是對堆排序的封裝,看到這裡有點意思了主角之一的heapsort出現了;
  • 繼續往下看 ,depth_limit>0 尚有分割餘額,那就燥起來吧!這樣來到了__unguarded_partition,這個函數從字眼看是快速排序的partiton過程,返回了cut隨機存取迭代器,__unguarded_partition的第三個參數__median使用的是三點中值法來獲取的基準值Pivot,至此快速排序的partition的三個元素集齊了,最後返回新的切割點位置;
  • 繼續看 馬上搞定啦 ,__introsort_loop出現了,果然遞歸了,特別注意一下這裡只有一個遞歸,並且傳入的是cut和last,相當於右子序列,那左子序列怎麼辦啊?別急往下看,last=cut峰迴路轉cut變成了左子序列的右邊界,這樣就開始了左子序列的處理;

快速排序的實現對比

前面提到了在sort中快速排序的寫法和我們之前見到的有一些區別,看了一下《STL源碼剖析》對快排左序列的處理,侯捷老師是這麼寫的:"寫法可讀性較差,效率並沒有比較好",看到這裡更蒙圈了,不過也試著分析一下吧!

圖為: STL源碼剖析中侯捷老師對該種寫法的註釋

理解 STL 的 Sort 算法

常見寫法:

<code>//快速排序的常見寫法偽代碼
quicksort(arr,left,right){
pivoit = func(arr);//使用某種方法獲取基準值
cut = partition(left,right,pivot);//左右邊界和基準值來共同確定分割點位置
quicksort(arr,left,cut-1);//遞歸處理左序列
quicksort(arr,cut+1,right);//遞歸處理右序列
}/<code>

SGI STL中的寫法:

<code>stl_quicksort(first,last){
//循環作為外層控制結構
while(ok){
cut = stl_partition(first,last,_median(first,last));//分割分區
stl_quicksort(cut,last);//遞歸調用 處理右子序列
last = cut;//cut賦值為last 相當於切換到左子序列 再繼續循環
}
}
/<code>

網上有一些大佬的文章說sgi stl中快排的寫法左序列的調用藉助了while循環節省了一半的遞歸調用,是典型的尾遞歸優化思路.

這裡我暫時還沒有寫測試代碼做對比,先佔坑後續寫個對比試驗,再來評論吧,不過這種sgi的這種寫法可以看看哈。

堆排序的細節

<code>//注:這個是帶自定義比較函數的堆排序版本
//堆化和堆頂操作
template <class>
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>
inline void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp) {
__partial_sort(first, middle, last, value_type(first), comp);
}/<class>/<class>/<code>

插入排序上場了

__introsort_loop達到__stl_threshold閾值之後,可以認為數據集近乎有序了,此時就可以通過插入排序來進一步提高排序速度了,這樣也避免了遞歸帶來的系統消耗,看下__final_insertion_sort的具體實現:

<code>template <class>
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);
}
/<class>/<code>

來分析一下__final_insertion_sort的實現細節吧!

  • 引入參數隨機存取迭代器first和last
  • 如果last-first > __stl_threshold不成立就調用__insertion_sort,這個相當於元素數比較少了可以直接調用,不用做特殊處理;
  • 如果last-first > __stl_threshold成立就進一步再分割成兩部分,分別調用__insertion_sort和__unguarded_insertion_sort,兩部分的分割點是__stl_threshold,不免要問這倆函數有啥區別呀?

__insertion_sort的實現

<code>//逆序對的調整
template <class>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
RandomAccessIterator next = last;
--next;
while (value < *next) {
*last = *next;
last = next;
--next;
}
*last = value;
}

template <class>
inline void __linear_insert(RandomAccessIterator first,
RandomAccessIterator last, T*) {
T value = *last;
if (value < *first) {
copy_backward(first, last, last + 1);//區間移動
*first = value;
}
else
__unguarded_linear_insert(last, value);
}

//__insertion_sort入口
template <class>
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));

}
/<class>/<class>/<class>/<code>

在插入函數中同樣出現了 __unguarded_xxx這種形式的函數 ,unguarded單詞的意思是 無防備的,無保護的 ,侯捷大大提到這種函數形式是 特定條件下免去邊界檢驗條件 也能正確運行的函數。

copy_backward也是一種 整體移動 的優化,避免了one by one的調整移動,底層調用memmove來高效實現。

__unguarded_insertion_sort的實現

<code>template <class>
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>
inline void __unguarded_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last) {
__unguarded_insertion_sort_aux(first, last, value_type(first));
}/<class>/<class>/<code>

關於插入排序的這兩個函數的實現和目的用途,展開起來會很細緻,所以後面想著單獨在寫插入排序時單獨拿出了詳細學習一下,所以本文就暫時先不深究了,感興趣的讀者可以先行閱讀相關資料,後續我們再共同辯駁哈!

總結和筆者按

本文主要闡述了內省式排序的思想和基本實現思路,並且以此為切入點對sgi stl中sort算法的實現來進行了一些解讀。

stl的作者們為了追求極致性能所以使用了大量的技巧,對此本文並沒有過多展開,也主要是段位不太高怕解讀錯了,嘿嘿…,不過後續可以嘗試一點點剖析來一探大牛們的巔峰技藝。


分享到:


相關文章: