contributed by < fennecJ
>
程式參考 Optimized QuickSort — C Implementation (Non-Recursive) 的作法,將給定的 list 分為 pivot, 比 pivot 小的 left list 以及比 pivot 大的 right list 。假設我們有一個 list 如下:
經過第一次 partition 後,原本的 list 被分成三個 sub list:
再來將 L, pivot, R 三個 list 的 begin 和 end 分別存入 begin[i~i+2], end[i~i+2] ,然後更新 L, R 到 begin[i+2], end[i+2] 為新的 sublist (在此為 R 這個 sublist)。對每個 sublist 用同樣的作法進行切分,直到 L = R,表示這是處理好的 list ,將其加入 result 。最後直到 i = 0 ,表示所有 sublist 都被處理完畢,離開迴圈即完成整個 list 的 sorting 。
由於我們可以透過 list_tail() 從 begin 走到 end,因此我們不需要 end[] 陣列,從而免去 node_t
指標陣列的使用:
commit f335fa
如此可大幅降低記憶體開銷。
commit 688f9f
將原本的 node_t
structure 改寫為:
並透過 list_entry
存取 node_t
的內容。
commit 369848
在研讀第一週測驗題之 Timsort 時,發現該題用了一個小技巧:
在建立 run 的同時計算 run_size 並將 run_size 存在 head->next->prev
,由於目前實作的 quick sort 不會需要用到 prev link ,因此我們可以在建立 R/L sublist 時將其對應的 tail 存在 list 的 head->prev
,如此只要透過 begin[i]->prev 即可得到 sublist 的 tail :
不過要留意有時候 right/left 本身可能會是 NULL ,因此在存取 right->prev
, left->prev
, R->prev
時需要先確認指標本身不是 NULL 以免遇到 segmentation fault
比較改進前後的時間差距:
commit 706b3a
比較對長度為 100000 的 list 進行 40 次排序的時間差距:
可以看到有 的時間改進。
我也比較了長度為 10 的陣列的所有排列 (詳見文末 Misc) :
有 的時間改進。
Timsort 可視為 merge sort 的改進。
commit 19897f
研讀 Timsort 的運作原理時,發現了 yanjiew1 的實作,裡面提到了 Timsort 的額外兩個變體: Adaptive Shivers Sort 以及 powersort
Adaptive Shivers Sort 改良了 Timsort 的合併策略:假設 X, Y, Z 為目前堆疊上的 Runs ,Z 為堆疊頂部 ,若 ,則將 X, Y 合併。
我們可以透過 __built_in_clz()
快速計算 log2:
修改原本的 merge_collapse 並藉由 ilog2 實作出 adaptive ShiversSort 的合併策略:
PowerSort 是另一種 Timsort 的改良,其主要概念為想像一個平衡的 binary tree 每個節點構成的 subtree 含有多少數量的節點,之後計算出目前要排序的 2 個 run 的中點連線後包含在此區間內的最小節點深度為何,在論文中將 2 個 run 對應的節點深度稱為 power,並根據後者決定是否要合併 。
留意以下說明中起點 index 設為 0,但我後來檢視其實作將起點設為 1 較合理:論文中的實作有 - (left << 1)
,若 left 為 1 的話恰好和虛擬碼計算除法時上下同乘 2 吻合(詳見文後的 虛擬碼和參考實作 )
假設我們現在有長度為 28 的 list 需要排序,我們先想像其對應的 binary tree 為何:
因此我們可以想像一個深度為 4 的 binary tree ,分別有 power 1, 2, 3, 4
假設我們有 6 個 run {a, b, c, d, e, f},每個 run_size 分別為:
5, 3, 3, 14, 1, 2
則我們可以開始想像他們合併後的 power 為何,首先看前兩個 run {a, b} 合併後的 power。
第一個 run {a} 的 index 為 0, 1, 2, 3, 4
第二個 run {b} 的 index 為 5, 6, 7
計算中點的公式為:
這兩個 run 的中點分別為:
而這兩點的連線則為 (2, 6] 的區間,留意左側是開區間,不包含 2 ;而右側是閉區間,包含 6 。我們現在依序由淺到深檢視。
不同深度的 node 可表示為:
其中 n 為 list 總長度,在這裡 n 為 28
深度為 1
,index 14 並未包含在 (2, 6] 的區間。
深度為 2
在 binary tree 中,有兩個深度為二的節點:
分別是 index 7 和 index 21
index 7 和 21 皆並未包含在 (2, 6] 的區間。
深度為 3
,深度為三的 index 有:
7 - 3.5 = 3.5
7 + 3.5 = 10.5
21 - 3.5 = 17.5
21 + 3.5 = 24.5
其中 index 3.5 被包含在 (2, 6] 的區間。
因此 run {a, b} 之間的 power 就是 3 。
接下來看 run {b, c} 之間的 power 。
c 的座標為 8~10
根據前述計算, run {b} 的中點為 6 , run{c} 的中點為:
而這兩點的連線則為 (6, 9] 的區間。包含深度為 2 的 index 7 ,可知其 power 為 2 。
之後依序計算出每個 run 的中點:
因此
, ( 9, 18] 涵蓋 14
, (18, 25] 涵蓋 24.5
, (25, 27] 不在深度 1 ~ 3 的範圍內,因此為最大深度 4 。
影片 COMP526 (Fall 2023) 3-6 §3.6 Python's sorting method & Powersort 的後半部分以視覺化的方式呈現前述運算。
現在我們檢視 PowerSort 對應的虛擬碼:
〈Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs〉提出能透過 bitwise 運算用 O(1) 時間計算出 power 的作法:
其中 left 和 right 表示要排序的起點和終點,用來計算這次排序的長度為何用以推估 binary tree 的深度 。而我們的排序固定是整個 list ,因此可以將 left, right 用一個變數 len 取代,到時候只要傳入 list 的長度即可。
以下解釋這個程式碼為何和虛擬碼等效,檢視前述虛擬碼,可以看到 a, b 的計算公式為:
其中 i1, i2 為 list1, list2 的起點,也就是 start_A
和 start_B
; n1, n2 為 list1, list2 的長度; n 為整個要排序的 list 的長度。
我們將計算 a, b 的公式上下同乘 2 :
而 a, b 可對應論文實作中的 l, r
注意到 start_B = start_A + run_size(h1) = start_A + n1
則 l = start_A + start_B - (left << 1)
可寫作 l = 2 * start_A + n1 - (left << 1)
留意前面計算中點時假設起點 index 為 0 ,但我後來檢視其實作似乎應該將起點設為 1 較符合其 pseudo code
若 list 起點 index 為 1,則傳入 function 的 left 會是 1 ,所以 l 的計算會變成 l = 2 * start_A + n1 - 2
,若將其除上 (2*n) 則和虛擬碼中的 a 相等 (倒數第三行) 。
同理, r 的計算結果也和 b 相等,唯注意計算 r 的時候會多一個 +1 :
之所以會多這個 +1
是因為我們在檢視兩中點連線時其區間為 ,右側為閉區間, r 要被包含在區間內,而原本的虛擬碼中的 a, b 是浮點數,但 r 是整數,因此這裡要 +1
確保 r 有被包含在區間內。
而原本虛擬碼的最後面其運算為:
原本的 a 的計算為 (2 * i1 + n1 - 2) / 2n
,我們現在用 a' 表達 (2 * i1 + n1 - 2)
, b' 表達 (2 * i2 + n2 - 2)
。 則我們要計算的目標為
或者可以說
而在計算 時可以視為
而我們的目標是找到最小的 p 值使 ,即使 ((a' << 31) / 2n) & 0x8000_0000 = true
而 p 就可以透過 __built_in_clz((a' << 31) / 2n)
計算得出。 其中 (a' << 31) / 2n
可對照論文實作的 int a = (int) ((l << 31) / twoN)
而之所以最後在 clz 前要讓 (a ^ b)
,是因為這樣得到可以找到最小的 p 。
參考論文實作出計算 nodePower
的函式:
其中 start_A 表示在該 run 之前 stack 中的 run 總共有多長,也就是該 run 的起始 index 為何。
power sort 使用一個 stack 紀錄待合併的 run 以及這些 run 之間的 power 。 (i.e. stack[top].power = nodePower(stack[top].run, stack[top - 1].run
)
當要進入 stack 的 run r_new 和原本 stack top 中的 run_top 計算出來的 power_new 小於目前 stack[top].power 則將 stack 中最上面兩個 run 合併,直到 stack 中的 power 小於 power_new ,將 r_new 和 power_new 推入 stack 中:
之所以要確保新進來的 power 小於原本紀錄的 power ,是因為這樣能盡可能的讓串列的長度平衡。
以前述的 run a~f 為例,其 power 依序為
接著依序將 run 放入 stack 中:
將 放入 stack 中, power 設為 0 ,top 更新為 。
嘗試放入 ,power 為 3 > 0 ,將 放入 stack ,top 更新為 。
嘗試放入 ,發現 , power 變小表示待處理 run 的數量足以構成一個 sub tree ,有機會使 list 更加平衡,將其合併。
合併 stack 最靠近 top 的兩個 run : ,更新 top 指向 power = 0 。
目前 stack 中 power = 0 < 2 ,放入 ,更新 top 的 power 為 2 。
嘗試放入 ,其 power 為 1 < 2
合併 , 更新 top ,指向 power = 0 。
目前 stack[top].power = 0
< 1,將 放入 stack ,更新 top 的 power 為 1
嘗試放入 ,power = 3 > 1 ,直接放入並更新 power
嘗試放入 , power = 4 > 3 ,直接放入並更新 power
已無其他待放入 stack 的 run ,從 top 開始往前合併:
合併 , 長度為
合併 , 長度為
合併 , 長度為
至此便完成了 PowerSort 的排序。
以上合併過程的示意圖如下:
可以看到合併的過程接近一顆 binary tree,如此確保了 balance。
為了實作出 PowerSort,我指定新的 stack 用來紀錄不同 run 間的 power 以及對應的 start_A
(紀錄 run 開頭的 index ):
同時對 Timsort 做了以下修改:
而 merge_collapse_power
的實作如下:
commit cb20658
為了方便進行三種排序策略的比較,我寫了一個簡單的腳本用以作圖,
,會將「比較次數」、「合併時遇到的 max_run」,和「執行時間」予以製圖。
使用命令 make compare
即可自動做出上述圖片,而樣本數量和實驗次數可以修改 def.h
中的 SAMPLE
和 EXP_CNT
這兩個巨集。
統計比較次數:
△
為 power sortx
為 adaptive_ShiverSort+
為 Timsort以下依序比較資料大小為 12k
15k
18k
21k
32768 * 0.75
32768
32768 * 1.25
的結果,每組結果的縱軸依序為「比較次數」、「合併時遇到的 max_run」,和「執行時間」
若單以比較次數檢視,可以看到 PowerSort 和 Adaptive Shivers sort 擅長的資料大小不同,而 Adaptive Shivers sort 有一個很好的性質:他的表現很穩定,不會有突然比較很多次或很少次的情形發生;
相較之下 PowerSort 偶有需要特別多次比較的情形,目前尚未知道確切原因。
後來檢視論文實作,發現我實作的 Adaptive Shivers sort 相較論文多做了以下條件
原本的 Adaptive Shivers sort 的條件如下:
假設 X, Y, Z 為目前堆疊上的 Runs ,Z 為堆疊頂部 ,若 ,則將 X, Y 合併。然而我的實作除了以上狀況會進行合併外,若 Y 的長度小於等於 Z 的長度也會進行 Y, Z 的合併,即:
我參考了 cpython 中測試資料集,並實作了以下的資料集:
此外,我在 commit 048f7f 中加入了 list_sort 一併進行比較,並將 list_sort 的結果以藍色的 o 表示。原本由於 ascend_strict 和 descend_strict 以及 same 在 find_run 時便會排序好而從實驗排除的三種 samples 也因為 list_sort 的引入被加回來進行實驗。
另外為了能進一步看出潛在的規律,我嘗試將每個 data_set 的 y 方向的最大值設為相同的固定值,詳細可見 commit e607fb
Comparison cnt
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Max len
由於 list_sort 演算法本身並未涉及計算 list 長度的程式碼,但若加上計算 list 長度的邏輯於 list_sort 中會使測得的時間和比較次數不夠準確,因此 list_sort 演算法的 Max_len 在每種 sample 下皆為 0 。
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Time
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Comparison cnt
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Max run
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Time
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Comparison cnt
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Max run
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Time
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
Willsonbo
想請問是否有嘗試過將樣本點的數據標準化或是取標準差與峰態是否能觀察出其他性質呢?fennecJ
謝謝你的建議,我嘗試了你提到的數據標準化、取標準差與峰態等方法進行統計,目前沒能觀察出其它明顯的性質,因此這裡就沒有把統計結果放上來。
ascend_10 | ascend |
---|---|
descend | duplicate |
rnd_3 | rnd_1% |
rnd | worst |
參考 sortperf.py 實作對應的測試資料集並進行實驗。
研讀 Adaptive Shivers sort 之對應論文
引入 list_sort.c
進行比較。
印出 Timsort 的 worst case,嘗試觀察其有無特定規律。
將圖表的最大最小值固定後畫圖看能否發現其他規律?
參考 simplest tool to measure C program cache hit/miss and cpu time in linux? 計算 Timsort 及其衍生的 cache miss 加以比較,看看能否透過 cache miss 解釋時間差異的原因。
實驗看看 PowerSort 的計算有無可以加速的地方,例如用 - (1 + ilog(len))
取代 / (2 * len)
?
考量到 cache size 的限制,若在 sort 時用某種方法確保 list 合併的時的 run_size 大多低於某長度(i.e. 16KB) 可否讓比較時間減少?
為何選 16 KB ?假設一 64 位元硬體, L1 cache 大小為 512 KiB, list 中每個 node 有 2 個 4 byte 的 int (seq/val) 和 2 個 8 byte 的指標 (next
, prev
) ,共 24 bytes 。 512KiB/24 = 21.33 Kbytes 。16 KB 為 < 21.33 KB 中最接近的 2 的冪。(留意以上分析方式非常粗淺且可能不符真實情況)
由於看到 vax_r 設計實驗檢視隨機情形下會佔用的最大深度為何並用實驗結果說明可以如何減少最大深度的佔用。但我認為該實驗方法不夠嚴謹,可能遺漏部份極端狀況。為了檢視測驗一有沒有機會進一步降低記憶體使用量,我撰寫 permuteAndSort,作用是針對給定的陣列長度,產生所有可能的排列組合並傳入 quick_sort
函式確保考慮到所有情況,同時紀錄不同 max_depth 出現的次數並計算對應機率,可以透過外部傳參數給陣列長度,例如 ./a.out 3
,就會把陣列 [1, 2, 3]
的所有排列組合都傳進 quick_sort
中,並紀錄每次進 quick_sort
後 begin 最大深度出現的頻率。
我嘗試將對應的機率以數學形式表達,唯目前未能體會出明顯的規律,僅能看出最大深度雖機率很低,但仍有可能發生。