在計算機(jī)科學(xué)的領(lǐng)域,排序算法是每位學(xué)生必學(xué)的基礎(chǔ),而排序的需求是每位程序員在編程過程中都會遇到的。
在你輕松調(diào)用 .sort() 方法對數(shù)據(jù)進(jìn)行排序時,是否曾好奇過,這個簡單的方法背后使用的是哪種排序算法呢?
本文將帶你走進(jìn) TimSort,一個在標(biāo)準(zhǔn)函數(shù)庫中廣泛使用的排序算法。
這個算法由工程師 Tim Peters 于 2001 年專為 Python 設(shè)計,并自 Python 2.3 版本起成為其默認(rèn)排序算法。它的影響不止于此,Java、Android、GNU Octave、Chrome 的 V8 引擎、Swift 以及 Rust 等也紛紛采用了這一算法。
那么,是什么讓 TimSort 在眾多排序算法中獨(dú)樹一幟,贏得了如此廣泛的應(yīng)用和認(rèn)可呢?
在本文中,我們將深入剖析 TimSort 的內(nèi)部機(jī)制,揭示其背后的高效實(shí)現(xiàn)原理,讓你領(lǐng)略這一算法的獨(dú)特魅力。
小規(guī)模數(shù)據(jù)的高效處理:插入排序
TimSort 是一個結(jié)合了插入排序和歸并排序的混合排序算法,特別適合處理真實(shí)世界的各種數(shù)據(jù)。
從這句定義中您可能會好奇,為什么 TimSort 選擇了插入排序和歸并排序?為什么說它適合處理真實(shí)世界的數(shù)據(jù)?
讓我們首先探討第一個問題,為什么插入排序成為了 TimSort 的關(guān)鍵組成部分。
盡管插入排序的理論時間復(fù)雜度為 O(n^2),看似不及 O(nlogn) 的高效排序算法,但插入排序的實(shí)際效率卻非常高效,尤其是在處理小規(guī)模數(shù)據(jù)集時。
這是因?yàn)椴迦肱判蛑簧婕皟蓚€簡單操作:比較和移動。
通過比較,我們能夠確定新元素的插入點(diǎn);通過移動,我們?yōu)樾略氐牟迦腧v出空間。
視頻 插入排序
關(guān)鍵在于,對于小數(shù)據(jù)集而言,n^2 與 nlogn 的差異并不顯著,復(fù)雜度不占主導(dǎo)作用,此時每輪單元的操作數(shù)量才起到?jīng)Q定性因素。得益于其簡潔的操作,插入排序在小規(guī)模數(shù)據(jù)集上的表現(xiàn)通常非常出色。
但究竟什么規(guī)模的數(shù)據(jù)集算是“小”呢?
以 Python 為例,當(dāng)數(shù)據(jù)集大小小于 64 時,它會默認(rèn)采用插入排序。而在 Java 中,這一界限則被設(shè)定在了 32。
插入排序的優(yōu)化:二分插入排序
對于 TimSort 算法來說,傳統(tǒng)插入排序也存在進(jìn)一步提升性能的空間。
回顧一下,插入排序涉及的關(guān)鍵操作有兩個:比較和移動。這其中,對于一個數(shù)組來說,移動的總次數(shù)是固定不變的,因此,我們可以嘗試從減少比較的次數(shù)來優(yōu)化。
在插入排序的執(zhí)行過程中,數(shù)據(jù)被劃分為已排序和未排序的兩個部分。在已排序部分,我們尋找未排序部分下一個元素的插入位置時,常規(guī)做法是采用線性查找。
但 TimSort 采用了更高效的策略——二分查找法。利用二分查找在已排序部分尋找插入點(diǎn),大幅減少了比較次數(shù)。
對小規(guī)模數(shù)據(jù)集而言,這種優(yōu)化尤其有效,能顯著提升排序的效率。
視頻 二分查找插入位置
舉個例子,如上面視頻所示,在使用傳統(tǒng)插入排序時,為將元素 2 插入正確位置,需要進(jìn)行 5 次比較。而在二分插入排序中,這一過程可以縮減至僅需 2 次比較,從而顯著提高排序效率。
TimSort 的工作原理
在詳細(xì)了解了插入排序在 TimSort 中的作用之后,接下來我們可以進(jìn)一步了解歸并排序在 TimSort 中的應(yīng)用。不過在這之前,我們需要知道 TimSort 的整體工作原理。
TimSort 的設(shè)計目標(biāo)是最大限度地利用在絕大多數(shù)實(shí)際數(shù)據(jù)中已經(jīng)存在的連續(xù)有序序列,這些被稱為自然序列 natural run。
在算法的執(zhí)行過程中,它遍歷數(shù)據(jù)集,借助于這些自然序列,必要時將附近的元素添加進(jìn)去,形成一個個的數(shù)據(jù)塊 run,其中每個 run 中的元素都會進(jìn)行排序。
隨后,這些有序的 run 被堆疊在一個棧中,形成了算法處理過程的一個關(guān)鍵結(jié)構(gòu)。
動圖 run 堆疊
當(dāng)一個新的 run 被識別并加入到棧中后,TimSort 會根據(jù)棧頂多個 run 的長度來判斷,是否應(yīng)該合并棧頂附近的 run。
這個過程將持續(xù)進(jìn)行,直到所有數(shù)據(jù)都遍歷完。
run 合并
遍歷結(jié)束后,棧中剩余的所有 run 每次兩兩合并,直到最終形成一個完整有序的 run。
相比傳統(tǒng)歸并排序,合并預(yù)排序的 run 會大大減少了所需的比較次數(shù),從而提升了整體的排序效率。
現(xiàn)在,你可能對 TimSort 算法的細(xì)節(jié)產(chǎn)生了許多疑問。run 是如何形成的?這些 run 是如何利用數(shù)據(jù)中已存在的自然序列?當(dāng) run 被加入到棧中后,依據(jù)什么規(guī)則來決定是否合并?……
不用擔(dān)心,接下來我們將逐一解答這些問題,帶你更深入地理解 TimSort 算法。
計算 minrun
在 TimSort 算法中,run 的生成非常關(guān)鍵,而這一過程的核心是確定 run 最小長度 minrun。這個長度的設(shè)定是為了在排序過程中達(dá)到兩個關(guān)鍵目標(biāo):
確保 run 足夠長,以便有效地利用歸并排序;
避免 run 過于長,從而在合并時仍能保持高效。
實(shí)驗(yàn)研究表明,當(dāng) minrun 小于 8 時,第一條原則難以滿足;而當(dāng) minrun 超過 256 時,第二條原則受到影響。
因此,最佳的 minrun 長度范圍被確定在 32 到 64 之間。
這個范圍與我們之前提到的插入排序中小規(guī)模數(shù)據(jù)集的長度范圍非常接近,這并非巧合。事實(shí)上,Timsort 在生成 run 時也會利用到插入排序。
具體計算 minrun 的方法如下:
目標(biāo):選取一個 minrun 值,以使長度為 n 的數(shù)組被分割成約 n/minrun 個 runs,每個 run 包含大約 32 到 64 個元素。
計算方法:選擇最接近 n/(2^k) 的 minrun 值,這里 k 是使 n/(2^k) 落在32至64之間的最大整數(shù)。然后設(shè)置 minrun 為 n/(2^k)。
例如,對于長度為 65 的數(shù)組,minrun 將設(shè)置為33,形成 2 個runs;對于長度為 165 的數(shù)組,minrun 設(shè)置為42,形成 4 個runs。
這個計算過程涉及到 (2^k),可以通過位移操作高效實(shí)現(xiàn):
defget_minrun(n): #用于記錄在不斷右移過程中,n的最低位上非零位的數(shù)量 r=0 whilen>=64: #檢查n的最低位是否為1,若是,則設(shè)置r為1 r|=n&1 #向右移動一位,相當(dāng)于n除以2 n>>=1 #返回n加上r,n是原始值的最高6位,r是表示過程中n是否有非零最低位的標(biāo)志 returnn+r
這種方法不僅保證了 minrun 的有效性,而且利用了位運(yùn)算的高效性,體現(xiàn)了 TimSort 設(shè)計的巧思。
run 的生成過程
在掌握了 minrun 的計算方法之后,我們現(xiàn)在可以探究 run 是如何生成的。
TimSort 的核心目標(biāo)是充分利用數(shù)據(jù)中已存在的連續(xù)有序序列來生成 run,但這是如何實(shí)現(xiàn)的呢?
TimSort 的處理流程可分為以下幾個關(guān)鍵步驟:
TimSort 開始掃描整個數(shù)組,尋找連續(xù)的升序或降序序列。
如果遇到升序部分,TimSort 會持續(xù)掃描直到升序結(jié)束。
如果遇到降序部分,TimSort 會繼續(xù)掃描直到降序結(jié)束,并隨后將這部分翻轉(zhuǎn)成升序。
如果上述步驟識別的 run 未達(dá)到 minrun 長度,TimSort 會繼續(xù)擴(kuò)展這個 run,向數(shù)組后方遍歷,納入更多元素,直至達(dá) minrun 長度。在這個階段,新加入元素的順序并不重要。
一旦擴(kuò)展完成,這個擴(kuò)展后的 run(無論其最初是否有序)都將通過插入排序進(jìn)行排序,以確保其內(nèi)部有序。
如果識別的 run 長度遠(yuǎn)超 minrun,對于這些較長的連續(xù)有序序列,TimSort 會保持其原始長度,不進(jìn)行切割。這是因?yàn)檩^長的有序序列對于減少后續(xù)合并操作的復(fù)雜度非常有利。
對于這些超長的 run,通常無需進(jìn)行額外排序,除非它們是降序,這時 TimSort 會先將其翻轉(zhuǎn)成升序。
通過這些策略,TimSort 能夠高效地生成一個有序的、長度至少為 minrun 的 run,為后續(xù)的歸并排序過程奠定了堅實(shí)基礎(chǔ)。
棧中 run 的合并規(guī)則
在 TimSort 算法中,每生成一個新的 run,它就會被加入到一個專門的棧中。
這時,TimSort 會對棧頂?shù)娜齻€ run(我們稱它們?yōu)閄、Y和Z)進(jìn)行檢查,以確保它們符合特定的合并規(guī)則:
|Z| > |Y| + |X|
|Y| > |X|
如果這些條件沒有被滿足,Y 就會與 X 或 Z 中較小的一個合并,并重新檢查上述條件。當(dāng)所有條件都滿足時,可以在數(shù)據(jù)中繼續(xù)遍歷生成新的 run。
run 合并
這種獨(dú)特的合并規(guī)則是為了實(shí)現(xiàn)什么目標(biāo)呢?
在 TimSort 的合并規(guī)則下,最終保留在棧中的每個 run 的長度至少等于前兩個 run 的總長度(由于滿足|Z| > |Y| + |X| 和 |Y| > |X|的規(guī)則)。
這種設(shè)計意味著,隨著時間的推移,棧中 run 的長度會逐漸增大,其增長方式類似于斐波那契數(shù)列。
這種增長模式的一個重要優(yōu)勢在于,它提供了一種有效的方式來平衡數(shù)據(jù)遍歷完成之后 run 的合并操作,同時避免了過于頻繁的合并。
在最理想情況下,這個棧從頂部到底部 run 的長度應(yīng)該是[2,2,4,8,16,32,64,...]。這樣,從棧頂?shù)綏5椎暮喜⑦^程中,每次合并的兩個 run 的長度都是相等的,形成了完美的合并。
棧中 run 最理想形態(tài)
通過這些巧妙的規(guī)則,TimSort 在保證合并操作近似均衡的同時,也確保了在追求均衡和簡化合并決策之間的權(quán)衡。
正如 Tim Peters 所指出的,找到一種方式來維持棧中這兩個規(guī)則,是一個極具智慧的折中選擇。
合并過程中的空間開銷
了解完 TimSort 的工作原理和 run 在棧中的合并規(guī)則之后,我們現(xiàn)在來看 TimSort 中的最后一個重要環(huán)節(jié):如何高效地運(yùn)用歸并排序?
雖然傳統(tǒng)的歸并排序也擁有 O(nlogn) 的時間復(fù)雜度,但它并不是原地排序,并且需要額外的 O(n) 空間開銷,這使得它并沒有被廣泛地運(yùn)用。
當(dāng)然,也有改良過的原地歸并排序的實(shí)現(xiàn),但它們的時間開銷就會比較大。為了在效率和空間節(jié)約之間取得平衡,TimSort 采用了一種改進(jìn)的歸并排序,其空間開銷遠(yuǎn)小于O(n)。
以一個具體例子來說明:假設(shè)我們有兩個已排序的數(shù)組 [1, 2, 3, 6, 10] 和 [4, 5, 7, 9, 12, 14, 17],目標(biāo)是將它們合并。
在這個例子中,我們可以觀察到:
第二個數(shù)組中的最小元素(4)需要插入到第一個數(shù)組的第四個位置以保持整體順序,
第一個數(shù)組中的最大元素(10)需要插入到第二個數(shù)組的第五個位置。
因此,兩個數(shù)組中的 [1, 2, 3] 和 [12, 14, 17] 已經(jīng)位于它們的最終位置,無需移動。我們實(shí)際上需要合并的部分是 [6, 10] 和 [4, 5, 7, 9]。
在這種情況下,我們只需要創(chuàng)建一個大小為 2 的臨時數(shù)組,將[6, 10]復(fù)制到其中,然后在原數(shù)組中將它們與[4, 5, 7, 9]合并。
動圖 歸并排序 優(yōu)化合并過程
這個例子展示了從前往后的合并過程。同樣,還有從后往前合并的情況:
動態(tài)圖 歸并排序 從后往前合并
與傳統(tǒng)歸并排序相比,TimSort 在這里采用的優(yōu)化策略顯著減少了元素移動的次數(shù),縮短了運(yùn)行時間,并大幅降低了臨時空間的需求。
合并過程中的 galloping mode
在歸并排序過程中,通常的做法是逐個比較兩個數(shù)組中的元素,并將較小的元素依次放置到合適的位置。
然而,在某些情況下,這種方法可能涉及大量冗余的比較操作,尤其是當(dāng)一個數(shù)組中的元素連續(xù)地勝出另一個數(shù)組時。
想象一下,如果我們有兩個極端不平衡的數(shù)組:
A = [1, 2, 3, …, 9999, 10000]
B = [20000, 20001, …, 29999, 30000]
在這種情況下,為了確定 B 中元素的正確插入點(diǎn),我們需要進(jìn)行高達(dá) 10000 次的比較,這無疑是低效的。
如何解決這個問題呢?
TimSort 的解決方案是引入了所謂的“躍進(jìn)模式”(galloping mode)。這種模式基于一個假設(shè):如果一個數(shù)組中的元素連續(xù)勝出另一個數(shù)組中的元素,那么這種趨勢可能會持續(xù)下去。
TimSort 會統(tǒng)計從一個數(shù)組連續(xù)選中的元素數(shù)量,一旦連續(xù)勝出次數(shù)達(dá)到了稱為 min_gallop 的閾值時,TimSort 就會切換到躍進(jìn)模式。
在這種模式下,算法將不再逐個比較元素,而是將實(shí)施一種指數(shù)級搜索(exponential search)。以指數(shù)級的步長(2^k)進(jìn)行跳躍,首先檢查位置 1 的元素,然后是位置 3 (1 + 2^1 ),接著是位置 7 (3 + 2^2),以此類推。
當(dāng)首次找到大于或等于比較元素的位置時,我們就將搜索范圍縮小到上一步的位置(2^(k-1) + 1)和當(dāng)前步的位置(2^k + 1)之間的區(qū)間。
在這個區(qū)間內(nèi)進(jìn)行更二分搜索,以快速定位正確的插入位置。
據(jù)開發(fā)者的基準(zhǔn)測試,只有當(dāng)一個數(shù)組的首元素并不處于另一數(shù)組的前 7 位置時,躍進(jìn)模式才真正帶來優(yōu)勢,因此 min_gallop 的閾值為 7。
上面的步驟看起來比較復(fù)雜,我們以兩個數(shù)組為例:
A = [1, 25, 31, 37]
B = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36]
根據(jù)之前合并過程中的空間開銷原則,A 中的元素 1 是固定的,此時將25, 31, 37 移動到臨時空間進(jìn)行合并排序。
動圖 躍進(jìn)模式 1
在這種情況下,當(dāng) 25 在與 B 數(shù)組元素比較時連續(xù)勝出,觸發(fā)了躍進(jìn)模式。
動圖 躍進(jìn)模式 2
算法直接跳躍到位置 15 (7 + 2^3),發(fā)現(xiàn) 30 大于 25。
動圖 躍進(jìn)模式 3
進(jìn)而在位置 7 和 15 之間執(zhí)行二分搜索,以找到 25 的插入點(diǎn)。
動圖 躍進(jìn)模式 4
雖然躍進(jìn)模式在某些情況下能極大提高效率,但它并非總是最優(yōu)選擇。有時,躍進(jìn)模式可能導(dǎo)致更多的比較操作,尤其是在數(shù)據(jù)分布較為均勻時。
為了避免這種情況,TimSort采用了兩種策略:一是當(dāng)識別到躍進(jìn)模式的效率不及二分搜索時,會退出躍進(jìn)模式;二是根據(jù)躍進(jìn)模式的成功與否調(diào)整 min_gallop 值。
如果躍進(jìn)模式成功且連續(xù)選擇的元素均來自同一數(shù)組,min_gallop 值會減 1,以鼓勵再次使用躍進(jìn)模式;反之,則加 1,減少再次使用躍進(jìn)模式的可能性。
結(jié)語:TimSort - 數(shù)據(jù)排序的實(shí)用革新
在探索數(shù)據(jù)排序這個歷史悠久且充滿挑戰(zhàn)的領(lǐng)域中,TimSort 算法不僅是一項技術(shù)成就,更是實(shí)用性與創(chuàng)新的杰出典范。它的出現(xiàn),不單單是算法領(lǐng)域的一個新節(jié)點(diǎn),更是對現(xiàn)實(shí)世界復(fù)雜數(shù)據(jù)處理需求的有效回應(yīng)。
TimSort 的真正魅力不僅在于它的高效率,更在于它對實(shí)際數(shù)據(jù)特性的深入理解和利用。這個算法不是靜態(tài)的,它通過對數(shù)據(jù)的觀察,動態(tài)調(diào)整自身策略,以適應(yīng)不同的數(shù)據(jù)模式。
這種設(shè)計思路提供了一個重要的啟示:在面對現(xiàn)實(shí)世界問題時,理論和實(shí)踐的結(jié)合往往比單純追求理論完美更為重要。
通過本文的深入分析,我們對 TimSort 的工作原理及其核心概念有了更為直觀的理解?,F(xiàn)在,如果再次回顧它的定義,您會發(fā)現(xiàn)自己有了更深刻的認(rèn)識。
參考資料:
[1] https://en.wikipedia.org/wiki/Timsort
[2] https://dev.to/brandonskerritt/timsort-the-fastest-sorting-algorithm-you-ve-never-heard-of-2ake
[3] https://www.infopulse.com/blog/timsort-sorting-algorithm
[4] https://juejin.cn/post/6844904131518267400
[5] https://www.youtube.com/watch?v=_dlzWEJoU7I
[6] https://www.youtube.com/watch?v=1wAOy88WxmY
-
函數(shù)
+關(guān)注
關(guān)注
3文章
4379瀏覽量
64622 -
排序算法
+關(guān)注
關(guān)注
0文章
53瀏覽量
10237
原文標(biāo)題:這么多年排序白學(xué)了,原來每次排序都在使用世界上最快的排序算法 TimSort
文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
自己寫庫:構(gòu)建庫函數(shù)雛形

函數(shù)指針的六個常見應(yīng)用場景

Stm32f103 hal庫如果設(shè)置多個外部中斷,只要用螺絲刀碰觸其中一個中斷線,所有的中斷函數(shù)都有可能進(jìn)入,亂跳,為什么?
如何找到DLP4500的API函數(shù)庫和說明手冊?
三角函數(shù)的應(yīng)用廣泛性:從算法設(shè)計到DSP芯片實(shí)現(xiàn)的探索
HAL庫在Arduino平臺上的使用
HAL庫和標(biāo)準(zhǔn)庫的區(qū)別 HAL庫與CMSIS的關(guān)系
HAL庫的函數(shù)調(diào)用示例
常用SQL函數(shù)及其用法
RNN的損失函數(shù)與優(yōu)化算法解析
時間復(fù)雜度為 O(n^2) 的排序算法

怎么在TMDSEVM6678: 6678自帶的FFT接口和CUDA提供CUFFT函數(shù)庫選擇?
為什么在水文計算中廣泛采用配線法
利用vMeasure eMobilityAnalyzer函數(shù)庫分析電機(jī)性能

評論