色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術視頻
  • 寫文章/發帖/加入社區
會員中心
創作中心

完善資料讓更多小伙伴認識你,還能領取20積分哦,立即完善>

3天內不再提示

TimSort:一個在標準函數庫中廣泛使用的排序算法

算法與數據結構 ? 來源:算法與數據結構 ? 2025-01-03 11:42 ? 次閱讀

在計算機科學的領域,排序算法是每位學生必學的基礎,而排序的需求是每位程序員編程過程中都會遇到的。

在你輕松調用 .sort() 方法對數據進行排序時,是否曾好奇過,這個簡單的方法背后使用的是哪種排序算法呢?

本文將帶你走進 TimSort,一個在標準函數庫中廣泛使用的排序算法。

這個算法由工程師 Tim Peters 于 2001 年專為 Python 設計,并自 Python 2.3 版本起成為其默認排序算法。它的影響不止于此,JavaAndroid、GNU Octave、Chrome 的 V8 引擎、Swift 以及 Rust 等也紛紛采用了這一算法。

那么,是什么讓 TimSort 在眾多排序算法中獨樹一幟,贏得了如此廣泛的應用和認可呢?

在本文中,我們將深入剖析 TimSort 的內部機制,揭示其背后的高效實現原理,讓你領略這一算法的獨特魅力。

小規模數據的高效處理:插入排序

TimSort 是一個結合了插入排序和歸并排序的混合排序算法,特別適合處理真實世界的各種數據。

從這句定義中您可能會好奇,為什么 TimSort 選擇了插入排序和歸并排序?為什么說它適合處理真實世界的數據?

讓我們首先探討第一個問題,為什么插入排序成為了 TimSort 的關鍵組成部分。

盡管插入排序的理論時間復雜度為 O(n^2),看似不及 O(nlogn) 的高效排序算法,但插入排序的實際效率卻非常高效,尤其是在處理小規模數據集時。

這是因為插入排序只涉及兩個簡單操作:比較和移動。

通過比較,我們能夠確定新元素的插入點;通過移動,我們為新元素的插入騰出空間。

視頻 插入排序

關鍵在于,對于小數據集而言,n^2 與 nlogn 的差異并不顯著,復雜度不占主導作用,此時每輪單元的操作數量才起到決定性因素。得益于其簡潔的操作,插入排序在小規模數據集上的表現通常非常出色。

但究竟什么規模的數據集算是“小”呢?

以 Python 為例,當數據集大小小于 64 時,它會默認采用插入排序。而在 Java 中,這一界限則被設定在了 32。

插入排序的優化:二分插入排序

對于 TimSort 算法來說,傳統插入排序也存在進一步提升性能的空間。

回顧一下,插入排序涉及的關鍵操作有兩個:比較和移動。這其中,對于一個數組來說,移動的總次數是固定不變的,因此,我們可以嘗試從減少比較的次數來優化。

在插入排序的執行過程中,數據被劃分為已排序和未排序的兩個部分。在已排序部分,我們尋找未排序部分下一個元素的插入位置時,常規做法是采用線性查找。

但 TimSort 采用了更高效的策略——二分查找法。利用二分查找在已排序部分尋找插入點,大幅減少了比較次數。

對小規模數據集而言,這種優化尤其有效,能顯著提升排序的效率。

視頻 二分查找插入位置

舉個例子,如上面視頻所示,在使用傳統插入排序時,為將元素 2 插入正確位置,需要進行 5 次比較。而在二分插入排序中,這一過程可以縮減至僅需 2 次比較,從而顯著提高排序效率。

TimSort 的工作原理

在詳細了解了插入排序在 TimSort 中的作用之后,接下來我們可以進一步了解歸并排序在 TimSort 中的應用。不過在這之前,我們需要知道 TimSort 的整體工作原理。

TimSort 的設計目標是最大限度地利用在絕大多數實際數據中已經存在的連續有序序列,這些被稱為自然序列 natural run。

