打造 Go 語言最快的排序算法

前言

說到排序算法，很多同學會想起快速排序、堆排序、冒泡排序這些耳熟能詳的算法。瞭解得深一些的同學，也可能看過例如 Python 的 timsort 以及 C++ intro sort 之類的排序算法。

但是我們也會有很多疑問，例如 Go 語言中使用的快速排序和我們書上學到的快速排序有什麼區別呢？如果我們自己寫一個快排，會比 Go 語言自帶的快嗎？排序算法方面業界最新的進展是什麼呢，有沒有一個算法是最快的？

本篇文章會向大家介紹字節跳動 - 語言團隊在 Go 語言排序算法的實踐，我們使用了 pdqsort 算法 + Go1.18 泛型，實現了一個比標準庫 API 在幾乎所有情況下快 2x ~ 60x 的算法庫。

此項改動已經被社區採納合併進入 Go runtime 當中，成爲默認的 unstable 排序算法，預計將會在 Go 1.19 中和大家見面，其中非泛型版本位於標準庫 sort，泛型版本位於 exp/slices。

Proposal: https://github.com/golang/go/issues/50154

臨時項目地址：https://github.com/zhangyunhao116/pdqsort

簡介

Go、Rust、C ++ 的默認 unstable 排序算法雖然名義上叫快速排序（quicksort），但其實質是混合排序算法（hybrid sorting algorithm），它們雖然在大部分情況下會使用快速排序算法，但是也會在不同情況下切換到其他排序算法。

unstable 排序算法意味着在排序過程中，值相等的元素可能會被互相交換位置。

一般來說，常見的混合排序算法，都會在元素較少（這個值一般是 16 ~ 32）的序列中切換成插入排序（insertion sort），儘管插入排序的時間複雜度爲 O(n^2)，但是其在元素較少時性能基本超越其他排序算法，所以在混合排序算法的方案中被經常使用。

在其他情況下，默認使用快速排序算法。然而，快速排序算法有可能因爲 pivot 選擇的問題（有些序列 pivot 選擇不好，導致性能下降很快）而導致在某些情況下可能到達最壞的時間複雜度 O(n^2)，爲了保證快速排序算法部分在最壞情況下，我們的時間複雜度仍然爲 O(n* logn)。大部分混合排序算法都會在某種情況下轉而使用堆排序，因爲堆排序在最壞情況下的時間複雜度仍然可以保持 O(n* logn)。

一言以蔽之，目前流行的 unstable 排序算法基本都是在不同的情況下，使用不同的方式排序從而達到最優解。而我們今天介紹的 pdqsort 也是這一思想的延伸。

前置知識

介紹一些常見的基本的排序算法以及它們的特性。

Quicksort (classic)

Average-case：O(n*logn) Bad-case：O(n^2)

經典的 快速排序（quicksort） 主要採用了分治的思想，具體的過程是將一個 array 通過選定一個 pivot（錨點）分成不同的 sub-arrays，選定 pivot 後，使得這個 array 中位於 pivot 左邊的元素都小於 pivot，位於 pivot 右邊的元素都大於 pivot。由此，pivot 兩邊構成了兩個 sub-arrays，然後對這些 sub-arrays 進行相同的操作（選定 pivot 然後切分）。當某個 sub-array 只有一個元素時，其本身有序，此時便可以退出循環。如此反覆，最後得到整體的有序。

我們可以觀察到，經典的 quicksort 主要過程就是兩步：

總的來說，quicksort 的性能關鍵點在於選定 pivot，選擇 pivot 的好壞直接決定了排序的速度，如果每次 pivot 都被選定爲真正的 median（中位數），此時快排的效率是最高的。因此 pivot 的選擇重點在於尋找 array 真正的 median，目前所有的 pivot 選擇方案都是在尋找一個近似的 median。

爲什麼 pivot 選定爲中位數使得快排效率最高？

詳細解釋可以參考：https://en.wikipedia.org/wiki/Quicksort#Formal_analysis。簡單來說，pivot 如果選定爲中位數，則大部分情況下每次 partition 都會形成兩個長度基本相同的 sub-arrays，我們只需要 logn 次 partition 就可以使得 array 完全有序，此時時間複雜度爲 O(n* logn)。在最壞情況下，我們需要 n-1 次 partition （每次將長度爲 L 的 array 分爲長度爲 1 和 L - 1 的兩個 sub-arrays）才能使得 array 有序，此時時間複雜度爲 O(n^2)。

