Python sort 的實(shí)現(xiàn) - Timsort 算法
https://www.aliyun.com/jiaocheng/432919.html
摘要：近日閱讀編程珠璣,對算法突然又萌生了興趣,于是翻看資料查找到了Python的排序算法概述Timsort是Pythonbulitinsort所使用的一種算法,結(jié)合了歸并排序與插入排序。最優(yōu)時(shí)間復(fù)雜度為n,最差時(shí)間復(fù)雜度為nlogn,平均時(shí)間復(fù)雜度同為nlogn,空間復(fù)雜度為n,并且是穩(wěn)定排序。Java中對于非基礎(chǔ)類型的排序也是使用的這個(gè)算法各種排序算法時(shí)間/空間復(fù)雜度可以從Sortingalgorithm中得到Python排序代碼在源碼包的Objects/listobject.
近日閱讀編程珠璣,對算法突然又萌生了興趣,于是翻看資料查找到了 Python 的排序算法
概述?
Timsort 是 Python bulitin sort 所使用的一種算法,結(jié)合了歸并排序與插入排序。最優(yōu)時(shí)間復(fù)雜度為n
, 最差時(shí)間復(fù)雜度為nlogn
, 平均時(shí)間復(fù)雜度同為nlogn
, 空間復(fù)雜度為n
,并且是穩(wěn)定排序。Java 中對于非基礎(chǔ)類型的排序也是使用的這個(gè)算法
各種排序算法時(shí)間/空間復(fù)雜度可以從Sorting algorithm
中得到
Python 排序代碼在源碼包的Objects/listobject.c
中,個(gè)人看了感覺十分難懂,遂轉(zhuǎn)而去尋找 Java 的算法實(shí)現(xiàn),根據(jù)蠢作者還在使用的 Java7 來說,位于/usr/lib/jvm/openjdk-7/src.zip
中。如果你的 Linux 沒有這個(gè)目錄則需要apt-get install openjdk-7-source
算法實(shí)現(xiàn)?
如無特殊說明,代碼均引自 TimSort.java 中的 TimSort 類, 并將比較器,泛型等去除,修改為直接比較 int 類型
Timsort 認(rèn)為真實(shí)世界的數(shù)據(jù)看似無序?qū)崉t存在或長或短的有序片段,它將這些片段稱為run
,如[2, 3, 5, 4, 9]
中的[2, 3, 5]
和[4, 9]
。它遍歷數(shù)組盡可能尋找這些run
// 此方法被多次調(diào)用,用于尋找 run?
private static int countRunAndMakeAscending(int[] a, int lo, int hi?
) {?
assert lo < hi;?
int runHi = lo + 1;?
if (runHi == hi)?
return 1;?
// 根據(jù)前兩個(gè)元素的比較,判斷具有升序趨勢還是降序趨勢?
if (a[runHi++]
while (runHi < hi &;&; a[runHi]
runHi++;?
// 降序轉(zhuǎn)換成升序?
reverseRange(a, lo, runHi);?
} else {?
while (runHi < hi &;&; a[runHi]>=a[runHi - 1])?
runHi++;?
}?
// 返回自然有序部分的長度?
return runHi - lo;?
}?
run
不能過短,存在一個(gè)minRun
,這個(gè)值是根據(jù)列表長度生成的
private static int minRunLength(int n) {?
assert n >= 0;?
int r = 0;// Becomes 1 if any 1 bits are shifted off?
while (n >= MIN_MERGE) {// MIN_MERGE = 32Python 中為 64?
r |= (n &; 1);?
n >>= 1;?
}?
return n + r;?
}?
有序部分的長度一般不會(huì)太長,當(dāng)小于minRun
時(shí),會(huì)將此部分后面的元素插入其中,直至長度滿足minRun
private static void binarySort(int[] a, int lo, int hi, int start?
) {?
// lo 為 run 的起始位置?
// hi 為 run 應(yīng)該結(jié)束的位置 (即 run 的起始位置 + minRun)?
// start 當(dāng)前有序部分的結(jié)束位置 (start 后的元素需要插入至 run 中)?
assert lo <= start &;&; start <= hi;?
if (start == lo)?
start++;?
for ( ; start < hi; start++) {?
int pivot = a[start];?
// Set left (and right) to the index where a[start] (pivot) belongs?
int left = lo;?
int right = start;?
assert left <= right;?
/*?
* Invariants:?
* pivot >= all in [lo, left).?
* pivot
*/?
// 通過二分法查找元素應(yīng)當(dāng)出現(xiàn)的位置?
while (left < right) {?
int mid = (left + right) >>> 1;?
if (pivot < a[mid])?
right = mid;?
else?
left = mid + 1;?
}?
assert left == right;?
int n = start - left;// The number of elements to move?
// 將位置后的元素向后移動(dòng)一個(gè)位置?
// 在元素和要插入的位置很近時(shí),避免使用 arraycopy?
switch (n) {?
case 2:a[left + 2] = a[left + 1];?
case 1:a[left + 1] = a[left];?
break;?
default: System.arraycopy(a, left, a, left + 1, n);?
}?
// 插入元素?
a[left] = pivot;?
}?
}?
滿足長度要求的run
會(huì)被 push 至一個(gè) stack, Java 中的具體實(shí)現(xiàn)為調(diào)用了pushRun
方法然后將起始位置和長度存入兩個(gè)數(shù)組(棧)中
private void pushRun(int runBase, int runLen) {?
// runBase 為 run 的起始位置?
// runLen為 run 的長度?
this.runBase[stackSize] = runBase;// stackSize 初始為 0?
this.runLen[stackSize] = runLen;?
stackSize++;?
}?
并且每次 push 后會(huì)調(diào)用mergeCollapse
方法,檢查下面這兩個(gè)條件是否滿足。若不滿足會(huì)進(jìn)行歸并排序,直至滿足條件為止
// i 為棧的大小?
1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]?
2. runLen[i - 2] > runLen[i - 1]?
可以直觀的表述為 // (X Y Z 為 runLen)?
| Z |<- top?
| Y |?
| X |<- bottom?
-----?
1. X > Y + Z?
2. Y > Z?
當(dāng)然,如果已經(jīng)遍歷完數(shù)組找出了所有的run
,也會(huì)進(jìn)行歸并
代碼如下
private void mergeCollapse() {?
while (stackSize > 1) {?
int n = stackSize - 2;?
if (n > 0 &;&; runLen[n-1] <= runLen[n] + runLen[n+1]) {?
// [n-1] [n] [n+1]?
// run[n] 和更小的那個(gè)進(jìn)行 merge?
if (runLen[n - 1] < runLen[n + 1])?
n--;?
// 對 run[n] 和 run[n+1] 進(jìn)行 merge?
mergeAt(n);?
} else if (runLen[n] <= runLen[n + 1]) {?
mergeAt(n);?
} else {?
break; // Invariant is established?
}?
}?
}?
歸并排序使用了一些特殊的技巧
1) 在run1
中找run2
最小元素的位置
2) 在run2
中找run1
最大元素的位置
充分利用了兩個(gè)run
是順序存儲(chǔ)且相鄰的特點(diǎn),縮小了排序的范圍
(1, 3, { 5, 7,) (4, 5, 6, } 10, 12)
()
中為兩個(gè)run
{}
中為真正需要排序的部分
private void mergeAt(int i) {?
assert stackSize >= 2;?
assert i >= 0;?
assert i == stackSize - 2 || i == stackSize - 3;?
// run1 的起始位置?
int base1 = runBase[i];?
int len1 = runLen[i];?
// run2 的起始位置?
int base2 = runBase[i + 1];?
int len2 = runLen[i + 1];?
assert len1 > 0 &;&; len2 > 0;?
// 在數(shù)組中連續(xù)?
assert base1 + len1 == base2;?
// 修改 runLen[i] 的長度為合并后的長度?
runLen[i] = len1 + len2;?
// 若合并的是相對于棧頂 2rd 和 3rd 的 run 需要將棧頂向下移動(dòng)一個(gè)單位?
// | Z |<- top?
// | Y |?
// | X |<- bottom?
if (i == stackSize - 3) {?
runBase[i + 1] = runBase[i + 2];?
runLen[i + 1] = runLen[i + 2];?
}?
stackSize--;?
/*?
* Find where the first element of run2 goes in run1. Prior elements?
* in run1 can be ignored (because they're already in place).?
*/?
int k = gallopRight(a[base2], a, base1, len1, 0);?
assert k >= 0;?
// base1 至 base1 + k 的元素為兩個(gè) run 公共最小,不需要參與排序?
base1 += k;?
len1 -= k;?
// run1 即為公共最小,不需要再進(jìn)行排序?
if (len1 == 0)?
return;?
/*?
* Find where the last element of run1 goes in run2. Subsequent elements?
* in run2 can be ignored (because they're already in place).?
*/?
// base2 + len2 后的元素為兩個(gè) run 公共最大,不需要參與排序?
len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1);?
assert len2 >= 0;?
// run2 即為公共最大,不需要再進(jìn)行排序?
if (len2 == 0)?
return;?
// Merge remaining runs, using tmp array with min(len1, len2) elements?
if (len1 <= len2)?
mergeLo(base1, len1, base2, len2);?
else?
mergeHi(base1, len1, base2, len2);?
}?
gallop
是一種經(jīng)過優(yōu)化的二分查找,會(huì)通過倍增邊界縮小二分查找的范圍,gallopLeft
和gallopRight
實(shí)現(xiàn)相似
private int gallopLeft(int key, int[] a, int base, int len, int hint?
) {?
// key 為準(zhǔn)備插入的元素?
// hint 為開始查找的偏移?
assert len > 0 &;&; hint >= 0 &;&; hint < len;?
int lastOfs = 0;?
int ofs = 1;?
// key 比 a[base + hint] 小,倍增 ofs = 1, 3, 7, 2^n-1 使得?
// key > a[base + hist - ofs ]?
// key 比 a[base + hint] 大,倍增 ofs = 1, 3, 7, 2^n-1 使得?
// key < a[base + hist + ofs ]?
if (key > a[base + hint]) {?
// Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]?
int maxOfs = len - hint;?
while (ofs < maxOfs &;&; key > a[base + hint + ofs]) {?
lastOfs = ofs;?
// 1, 3, 7, 2^n-1?
ofs = (ofs << 1) + 1;?
if (ofs <= 0) // int overflow?
ofs = maxOfs;?
}?
if (ofs > maxOfs)?
ofs = maxOfs;?
// Make offsets relative to base?
lastOfs += hint;?
ofs += hint;?
} else { // key <= a[base + hint]?
// Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]?
final int maxOfs = hint + 1;?
while (ofs < maxOfs &;&; key <= a[base + hint - ofs]) {?
lastOfs = ofs;?
ofs = (ofs << 1) + 1;?
if (ofs <= 0) // int overflow?
ofs = maxOfs;?
}?
if (ofs > maxOfs)?
ofs = maxOfs;?
// Make offsets relative to base?
// 負(fù)向偏移,交換順序?
int tmp = lastOfs;?
lastOfs = hint - ofs;?
ofs = hint - tmp;?
}?
assert -1 <= lastOfs &;&; lastOfs < ofs &;&; ofs <= len;?
// lastofs = base + 2^(n-1)-1?
// ofs = 2^n-1?
// a[base+lastOfs] < key <= a[base+ofs], 在 base+lastOfs-1到 base+ofs 范圍內(nèi)執(zhí)行二分查找?
// 確認(rèn) key 應(yīng)當(dāng)插入的位置?
lastOfs++;?
while (lastOfs < ofs) {?
int m = lastOfs + ((ofs - lastOfs) >>> 1);?
if (key>a[base + m])?
lastOfs = m + 1;// a[base + m] < key?
else?
ofs = m;// key <= a[base + m]?
}?
assert lastOfs == ofs;// so a[base + ofs - 1] < key <= a[base + ofs]?
return ofs;?
}?
歸并排序的實(shí)現(xiàn)大致可以理解為將run1
移入一個(gè)臨時(shí)的數(shù)組空間,然后和run2
進(jìn)行逐個(gè)比較,將較小的元素移入run1 + run2
這個(gè)空間中
private void mergeLo(int base1, int len1, int base2, int len2) {?
assert len1 > 0 &;&; len2 > 0 &;&; base1 + len1 == base2;?
// Copy first run into temp array?
int[] a = this.a; // For performance?
// 申請臨時(shí)數(shù)組空間,并將 run1 復(fù)制進(jìn)去?
int[] tmp = ensureCapacity(len1);?
System.arraycopy(a, base1, tmp, 0, len1);?
int cursor1 = 0;// Indexes into tmp array?
int cursor2 = base2; // Indexes int a?
int dest = base1;// Indexes int a?
// Move first element of second run and deal with degenerate cases?
a[dest++] = a[cursor2++];?
// 若 run2 只有一個(gè)元素,將臨時(shí)數(shù)組中的元素拷貝到后面即可?
if (--len2 == 0) {?
System.arraycopy(tmp, cursor1, a, dest, len1);?
return;?
}?
// 若 run1 只有一個(gè)元素,將 run2 的元素全部前移,然后添加 run1 中的元素?
if (len1 == 1) {?
System.arraycopy(a, cursor2, a, dest, len2);?
a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge?
return;?
}?
// Use local variable for performance?
// minGallop = 7?
int minGallop = this.minGallop;//"" " ""?
outer:?
while (true) {?
int count1 = 0; // Number of times in a row that first run won?
int count2 = 0; // Number of times in a row that second run won?
/*?
* Do the straightforward thing until (if ever) one run starts?
* winning consistently.?
*/?
// 對 run1 和 run2 進(jìn)行 merge?
do {?
assert len1 > 1 &;&; len2 > 0;?
if (a[cursor2] < tmp[cursor1]) {?
a[dest++] = a[cursor2++];?
count2++;?
count1 = 0;?
if (--len2 == 0)?
break outer;?
} else {?
a[dest++] = tmp[cursor1++];?
count1++;?
count2 = 0;?
if (--len1 == 1)?
break outer;?
}?
// WTF 這個(gè)相當(dāng)于 count1 < minGallop &;&; count2 < minGallop?
// 因?yàn)?count1 或 count2 總有一個(gè)為 0?
// 如果在這里跳出說明遇到了某一個(gè) run 中連續(xù)存在比另一個(gè) run 的某個(gè)元素大的情況?
} while ((count1 | count2) < minGallop);?
/*?
* One run is winning so consistently that galloping may be a?
* huge win. So try that, and continue galloping until (if ever)?
* neither run appears to be winning consistently anymore.?
*/?
// 再次利用 gallop 縮小范圍?
do {?
assert len1 > 1 &;&; len2 > 0;?
count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0);?
if (count1 != 0) {?
System.arraycopy(tmp, cursor1, a, dest, count1);?
dest += count1;?
cursor1 += count1;?
len1 -= count1;?
if (len1 <= 1) // len1 == 1 || len1 == 0?
break outer;?
}?
a[dest++] = a[cursor2++];?
if (--len2 == 0)?
break outer;?
count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0);?
if (count2 != 0) {?
System.arraycopy(a, cursor2, a, dest, count2);?
dest += count2;?
cursor2 += count2;?
len2 -= count2;?
if (len2 == 0)?
break outer;?
}?
a[dest++] = tmp[cursor1++];?
if (--len1 == 1)?
break outer;?
minGallop--;?
} while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);?
if (minGallop < 0)?
minGallop = 0;?
minGallop += 2;// Penalize for leaving gallop mode?
}// End of "outer" loop?
this.minGallop = minGallop < 1 ? 1 : minGallop;// Write back to field?
if (len1 == 1) {?
assert len2 > 0;?
System.arraycopy(a, cursor2, a, dest, len2);?
a[dest + len2] = tmp[cursor1]; //Last elt of run 1 to end of merge?
} else if (len1 == 0) {?
throw new IllegalArgumentException(?
"Comparison method violates its general contract!");?
} else {?
assert len2 == 0;?
assert len1 > 1;?
System.arraycopy(tmp, cursor1, a, dest, len1);?
}?
}?
補(bǔ)充一點(diǎn)在 Java 版本的 Timsort 中,如果當(dāng)數(shù)組的元素小于MIN_MERGE
(32) 個(gè)時(shí),會(huì)執(zhí)行一個(gè)簡化版本 mini-TimSort。直接找出第一個(gè)run
然后將剩下的元素通過binarySort
方法插入進(jìn)去
流程示例?
無視 mini-TimSort
原始待排數(shù)組
[3, 6, 8, 9, 15, 13, 11, 7, 42, 58, 100, 22, 26, 39, 38, 43, 50]?
minRunLength
為 9,遍歷可得第一個(gè)有序部分為[3, 6, 8, 9, 15]
,長度小于minRunLength
。所以將后面的 4 個(gè)元素通過二分法找到其在有序部分的位置然后插入得到run1
[3, 6, 7, 8, 9, 11, 13, 15, 42]
。入棧后檢查約束條件,因?yàn)榇藭r(shí)棧中只有一個(gè)元素,所以條件滿足。之后,尋找第二個(gè)run
得到[22, 26, 38, 39, 43, 50, 58, 100]
。入棧后條件雖然滿足,但是因?yàn)橐呀?jīng)遍歷至數(shù)組尾部。所以需要執(zhí)行最終的歸并
gallopLeft
比較run1
和run2
的末尾元素 42 和 100 通過倍增縮小邊界oft = 1
比較 42 和 58oft = 3
比較 42 和 43oft = 7
比較 42 和 22
確定應(yīng)當(dāng)在[22, 26, 38, 39, 43]
中進(jìn)行二分查找
gallopRight
同理
可得實(shí)際需要進(jìn)行歸并排序的范圍如下{}
所示
[3, 6, 7, 8, 9, 11, 13, 15,{ 42, 22, 26, 38, 39,} 43, 50, 58,} 100]?
然后將 42 拷貝至tmp
中,比較,歸并
本文配合下面影片食用更佳
以上是Python sort 的實(shí)現(xiàn) - Timsort 算法的內(nèi)容，更多?算法?Timsort?實(shí)現(xiàn)?Python?sort?的內(nèi)容，請您使用右上方搜索功能獲取相關(guān)信息。