在算法的執行過程中,它遍歷數據集,借助于這些自然序列,必要時將附近的元素添加進去,形成一個個的數據塊 run,其中每個 run 中的元素都會進行排序。

隨后,這些有序的 run 被堆疊在一個棧中,形成了算法處理過程的一個關鍵結構。

281eea24-c84b-11ef-9310-92fbcf53809c.gif

動圖 run 堆疊

當一個新的 run 被識別并加入到棧中后,TimSort 會根據棧頂多個 run 的長度來判斷,是否應該合并棧頂附近的 run。

這個過程將持續進行,直到所有數據都遍歷完。

284bef4c-c84b-11ef-9310-92fbcf53809c.png

run 合并

遍歷結束后,棧中剩余的所有 run 每次兩兩合并,直到最終形成一個完整有序的 run。

相比傳統歸并排序,合并預排序的 run 會大大減少了所需的比較次數,從而提升了整體的排序效率。

現在,你可能對 TimSort 算法的細節產生了許多疑問。run 是如何形成的?這些 run 是如何利用數據中已存在的自然序列?當 run 被加入到棧中后,依據什么規則來決定是否合并?……

不用擔心,接下來我們將逐一解答這些問題,帶你更深入地理解 TimSort 算法。

計算 minrun

在 TimSort 算法中,run 的生成非常關鍵,而這一過程的核心是確定 run 最小長度 minrun。這個長度的設定是為了在排序過程中達到兩個關鍵目標:

確保 run 足夠長,以便有效地利用歸并排序;

避免 run 過于長,從而在合并時仍能保持高效。

實驗研究表明,當 minrun 小于 8 時,第一條原則難以滿足;而當 minrun 超過 256 時,第二條原則受到影響。

因此,最佳的 minrun 長度范圍被確定在 32 到 64 之間。

這個范圍與我們之前提到的插入排序中小規模數據集的長度范圍非常接近,這并非巧合。事實上,Timsort 在生成 run 時也會利用到插入排序。

具體計算 minrun 的方法如下:

目標:選取一個 minrun 值,以使長度為 n 的數組被分割成約 n/minrun 個 runs,每個 run 包含大約 32 到 64 個元素。

計算方法:選擇最接近 n/(2^k) 的 minrun 值,這里 k 是使 n/(2^k) 落在32至64之間的最大整數。然后設置 minrun 為 n/(2^k)。

例如,對于長度為 65 的數組,minrun 將設置為33,形成 2 個runs;對于長度為 165 的數組,minrun 設置為42,形成 4 個runs。

這個計算過程涉及到 (2^k),可以通過位移操作高效實現:

defget_minrun(n): #用于記錄在不斷右移過程中,n的最低位上非零位的數量 r=0 whilen>=64: #檢查n的最低位是否為1,若是,則設置r為1 r|=n&1 #向右移動一位,相當于n除以2 n>>=1 #返回n加上r,n是原始值的最高6位,r是表示過程中n是否有非零最低位的標志 returnn+r

這種方法不僅保證了 minrun 的有效性,而且利用了位運算的高效性,體現了 TimSort 設計的巧思。

run 的生成過程

在掌握了 minrun 的計算方法之后,我們現在可以探究 run 是如何生成的。

TimSort 的核心目標是充分利用數據中已存在的連續有序序列來生成 run,但這是如何實現的呢?

TimSort 的處理流程可分為以下幾個關鍵步驟:

TimSort 開始掃描整個數組,尋找連續的升序或降序序列。

如果遇到升序部分,TimSort 會持續掃描直到升序結束。

如果遇到降序部分,TimSort 會繼續掃描直到降序結束,并隨后將這部分翻轉成升序。

如果上述步驟識別的 run 未達到 minrun 長度,TimSort 會繼續擴展這個 run,向數組后方遍歷,納入更多元素,直至達 minrun 長度。在這個階段,新加入元素的順序并不重要。