我們爲何不直接尋找 array 真正的 median？

原因是因爲 array 的長度太長的話，尋找真正的 median 是一個非常昂貴的操作（需要存儲所有的 items），相比於尋找一個近似的 median 作爲 pivot 會消耗更多的資源，如果找到正確 median 的消耗比使用一個近似 median 高的話，這就是一個負優化。折中的方案就是使用一個高性能的近似 median 選擇方案。

基本所有針對 quicksort 的改進方案，都是通過改造這兩步得到的，例如第一步可以使用多種不同的 pivot 選擇方案（見附錄），第二步則有諸如 BlockQuickSort 這樣通過減少分支預測來提升性能的方案。

Insertion sort

插入排序的主要想法是，每一次將一個待排序的元素插入到前方已經排序好的序列中，直到插入所有元素。儘管其平均時間複雜度高達 O(n^2)，但是在 array 長度較短（這個值一般是 16 ~ 32）的情況下，在實際應用中擁有良好的性能表現。

Heap sort

堆排序是利用堆結構設計出來的一種排序算法。這個算法有一個非常重要的特性，其在最壞情況下的時間複雜度仍然爲 O(n* logn)。故而很多混合排序算法利用了這一特性，將堆排序作爲 fall back 的排序算法，使得混合排序算法在最壞情況下的理論時間複雜度仍然爲 O(n* logn)。

pdqsort (pattern-defeating quicksort)

論文地址：https://arxiv.org/pdf/2106.05123.pdf

pdqsort (pattern-defating quicksort) 是 Rust、C++ Boost 中默認的 unstable 排序算法，其實質爲一種混合排序算法，會在不同情況下切換到不同的排序機制，是 C++ 標準庫算法 introsort 的一種改進。可以認爲是 unstable 混合排序算法的較新成果。

其理想情況下的時間複雜度爲 O(n)，最壞情況下的時間複雜度爲 O(n* logn)，不需要額外的空間。

pdqsort 的主要改進在於，其對 common cases （常見的情況）做了特殊優化。因此在這些情況下性能超越了之前算法，並且相比 introsort 在隨機序列的排序性能基本保持了一致。例如當序列本身有序、完全逆序、基本有序這些情況下都超越了大部分算法。其主要的思想是，不斷判定目前的序列情況，然後使用不同的方式和路徑達到最優解。

這裏的算法細節描述的是 https://github.com/zhangyunhao116/pdqsort 中的實踐，其大致相當於論文中的 PDQ 算法（沒有來自 BlockQuickSort 的優化），並且加入了一些參數調整以及借鑑了部分其他 pdqsort 的實踐優化。

注意，不同 pdqsort 實踐中會有一些細微差異（因爲語言以及接口的關係），不過其總體思想是一致的。

pdqsort C++ 版本性能對比，位於 https://github.com/orlp/pdqsort

整體流程

爲了更好地解析 pdqsort 算法，我們先來描述下其主要流程。pdqsort 就是下面三種情況的不斷循環，根據序列長度以及是否是最壞情況，每個 array 都會使用下面三種方法之一進行排序（有優先級，儘可能使用排在前面的方式）

  1. 短序列情況，對於長度在 [0, MAX_INSERTION] 的輸入，使用 insertion sort （插入排序）來進行排序後直接返回，這裏的 MAX_INSERTION 我們在 Go 語言下的性能測試，選定爲 24。

  2. 最壞情況，如果發現改進的 quicksort 效果不佳（limit == 0），則後續排序都使用 heap sort 來保證最壞情況時間複雜度爲 O(n*logn)。

  3. 正常情況，對於其他輸入，使用改進的 quicksort 來排序，這裏的算法分幾步，後續內容會詳細介紹部分步驟。

圖中淺黃色虛線框代表此步驟爲可選項，即算法會根據情況（以下變量）來決定是否執行。

下列變量代表 pdqsort 進行本次循環排序的情況，用於幫助算法來猜測需要排序的 array 的狀態，來決定某些步驟是否需要進行

3-1. 應對可能的最壞情況，即實現中的breakPatterns。此時會判斷 wasBalanced 是否爲 true，如果不平衡（false），則隨機交換幾個元素，破壞一些可能造成 pivot 與 median 相差較大的特殊情況。

3-2. pivot 的選擇，即實現中的 choosePivot。函數同時返回兩個值，pivotidx 和 likelySorted，前者是 pivot 在此 array 的 index（索引），後者代表着選擇 pivot 的過程中，是否可以大概率認定這個 array 已經爲有序。

