跳到主要內容區塊

計資中心電子報C&INC E-paper

技術論壇

Python小技巧:Python中的list排序演算法
  • 卷期:v0068
  • 出版日期:2024-03-20

作者:周秉誼 / Tomofun 資深技術經理


排序(Sorting)是一個最基本也是最常被使用的演算法,幾乎所有的程式語言都有提供排序的函式。在目前官方的CPython中,list的排序演算法從2.3版之後改為使用Timsort。本文將分享Timsort的中心概念及CPython中Timsort的幾個最佳化技巧,說明為什麼Timsort會是大家認為最適合Python的排序演算法。

 

前言

Python是非常容易學習的程式語言,不只可以運用在日常工作的自動化,也可以作為網路服務的後端(Backend)程式,也有豐富的標準函式庫(Python Standard Library)和套件(Package),使得Python成為多種使用情境下都可以使用的程式語言。

除了友善的學習曲線之外,Python也在彈性和程式效能之間達到平衡。排序(Sorting)是一個最基本也是最常被使用的演算法,幾乎所有的程式語言都有提供排序的函式可供程式設計人員使用,因應各個程式語言的特性,不同語言的排序函式也會採用不同的排序演算法。如C語言stdlib中的qsort()函式是使用Quick Sort演算法,C++語言STL中的std::sort()函式是使用Introsort等等。在目前官方的CPython中,list的排序函式則是使用了Timsort排序演算法。

 

排序演算法性質

不同的排序演算法會有不同的特性,通常會從幾個面向來探討,包括了時間複雜度 (Time complexity)、空間複雜度(Space complexity)、穩定性 (Stability)、自適應排序(Adaptive sort)等。時間複雜度用來評量排序演算法處理大量資料時所需要的時間,一般以比較(Comparison)為主的排序演算法的時間複雜度多為O(nlogn)或O(n^2),從時間複雜度可以了解花費的時間隨資料量上升時的變化,時間複雜度又可以分為最佳時間(Best time)、平均時間(Average time)和最差時間(Worst time)三個面向。空間複雜度可以視為額外的記憶體使用量,一般排序演算法多為O(1)、O(logn)或O(n)。穩定性指的是相同大小的不同物件在排序之後,可不可以維持原本在陣列中的前後關係,如果可以則稱這個排序演算法是穩定的(Stable),反之則是不穩定的(Unstable),穩定的排序演算法通常會有較好的使用性,但也要花費較多的計算和記憶體成本。自適應排序法可以利用陣列中已經排序好的特性,減少所需要的計算時間,而有較佳的最佳計算時間。

 

 

Best time

Average time

Worst time

Space

Stable

Quick Sort

O(n log n)

O(n log n)

O(n^2)

O(log n)

No

Merge Sort

O(n log n)

O(n log n)

O(n log n)

O(n)

Yes

Introsort

O(n log n)

O(n log n)

O(n log n)

O(log n)

No

Insertion sort

O(n)

O(n^2)

O(n^2)

O(1)

Yes

Timsort

O(n)

O(n log n)

O(n log n)

O(n)

Yes

圖1.排序演算法比較

 

Timsort

Timsort是由Tim Peters在2002年時開發出來,在Python 2.3版之後,就取代原有的Samplesort,成為Python內建的排序演算法。Timsort是混合了合併排序法(Merge Sort)及插入排序法(Insertion Sort)的一種混合排序法(Hybrid sorting),也是一種穩定排序法及自適應排序法。經過分析和實際測試,Timsort在多種日常常見的情境當中有非常好的效能,也有其他程式語言採用。Timsort的中心概念有兩個部份,首先將資料分成一個個minrun大小的run,對每個run以插入排序法進行排序;再將各個排序好的run以類似合併排序法的合併過程合併後,就完成陣列的排序了。

 

timsort(a, n):
 for (i=0;i<n;i+=MINRUN)
   insertion_sort(a, i, i+MINRUN);
 for (runsize=MINRUN;runsize<n;runsize*=2) {
     for (left=0;left<n;left+=2*runsize) {
         mid = left + runsize -1;
         right = left + 2*runsize -1;
         merge(a, left, mid, right);
     }
 }

圖2.Timsort排序演算法

 

Timsort最佳化技巧

除了基本的中心概念之外,CPython中的Timsort還做了幾個不同的技巧來加速排序,包括minrun大小的最佳化、以Binary Insertion Sort取代插入排序法、節省Merge時的記憶體使用等等。

在CPython的Timsort中,minrun的大小是由陣列的大小n來計算出來的,介於32和64之間,選擇一個令n/minrun等於二冪次方的minrun;如果無法剛好等於,就選小於二冪次方中最接近的一個minrun。而如果n小於64,則直接以n做為minrun來進行插入排序。

對每個run使用插入排序法是Timsor的一個關鍵,雖然在演算法分析上插入排序法平均的時間複雜度是O(nlogn),但是插入排序法有良好的自適應特性,對已有部份排序的資料可以提升到O(kn),而且在小資料量的情況之下,其他排序演算法的計算成本很難低於插入排序法。而CPython的Timsort更使用Binary Insertion Sort取代插入排序法,最主要的原因就是要節省比較的次數。Binary Insertion Sort是使用二元搜尋(Binary search)花費O(logn)的比較來找到插入的位置,相較於插入排序法是使用線性搜尋(Linear search)花費O(n)的比較,但在插入後都是要做O(n)次的資料搬移。這個特性剛好在Python中十分有利,因為Python的list中的每一個元素都是一個物件,這些物件的型別(Typing)可能非常不同,因此一個基本的比大小就需要大量的計算成本;相對來說,list中的物件搬移就只是C語言中指標(Pointer)的搬移,比起不同型別間的比大小要單純得多了。所以節省比較次數是CPython的Timsort能有較佳效能的一個關鍵。

要在合併排序中以線性時間、不花費額外記憶體進行合併,在理論上是做得到,但實務上計算的成本會非常高。因此CPython的Timsort在進行合併的時候還是會使用到額外的記憶體當暫存空間,但是在合併相鄰的A、B兩個run時搬移之前,會先在A run中搜尋B[0]的位置A[x],則A[0:x-1]元素都不需要搬移,相似的做法也可以應用在B run中搜尋A[-1]的位置B[y],則B[y+1:-1]間的元素也已經在正確的位置上了。

 

結語

在CPython的程式碼中,留有Timsort作者Tim Peters在開發Timsort時的實驗結果,針對隨機序列、遞增序列、遞減序列、幾乎排序好的序列等各種輸入序列的情境進行測試,結果中發現Timsort對於幾乎排序好的序列,比起原本的Samplesort節省了非常多的比較次數。總結來說,CPython的Timsort是一個以節省比較次數來提高效能的排序演算法,這個特性在Python的list排序中,可以省去大量未知型別物件間的比較,進而提升排序的效能。這也是為什麼Timsort會是目前大家認為最適合Python的排序演算法。

 

參考資料