一旦擴展完成,這個擴展后的 run(無論其最初是否有序)都將通過插入排序進行排序,以確保其內部有序。

如果識別的 run 長度遠超 minrun,對于這些較長的連續有序序列,TimSort 會保持其原始長度,不進行切割。這是因為較長的有序序列對于減少后續合并操作的復雜度非常有利。

對于這些超長的 run,通常無需進行額外排序,除非它們是降序,這時 TimSort 會先將其翻轉成升序。

通過這些策略,TimSort 能夠高效地生成一個有序的、長度至少為 minrun 的 run,為后續的歸并排序過程奠定了堅實基礎。

棧中 run 的合并規則

在 TimSort 算法中,每生成一個新的 run,它就會被加入到一個專門的棧中。

這時,TimSort 會對棧頂的三個 run(我們稱它們為X、Y和Z)進行檢查,以確保它們符合特定的合并規則:

|Z| > |Y| + |X|

|Y| > |X|

如果這些條件沒有被滿足,Y 就會與 X 或 Z 中較小的一個合并,并重新檢查上述條件。當所有條件都滿足時,可以在數據中繼續遍歷生成新的 run。

284bef4c-c84b-11ef-9310-92fbcf53809c.png

run 合并

這種獨特的合并規則是為了實現什么目標呢?

在 TimSort 的合并規則下,最終保留在棧中的每個 run 的長度至少等于前兩個 run 的總長度(由于滿足|Z| > |Y| + |X| 和 |Y| > |X|的規則)。

這種設計意味著,隨著時間的推移,棧中 run 的長度會逐漸增大,其增長方式類似于斐波那契數列。

這種增長模式的一個重要優勢在于,它提供了一種有效的方式來平衡數據遍歷完成之后 run 的合并操作,同時避免了過于頻繁的合并。

在最理想情況下,這個棧從頂部到底部 run 的長度應該是[2,2,4,8,16,32,64,...]。這樣,從棧頂到棧底的合并過程中,每次合并的兩個 run 的長度都是相等的,形成了完美的合并。

2875427a-c84b-11ef-9310-92fbcf53809c.png

棧中 run 最理想形態

通過這些巧妙的規則,TimSort 在保證合并操作近似均衡的同時,也確保了在追求均衡和簡化合并決策之間的權衡。

正如 Tim Peters 所指出的,找到一種方式來維持棧中這兩個規則,是一個極具智慧的折中選擇。

合并過程中的空間開銷

了解完 TimSort 的工作原理和 run 在棧中的合并規則之后,我們現在來看 TimSort 中的最后一個重要環節:如何高效地運用歸并排序?

雖然傳統的歸并排序也擁有 O(nlogn) 的時間復雜度,但它并不是原地排序,并且需要額外的 O(n) 空間開銷,這使得它并沒有被廣泛地運用。

當然,也有改良過的原地歸并排序的實現,但它們的時間開銷就會比較大。為了在效率和空間節約之間取得平衡,TimSort 采用了一種改進的歸并排序,其空間開銷遠小于O(n)。

以一個具體例子來說明:假設我們有兩個已排序的數組 [1, 2, 3, 6, 10] 和 [4, 5, 7, 9, 12, 14, 17],目標是將它們合并。

在這個例子中,我們可以觀察到:

第二個數組中的最小元素(4)需要插入到第一個數組的第四個位置以保持整體順序,

第一個數組中的最大元素(10)需要插入到第二個數組的第五個位置。

因此,兩個數組中的 [1, 2, 3] 和 [12, 14, 17] 已經位于它們的最終位置,無需移動。我們實際上需要合并的部分是 [6, 10] 和 [4, 5, 7, 9]。

在這種情況下,我們只需要創建一個大小為 2 的臨時數組,將[6, 10]復制到其中,然后在原數組中將它們與[4, 5, 7, 9]合并。