3-3. 應對幾乎有序的情況，即實現中的 partialInsertionSort。如果 wasBalanced && wasPartitioned && likelySorted 爲 true，則代表此 array 有非常大的可能是一個有序序列。此時我們使用 partial insertion sort 的排序算法，其原理和 insertion sort 大致相當，只是多了一個嘗試次數，即只會對有限的元素進行插入排序，增加這個限制是爲了避免猜測錯誤導致消耗大量時間。如果達到嘗試次數時 array 仍未有序，則退出。如果在嘗試次數之前發現所有元素有序，則可以直接返回。

3-4. 應對重複元素較多的情況，即實現中的 partitionEqual 。如果 pred 存在，並且和本次選中的 pivot 值相等（pred 是之前 array 的 pivot，即目前 array 中的最小值，因爲與 pivot 重複的元素只可能出現在 partition 後的兩個 sub-arrays 其中之一），說明重複元素很可能較多，則調用 partitionEqual 然後繼續進行下次循環，使用這種方法將重複元素提前放到一起，因爲多次選定重複元素作爲 pivot 會使得 partition 的效率較低。

3-5. partition，使用 pivot 來分割 array，即實現中 partition。此函數和一般快排的 partition 相比基本相同，區別在於其會檢測序列是否本身就是有序的（即 partition 時沒有交換任何元素）。

實現細節

breakPatterns (3-1)

這一步的作用是解決一些會導致現有 pivot 選擇方案表現很差的情況，所以當上次 partition 的 pivot 選擇不好時（表現爲最終 pivot 的位置離 array 兩端之一很近），此時會隨機交換幾個元素來避免一些極端情況。同時，此步驟還會將 limit 減去 1，說明上次 pivot 的選取方案不夠好（當 limit 爲 0 時使用 heapsort 而不是快排方案來進行排序）。

pivot 選擇 (3-2)

附錄中有關於 pivot 選擇方案的詳細介紹。

假設 array 的長度爲 L，SHORTEST_MEDIAN_OF_MEDIANS 值爲 50。這裏根據長度分爲三種情況：

  1. L 位於 [0,8): 直接取固定值作爲 pivot，即 L/4 * 2

  2. L 位於 [8,SHORTEST_MEDIAN_OF_MEDIANS): 使用 medians of three 方法採樣 3 個元素篩選 pivot，即 L/4* 1 L/4* 2 L/4* 3 的中間值

  3. L 位於 [SHORTEST_MEDIAN_OF_MEDIANS, ∞): 使用 Tukey’s median of medians 採樣 9 個元素得到一個近似中間值

此方法還會判斷這個 array 是否很可能已經有序，例如當第三種情況時，如果發現 a a-1 a+1 這三個值中，a 恰好是中間值（b,c 也同樣如此），則說明元素在這些地方都局部有序，所以這個 array 很可能是已經有序的。如果每次都發現，a a-1 a+1 這三個值都是逆序排列（b,c 也同樣如此），則說明元素在這些地方都局部逆序，整個 array 很可能是完全逆序的。此時的策略是將整個 array 翻轉，這樣有很大概率使得整個 array 幾乎有序。

Go 語言環境下的實踐考量

Go 1.18 泛型對於排序算法的影響

Go 1.18 的泛型在這種情況下有較大的性能提升並且增加了可維護性，同樣的算法在經過泛型改造後能得到 2x 的性能提升。這一點我們通過觀察 pdqsort 泛型版本，以及 pdqsort (with sort.Interface) 的版本性能對比可以觀察出來。

在可維護性方面，通過泛型的類型約束抽象了所有可比對的基本類型，不需要使用複雜的代碼生成技術。

在性能方面，泛型由於有了類型參數，可以在編譯期生成大量代碼，免去了使用 sort.Interface 帶來的抽象開銷。

pdqsort 相比於 Go 原有算法的優勢

在純粹的算法層面，即 pdqsort (with sort.Interface) ，pdqsort 在完全隨機的情況下和原有算法（類似於 IntroSort）性能幾乎一致（非泛型版本，因爲需要兼容 sort.Interface）。在常見的場景下（例如序列有序 | 幾乎有序 | 逆序 | 幾乎逆序 | 重複元素較多）等情況下，會比原有的算法快 1 ~ 30 倍。