288b45a2-c84b-11ef-9310-92fbcf53809c.gif

動圖 歸并排序 優化合并過程

這個例子展示了從前往后的合并過程。同樣,還有從后往前合并的情況:

289eba9c-c84b-11ef-9310-92fbcf53809c.gif

動態圖 歸并排序 從后往前合并

與傳統歸并排序相比,TimSort 在這里采用的優化策略顯著減少了元素移動的次數,縮短了運行時間,并大幅降低了臨時空間的需求。

合并過程中的 galloping mode

在歸并排序過程中,通常的做法是逐個比較兩個數組中的元素,并將較小的元素依次放置到合適的位置。

然而,在某些情況下,這種方法可能涉及大量冗余的比較操作,尤其是當一個數組中的元素連續地勝出另一個數組時。

想象一下,如果我們有兩個極端不平衡的數組:

A = [1, 2, 3, …, 9999, 10000]

B = [20000, 20001, …, 29999, 30000]

在這種情況下,為了確定 B 中元素的正確插入點,我們需要進行高達 10000 次的比較,這無疑是低效的。

如何解決這個問題呢?

TimSort 的解決方案是引入了所謂的“躍進模式”(galloping mode)。這種模式基于一個假設:如果一個數組中的元素連續勝出另一個數組中的元素,那么這種趨勢可能會持續下去。

TimSort 會統計從一個數組連續選中的元素數量,一旦連續勝出次數達到了稱為 min_gallop 的閾值時,TimSort 就會切換到躍進模式。

在這種模式下,算法將不再逐個比較元素,而是將實施一種指數級搜索(exponential search)。以指數級的步長(2^k)進行跳躍,首先檢查位置 1 的元素,然后是位置 3 (1 + 2^1 ),接著是位置 7 (3 + 2^2),以此類推。

當首次找到大于或等于比較元素的位置時,我們就將搜索范圍縮小到上一步的位置(2^(k-1) + 1)和當前步的位置(2^k + 1)之間的區間。

在這個區間內進行更二分搜索,以快速定位正確的插入位置。

開發者的基準測試,只有當一個數組的首元素并不處于另一數組的前 7 位置時,躍進模式才真正帶來優勢,因此 min_gallop 的閾值為 7。

上面的步驟看起來比較復雜,我們以兩個數組為例:

A = [1, 25, 31, 37]

B = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36]

根據之前合并過程中的空間開銷原則,A 中的元素 1 是固定的,此時將25, 31, 37 移動到臨時空間進行合并排序。

28c00c92-c84b-11ef-9310-92fbcf53809c.gif

動圖 躍進模式 1

在這種情況下,當 25 在與 B 數組元素比較時連續勝出,觸發了躍進模式。

動圖 躍進模式 2

算法直接跳躍到位置 15 (7 + 2^3),發現 30 大于 25。

28db19ba-c84b-11ef-9310-92fbcf53809c.gif

動圖 躍進模式 3

進而在位置 7 和 15 之間執行二分搜索,以找到 25 的插入點。

28f9cfea-c84b-11ef-9310-92fbcf53809c.gif

動圖 躍進模式 4

雖然躍進模式在某些情況下能極大提高效率,但它并非總是最優選擇。有時,躍進模式可能導致更多的比較操作,尤其是在數據分布較為均勻時。

為了避免這種情況,TimSort采用了兩種策略:一是當識別到躍進模式的效率不及二分搜索時,會退出躍進模式;二是根據躍進模式的成功與否調整 min_gallop 值。

如果躍進模式成功且連續選擇的元素均來自同一數組,min_gallop 值會減 1,以鼓勵再次使用躍進模式;反之,則加 1,減少再次使用躍進模式的可能性。

結語:TimSort - 數據排序的實用革新

在探索數據排序這個歷史悠久且充滿挑戰的領域中,TimSort 算法不僅是一項技術成就,更是實用性與創新的杰出典范。它的出現,不單單是算法領域的一個新節點,更是對現實世界復雜數據處理需求的有效回應。

TimSort 的真正魅力不僅在于它的高效率,更在于它對實際數據特性的深入理解和利用。這個算法不是靜態的,它通過對數據的觀察,動態調整自身策略,以適應不同的數據模式。

這種設計思路提供了一個重要的啟示:在面對現實世界問題時,理論和實踐的結合往往比單純追求理論完美更為重要。

通過本文的深入分析,我們對 TimSort 的工作原理及其核心概念有了更為直觀的理解。現在,如果再次回顧它的定義,您會發現自己有了更深刻的認識。

參考資料

[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

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容侵權或者其他違規問題,請聯系本站處理。 舉報投訴
  • 函數
    +關注

    關注

    3

    文章

    4333

    瀏覽量

    62708
  • 排序算法
    +關注

    關注

    0

    文章

    53

    瀏覽量

    10080

原文標題:這么多年排序白學了,原來每次排序都在使用世界上最快的排序算法 TimSort

文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數據結構】歡迎添加關注!文章轉載請注明出處。

收藏 人收藏

    評論

    相關推薦

    HALArduino平臺上的使用

    HALArduino平臺上的使用 Arduino平臺是開源的電子原型平臺,它包括硬件(基于微控制器的電路板)和軟件(Arduino IDE)。Arduino平臺因其簡單易用而受
    的頭像 發表于 12-02 14:04 ?333次閱讀

    HAL標準的區別 HAL與CMSIS的關系

    嵌入式系統開發中,HAL(硬件抽象層)標準是兩種常用的軟件,它們功能和使用場景上有所
    的頭像 發表于 12-02 14:02 ?788次閱讀

    常用SQL函數及其用法

    SQL(Structured Query Language)是種用于管理和操作關系數據的編程語言。SQL 提供了豐富的函數庫,用于數據檢索、數據更新、數據刪除以及數據聚合等操作。以下是
    的頭像 發表于 11-19 10:18 ?304次閱讀

    時間復雜度為 O(n^2) 的排序算法

    , O(n2) 的排序算法可能會比 O(nlogn) 的排序算法執行效率高。不過隨著數據規模增大, O(nlogn) 的排序
    的頭像 發表于 10-19 16:31 ?1176次閱讀
    時間復雜度為 O(n^2) 的<b class='flag-5'>排序</b><b class='flag-5'>算法</b>

    怎么TMDSEVM6678: 6678自帶的FFT接口和CUDA提供CUFFT函數庫選擇?

    請教下gpgpu上包括4Riscv cpu和DPU, 沒有6678,要替換原來信號處理用的6678,該怎么6678自帶的FFT接
    發表于 09-27 07:20

    為什么水文計算中廣泛采用配線法

    水文計算中廣泛采用配線法(或稱適線法),主要基于以下幾個方面的原因: 、理論依據堅實 配線法以經驗頻率點據為基礎,通過求解與經驗點據擬合最優的頻率曲線參數,從而估計水文要素總體的統計規律。這種
    的頭像 發表于 09-19 16:10 ?460次閱讀

    利用vMeasure eMobilityAnalyzer函數庫分析電機性能

    本文利用vMeasure eMobilityAnalyzer函數庫中的克拉克變換功能,將三相電機定子電流或電壓轉換為兩相電流或電壓,幫助工程師更有效地、可視化地分析電機的行為并對控制算法進行針對性的優化,從而提高電機的性能和效率。
    的頭像 發表于 09-13 11:37 ?407次閱讀
    利用vMeasure eMobilityAnalyzer<b class='flag-5'>函數庫</b>分析電機性能

    手把手教你排序算法怎么寫

    今天以直接插入排序算法,給大家分享一下排序算法的實現思路,主要包含以下部分內容:插入排序介紹插入排序
    的頭像 發表于 06-04 08:03 ?709次閱讀
    手把手教你<b class='flag-5'>排序</b><b class='flag-5'>算法</b>怎么寫

    使用STM32FEBKC6T6開發FOC,如何使用函數庫

    本人使用STM32FEBKC6T6 開發FOC,但是,不知道如何使用她的函數庫ST Motor Control Workbench 4.0中生成《stm32f30x_MC_it.c文件》里面
    發表于 05-15 08:22

    CMSIS的DSP數字信號處理函數庫應用

    為了使用DSP數據,需要在IAR開發環境中,對工程文件選項General中的連接設置中,選擇CMSIS DSP。程序中增加arm math頭文件即可。
    發表于 03-25 10:52 ?1488次閱讀
    CMSIS的DSP數字信號處理<b class='flag-5'>函數庫</b>應用

    用FPGA實現雙調排序的方法(2)

    典型的排序算法包括冒泡排序、選擇排序、插入排序、歸并排序、快速
    的頭像 發表于 03-21 10:28 ?648次閱讀
    用FPGA實現雙調<b class='flag-5'>排序</b>的方法(2)

    FPGA實現雙調排序算法的探索與實踐

    雙調排序(BitonicSort)是數據獨立(Data-independent)的排序算法,即比較順序與數據無關,特別適合并行執行。了解雙調排序
    發表于 03-14 09:50 ?663次閱讀
    FPGA實現雙調<b class='flag-5'>排序</b><b class='flag-5'>算法</b>的探索與實踐

    TC264有矩陣或三角函數的加速嗎?

    illd 上搜索了很長時間,并使用了 Google 等搜索引擎。我似乎沒有找到矩陣或相關的三角函數庫。不過,我倒是找到了類似于 a
    發表于 03-05 07:47

    C語言實現經典排序算法概覽

    冒泡排序(英語:Bubble Sort)是種簡單的排序算法。它重復地走訪過要排序的數列,次比
    的頭像 發表于 02-25 12:27 ?459次閱讀
    C語言實現經典<b class='flag-5'>排序</b><b class='flag-5'>算法</b>概覽

    開源的hbird-e-sdk中,怎么用軟件實現三角函數的計算,有沒有數學函數庫可以調用?

    想請問開源的hbird-e-sdk中,怎么用軟件實現三角函數的計算,有沒有數學函數庫可以調用?類似于“math.h”
    發表于 01-10 07:06
    主站蜘蛛池模板: 亚洲精品在线网址| 香蕉久久夜色精品国产小优| 青草久久伊人| 18黄女脱内衣| 久久精品天天中文字幕| 亚洲 日韩 色 图网站| 国产AV精品久久久免费看| 漂亮妈妈中文字幕版| 99精品视频在线观看免费| 美女搜查官被高难度黑人在线播放| 婬香婬色天天视频| 久久99精品久久久久久园产越南| 亚洲 欧洲 国产 日产 综合| 国产精品自在在线午夜蜜芽tv在线| 无码内射成人免费喷射| 国产伦精品一区二区三区免费观看 | 亚洲乱码日产精品BD在线下载| 国家产午夜精品无人区| 亚洲青青草原| 久久热在线视频精品店| 91情国产l精品国产亚洲区| 免费看国产精品麻豆| gogogo免费视频观看| 四虎免费影院| 交换娇妻呻吟声不停中文字幕| 伊人久久大香线蕉观看| 榴莲黄版无限刷| 白洁在线观看| 性盈盈剧场| 久久精品免费看网站| 97在线视频免费播放| 日韩精品欧美在线视频在线| 国产AV精品无码免费看| 亚洲精品国产自在在线观看| 久热人人综合人人九九精品视频| 97欧美精品大香伊蕉在人线| 秋霞伦理电影在2017韩国在线伦| 国产白色视频在线观看w| 亚洲精品另类有吗中文字幕| 玖玖在线精品| 国产69精品久久久久乱码|