因此，我們同樣向 Go 官方提議將 pdqsort 應用在 sort.Sort 中，相關的 issue 討論位於：https://github.com/golang/go/issues/50154

Go 原有的算法類似於 introsort，其通過遞歸次數來決定是否切換到 fall back 算法，而 pdqsort 使用了另一種計算方式（基於序列長度），使得切換到 fall back 算法的時機更加合理。

爲什麼禁用來自 BlockQuickSort 的優化

因爲 BlockQuickSort 的優化基本來自減少分支預測，原理是在 partition 一個長序列的時候，先存儲需要交換的元素，後續統一放到真正的序列中。經過實際性能測試，發現這一優化在 Go 上並不成立，甚至是一個負優化。原因可能由於 Go 是一門 heap-allocate 的語言，對於此類優化並不敏感。並且對於減少分支預測，Go 的編譯器在某些情況下並不能優化到相應指令（CMOV）。

總結

目前大部分工業界使用的 unstable 排序算法，基本上都從過去教科書中單一的排序算法轉變成混合排序算法，來應對實踐場景中各式各樣的序列。

pdqsort 依靠其在常見場景相比之前算法的性能優勢，逐漸成爲 unstable 排序算法的主流實現。基於 Go1.18 帶來的泛型，使得排序算法的實現被大大簡化，也給予了我們實現新算法的可能。但是 pdqsort 也不是萬能靈藥，在某些情況下，其他的算法依然保持着優勢（例如 Python 標準庫的 timsort 在混合升序 && 降序的場景優於 pdqsort）。不過在大部分情況下，pdqsort 依靠其對於不同情況的特定優化，成爲了 unstable 算法較好的選擇。

附錄

quicksort pivot 方案對比

這裏簡單介紹不同的 pivot 選擇方案。最好的 pivot 選擇方案就是使用一個高性能的近似 median 選擇方案，在準確度和性能上達到平衡。假設我們需要排序的元素爲 [4,3,2,1]，我們需要將其排列爲升序，即 [1,2,3,4]。

選擇首個元素

這是我們實現快排時最簡單的方法，即選取 array 的首個元素作爲 pivot。

可以看到，選擇首個元素的方式在 array 爲逆序的情況下，每輪 partition 只將問題的規模減小了 1，即每次只能確定一個元素的最終位置。這種簡單的方法在面對極端情況時效果並不好，在完全逆序的情況下達到了快排的最壞情況。

median of three

這個方法是分別取最左邊、最右邊、中間三個值，然後選出其中間值作爲 pivot。例如 [4,3,2,1]，我們會選取 4 3 1 然後選擇其中的 3 作爲 pivot。這種方式相比於首個元素的方式會更加合理，因爲採樣了多個元素，不容易受到一些極端情況的影響，往往會比首個元素的方式有更好的效果。

stackoverflow discussion:

https://stackoverflow.com/questions/7559608/median-of-three-values-strategy

median of medians

這個方法的原理其實和 median of three 相似，不同的地方在於加大了 pivot 的採樣範圍，在 array 長度較長的情況下理論表現會更好。其採樣步驟是先將 array 分爲 n/5 個 sub-arrays，n 爲 array 的長度。然後將這些 sub-arrays 的 medians 都取出，選取這些 medians 中的 median，同樣的方式如此反覆，最後得到一個 median of medians 作爲最後的 pivot。

stackoverflow discussion:

https://stackoverflow.com/questions/5605916/quick-sort-median-selection

Median-finding Algorithm:

https://brilliant.org/wiki/median-finding-algorithm/#citation-1

John Tukey’s median of medians

此方法其實是 median of three 的改進，我們在 median of three 會取三個元素，而 Tukey’s median of medians 會取三個元素及其相鄰兩個元素的 median（例如 median of three 取了 a,b,c 則此方案會選擇 a-1 a a+1 取這三個值的 median），然後再取這個三個 medians 的 median。即此方案會採樣其中 9 個元素，相比於 median of three 多了三倍的採樣率，所以此方法也叫做 Tukey’s ninther。

See

https://www.johndcook.com/blog/2009/06/23/tukey-median-ninther/

加入我們

字節跳動語言團隊致力於解決公司內部大規模集羣中程序語言相關的各種問題，讓 Go, Python, Java, node.js 和 C/C++ 等多種語言更好的有機結合在一起，利用每種語言獨立的特性更好的發揮它們各自的長處。

我們正在尋求優秀的同學加入！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/5HqfRGqPyAhFt0krPgMHOQ

猜你喜歡