--- tags: linux2024 --- # 2024q1 Homework2 (quiz1+2) contributed by < `randyuncle` > TODO: - [ ] 預計先做第一週測驗作業二,了解 Tim sort 和 `lib/list_sort` 的差別,以銜接 M03 中對於 Tim sort 引入 lab0-c 的檢查要求 ## quiz1 -- 測驗一 <!-- TODO: 程式碼解釋完就算成功( --> ### 前言 在此題中的快速排序法參考的是 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)。在這篇文章中,作者依舊使用頭部節點(也就是鍊結串列的第一個節點)做為每一輪比較的 pivot。但和[常見的快速排序法](https://github.com/randyuncle/My-personal-bachelar-coding-experience/blob/main/DataStructure/F74094017_hw27.c)不同的是,作者使用固定大小的堆疊陣列,去取代遞迴呼叫所使用的記憶體堆疊。 除此之外,此程式的交換在每輪遍歷時,指標 `L` 和 `R` 遇到比 pivot 大和比 pivot 小的值的場合,就會觸發,直到 `L >= R` 為止,且每輪只會觸發一次,而非像[常見的快速排序法](https://github.com/randyuncle/My-personal-bachelar-coding-experience/blob/main/DataStructure/F74094017_hw27.c)一樣,在每輪的排序途中做複數次交換。 ### 此題鏈結串列的運作 #### 鏈結串列結構體 在此題中,自定義了一個鏈結串列結構體: ```c typedef struct __node { struct __node *left, *right; struct __node *next; long value; } node_t; ``` 對應的結構圖如下: ```graphviz digraph structs { node[shape=record] struct0 [label="<left> left|<value> value|<right> right|<next> next"]; struct1 [label="<left> left|<value> value|<right> right|<next> next"]; struct2 [label="<NULL> NULL"] struct0:next -> struct1[arrowhead=vee, tailclip=true, arrowsize=1]; struct1:next -> struct2[arrowhead=vee, tailclip=true, arrowsize=1]; } ``` 在 `node_t` 結構體中,它有一個指標 `next`、一個整數型態變數 `value`、以及兩個在測驗題的參考程式中沒看到有特別著墨的 `left` 和 `right` 指標。由此可推測此為一個單向的鏈結串列。 接下來,將針對維護此鏈結串列的操作函式做說明。 #### `list_add` ```c void list_add(node_t **list, node_t *node_t) { node_t->next = *list; *list = node_t; } ``` `list_add` 函式主要功能是將新的節點連進鏈結串列中。由於結構體 `node_t` 中的 `next` 變數是個指標,因此若要賦予 `node_t->next` 內容的話,需要引入的參數 `list` 需為指標的指標。 我們假設 * 鏈接串列參數 `node_t **list` 指向的結構體的整數型態變數 `value` 為 `A` ```graphviz digraph structs { node[shape=record] struct1 [label="<left> left|<value> A|<right> right|<next> next"]; struct2 [label="<...> ..."] struct1:next -> struct2[arrowhead=vee, tailclip=true, arrowsize=1]; } ``` * 結構體參數 `node_t *node_t` 的整數型態變數 `value` 為 `B` ```graphviz digraph structs { node[shape=record] struct0 [label="<left> left|<value> B|<right> right|<next> next"]; } ``` 此函式運作完後的 `node_t *list` 可得到如下圖的結果: ```graphviz digraph structs { node[shape=record] struct0 [label="<left> left|<value> B|<right> right|<next> next"]; struct1 [label="<left> left|<value> A|<right> right|<next> next"]; struct2 [label="<...> ..."] struct0:next -> struct1[arrowhead=vee, tailclip=true, arrowsize=1]; struct1:next -> struct2[arrowhead=vee, tailclip=true, arrowsize=1]; } ``` 可以發現到欲連入鏈接串列的節點(`node_t *node_t`),會被接在原本的鏈接串列頭部節點(`node_t **list`)的前面,成為新的頭部節點。 #### `list_tail` ```c node_t *list_tail(node_t **left) { while ((*left) && (*left)->next) left = &((*left)->next); //AAAA return *left; } ``` `list_tail` 函式的功能是回傳指定參數鏈接串列的最後一個節點,以 while 迴圈寫成。 運作的方式可參考以下的圖: 首先,引入的鏈接串列會是下列的形式 ```graphviz ``` 之後,在經過第一次迭代操作後,可以得到以下的狀態 ```graphviz ``` 重複以上的操作,直到到達鏈接串列的最後一個節點,也就是 `(*left)->next` 和 `(*left)` 任一項不存在的場合(不過通常都是 `(*left)->next` 不存在就會跳出迴圈)。 <!-- #### `list_length` #### `list_construct` #### `list_free` ### 快速排序的實作程式碼可用時的實驗程式片段 #### `list_is_ordered` #### `shuffle` #### `main` ### 快速排序程式碼的運作 ### 可能的改進方案 --> --- ## quiz1 -- 測驗二 ### 解釋 Tim sort 程式碼運作原理 Tim Sort 的運作分為兩個部分:分割和合併。與 `lib/list_sort` 中實現的 merge sort 相似之處在於,它們都優化了對 cache 的使用,即在分割序列時,就已經啟動了合併操作,這樣可以在非連續記憶體序列還在 L1 cache 中時就開始進行合併。除此之外,它們在合併的規則都有參考 2 的冪,以有較佳的比較次數。 在[測驗二](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)中的程式,使用了 Linux 核心的 `list.h` API,以及於 `lib/list_sort` 中所實現的合併策略。比較需要注意的是 `lib/list_sort` 合併策略的引入,使得此程式不需要按照[作者原來的構想](https://en.wikipedia.org/wiki/Timsort#Merge_criteria) -- 額外令一個空間去存取合併後的結果,使其之記憶體開銷降至最低。 接下來,以下將針對部分的程式碼操作做說明。 #### `tim_sort` 執行 Tim sort 的主要函式。 首先,Tim sort 在排序的開頭,會先走訪過一遍鏈接串列,也就是以下 do-while 迴圈在做的操作: ```c do { /* Find next run */ struct pair result = find_run(priv, list, cmp); result.head->prev = tp; tp = result.head; list = result.next; stk_size++; tp = merge_collapse(priv, cmp, tp); } while (list); ``` 在走訪鏈接串列的過程,Tim sort 會以 `find_run` 函式,將鍊接串列分割成一條一條各自已排序成由小到大的子串列,並將每一輪的分割子串列之頭尾節點指標回傳給變數 `result`,以將其接入堆疊串列 `tp` 中。 在堆疊串列 `tp` 成功接入新的子串列、更新了目前堆疊的高度後,會交由 `merge_collapse` 函式,決定是否要將堆疊中的部分串列合併。關於 `merge_collapse` 函式的運作後續會說明。 以上操作完成後,接下來會使用 `merge_force_collapse()` 函式,將剩餘的 run 串列強制合併。 ```c /* End of input; merge together all the runs. */ tp = merge_force_collapse(priv, cmp, tp); ``` 最後,`tim_sort` 函式會先確保所有的子串列都變成雙向鏈接串列,之後,再將剩下的子串列合併在一起。其中,這裡合併策略使用了 `lib/list_sort` 的實作方法完成。 ```c /* The final merge; rebuild prev links */ struct list_head *stk0 = tp, *stk1 = stk0->prev; while (stk1 && stk1->prev) stk0 = stk0->prev, stk1 = stk1->prev; if (stk_size <= FFFF) { build_prev_link(head, head, stk0); return; } merge_final(priv, cmp, head, stk1, stk0); ``` 如果我們對比 `lib/list_sort` 的 `list_sort` 函式的結尾處,會發現上面列出的程式碼的實作是非常相似於 `list_sort` 函式得處理方式。 #### `find_run` Tim sort 中,尋找所有已排序的子序列,並在運作途中,會將 descending order 的子序列直接轉成 ascending order 的函式。回傳的資料型態為一個包含子序列頭尾節點的結構體。 ```c /* Return data type of function `find_run` */ struct pair { struct list_head *head, *next; }; ``` 在分辨是否為 descending order 子序列的方式,由以下的 if 判斷條件所掌握: ```c cmp(priv, list, next) > 0 ``` 這條函式的含意,主要是判斷是當前輸入的節點值 ( `value` ) 和它下一個的節點值的大小差別。如果 `list->value > next->value`,代表此子序列有可能是 descending order;反之,則為 ascending order,或兩兩相同。其中,這裡的 `cmp` 函式和 `lib/list_sort` 中代表的意思是一模一樣的。 如果經過此比較函式的比較後,發現結果為 `list->value > next->value` 的話,當前的子序列為 descending order 的結構,需要將其反轉,也就是下列的程式碼所做的操作: ```c do { len++; list->next = prev; prev = list; list = next; next = list->next; head = list; } while (next && cmp(priv, list, next) > 0); ``` 以 do-while 迴圈,將節點一個一個反接成 head 節點的前一個節點 ```graphviz digraph _graph_name_ { rankdir=LR; # 順序由左至右(上下是"TD" graph [fontname="DFKai-SB"]; # 此三行是設定字型 node [fontname="DFKai-SB"]; # 中文務必指定 edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼 # node head[label = "head", shape=none] next[label = "next", shape=none] prev[label = "prev", shape=none] list[label = "list", shape=none] A[label = "A", shape=box] B[label = "B", shape=box] # 不給 label 就會直接用名稱 C[label = "C", shape=box] null[label = "NULL", shape=none] # edge prev -> null C -> B -> A A -> B -> C next -> B head -> C list -> C } ``` ```graphviz digraph _graph_name_ { rankdir=LR; # 順序由左至右(上下是"TD" graph [fontname="DFKai-SB"]; # 此三行是設定字型 node [fontname="DFKai-SB"]; # 中文務必指定 edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼 # node head[label = "head", shape=none] next[label = "next", shape=none] prev[label = "prev", shape=none] list[label = "list", shape=none] A[label = "A", shape=box] B[label = "B", shape=box] # 不給 label 就會直接用名稱 C[label = "C", shape=box] null[label = "NULL", shape=none] # edge prev -> C C -> null B -> A A -> B -> C next -> A head -> C list -> B } ``` 並將 head 節點更新為反接的節點 ```graphviz digraph _graph_name_ { rankdir=LR; # 順序由左至右(上下是"TD" graph [fontname="DFKai-SB"]; # 此三行是設定字型 node [fontname="DFKai-SB"]; # 中文務必指定 edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼 # node head[label = "head", shape=none] next[label = "next", shape=none] prev[label = "prev", shape=none] list[label = "list", shape=none] A[label = "A", shape=box] B[label = "B", shape=box] # 不給 label 就會直接用名稱 C[label = "C", shape=box] null[label = "NULL", shape=none] # edge prev -> C C -> null B -> A A -> B -> C next -> A head -> B list -> B } ``` 另一方面,如果此子序列是 ascending order 的話,則做 do-while 迴圈的掃描,直到下一個節點 ( `next` 指標 ) 比當前節點 ( `list` 指標 ) 的值 ( `value` ) 大為止。 ```c do { len++; list = next; next = list->next; } while (next && cmp(priv, list, next) <= 0); ``` 在函式的最後,則是一個將該 run 的頭部節點之 `prev` 指標令為 NULL,暫時斷掉和原鏈接串列的連結。 ```c head->prev = NULL; head->next->prev = (struct list_head *) len; ``` 比較需要注意的是,在頭部節點的下一個節點的 `prev` 指標中,是令其指向為 `len` 變數。而這裡的 `len` 變數,在函式開頭就有做以下的型態定義和初始化: ```c size_t len = 1; ``` 所以,在每輪 `find_run` 函式運作完,其所分割出來的 run 串列之 `head->next->prev` 指標,都會指向一個為 `size_t` 資料型態的變數 `len`,並且變數 `len` 會被強轉型為 `struct list_head *` 指標的資料型態。 #### `run_size` 一個用來計算目前 run 串列的大小(也就是節點數量)。 ```c static inline size_t run_size(struct list_head *head) { if (!head) return 0; if (!head->next) return 1; return (size_t) (head->next->prev); } ``` 前兩個 if 條件判斷是用來直接排除沒有節點或只有一個節點的情況。若輸入的引數 `head` 指標有多於一個節點的話,則會回傳存在 `head->next->prev` 的 `size_t len` 數值,表示此 run 串列的長度大小。 #### `merge_collapse` 決定是否要在 Tim sort run 操作中進行堆疊串列合併的函式,確保每個 run 的長度差距不至於差到太多。決定合併的判斷依據是在堆疊 ( `tp` 指標 ) 中的 run 串列的大小比較,以及堆疊中的 run 串列的數量。 在此程式中,主要對於 run 串列的合併條件為以下: > 該函式主要檢查堆疊頂端的 3 個 run 是否滿足以下原則: > 1. A 的長度要**大於** B 和 C 的長度總和。 > 2. B 的長度要**大於** C 的長度。 從以上的幾個條件,也可以知道,此程式實作的 Tim sort 的 minimum run size 的選擇並非是一個固定的值,而是一個 run 串列之間比較權衡的結果,平衡各個 run 串列的長度差距。 在程式中的實作為以下: * 堆疊中的 run 串列數量多於 3,且堆疊 `tp->prev->prev` 的 run 串列大小**不大於** `tp->prev` 和 `tp` 指標指向的串列的總和;又或者,堆疊中的 run 串列數量多於 4,且堆疊 `tp->prev->prev->prev` 的 run 大小**不大於** `tp->prev->prev` 和 `tp->prev` 指標指向的串列的總和。 ```c if ((n >= 3 && run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) || (n >= 4 && run_size(tp->prev->prev->prev) <= run_size(tp->prev->prev) + run_size(tp->prev))) ``` * 若 `tp->prev->prev` run 串列大小**小於** `tp` run 串列,以 `tp->prev` run 串列為基準引入 `merge_at` 函式執行合併。 ```c if (run_size(tp->prev->prev) < run_size(tp)) { tp->prev = merge_at(priv, cmp, tp->prev); } ``` * 若非以上條件,則以 `tp` run 串列為基準引入 `merge_at` 函式執行合併。 ```c tp = merge_at(priv, cmp, tp); ``` * `tp->prev` 指標指向的 run 串列大小**不大於** `tp` 指標指向的 run 串列。 ```c else if (run_size(tp->prev) <= run_size(tp)) { tp = merge_at(priv, cmp, tp); } ``` #### `merge_force_collapse` 在 `tim_sort` 函式走訪完整個鏈接串列後,將整個堆疊中的 run 串列強制合併的函式。主要看當前堆疊的前三個 run 串列之間的狀態比較,來決定合併的方式。 判定合併方式的條件,即為前述 merge_collapse() 函式中的第一個項目符號符合後所進的 if-else 條件式。 #### `merge_at` 將輸入引數 `at` 指標以及它的前一個指標 `at->prev`執行合併操作的函式。 執行合併前,會先將合併後的串列大小做加總,並存成 `size_t` 資料型態的變數 ```c size_t len = run_size(at) + run_size(at->prev); ``` 執行合併的方式,則是使用 `lib/list_sort` 的合併策略,將 `at` 指標以及他的前一個指標 `at->prev` 指標合併成一個新的 run 串列。 ```c struct list_head *list = merge(priv, cmp, at->prev, at); ``` 在合併完成後,此函式會進行與 `find_run()` 函式結尾相同的操作,亦即,將合併後的 `list` 指標的下一個節點指向的前一個指標 (list->next->prev) 更新為新的 `size_t` 資料型態的變數。 ```c list->next->prev = (struct list_head *) len; ``` ### 將 Timsort 引入進 lab0-c > 詳見:[整合 Tim sort 進 queue.c](https://hackmd.io/jX0N-0D4S_yxXipGlRRBIg?both#%E6%95%B4%E5%90%88-Tim-sort-%E9%80%B2-queuec) ### 提出改進方案並實作之 Tim sort 相比於傳統 merge sort,多了幾個為了 cache-friendly、有助於減少比較次數、且理論可在合併時做到最佳平衡的技巧: * Defining minimum run size while finding runs. * Introduces galloping mode during merging. 而這兩個想法在原程式是沒有落實的,因此以下我想將以上的兩個想法落實進原程式中,並比較若實現這兩個想法進去後的比較次數及效能差異。 #### Minimum run size 從前一節的描述以及實作中,可以看到 Tim sort 在做合併之前,都會先走訪過一次整個資料結構中的所有元素,以找到每一節的 ascending ( 或 descending ) order。為了能夠保證每個 run 都有一個基礎大小,使其可以做到均勻的合併,Tim sort 的作者設定了一個被稱為 `MAX_MINRUN` 的變數,規定每條 run 限定的最小長度大小。作者也同時在[原實作中](https://github.com/python/cpython/blob/main/Objects/listsort.txt#L211)寫下了配套的求取機制: > take the first `log2(MAX_MINRUN)` bits of `N`, and add 1 if any of the remaining bits are set. In fact, that rule covers every case in this section, including small `N` and exact powers of 2; `merge_compute_minrun()` is a deceptively simple function. 簡單來說,每條 run 的最短長度,就是原本的 `MAX_MINRUN` 變數取 log~2~ 的結果。 如果在 `find_run` 的過程中,有一條 run 的長度比最短的 run 長度要小的話,則會需要填補缺少節點進去該 run 中。作者在填補後,會以 binary insertion sort 的方式做重新排序,使其變成 ascending ( 或 descending ) order。雖然在程式中,可以知道每條 run 當下的長度,但是在鏈接串列中,並不太好使用二分搜尋法的方式插入節點,因為就算得到中點的資訊,仍需要使用迴圈等方式,將指標定位到該節點上。 在我查看 cpython 中的 [listsort.txt](https://github.com/python/cpython/blob/main/Objects/listsort.txt#L211) 的內容時,看到了裡面做 galloping mode 時的 "galloping" 運作原理,於是嘗試使用類似 galloping 的方式,在 commit [19e34a5](https://github.com/randyuncle/lab0-c/commit/19e34a5dcdd6a0e68f25e4fad95c4c274d5e1347) 中是以兩兩節點一同讀取的方式,取代原本使用二分搜尋法,去找到節點應插入的位置。 - [ ] linear searching during insertion sort > commit [19e34a5](https://github.com/randyuncle/lab0-c/commit/19e34a5dcdd6a0e68f25e4fad95c4c274d5e1347) > 2024/4/23 在想能不能把 `findrun()` 用指標的指標重新撰寫,不然現在的做法需要先將串列的 prev 指標重新建成以避免無限 loop bug 出現。 commit [19e34a5](https://github.com/randyuncle/lab0-c/commit/19e34a5dcdd6a0e68f25e4fad95c4c274d5e1347) 是我目前的實作結果。關於其中的 minimum run size 的求取已在 commit message 中做簡易的描述。 在 [listsort.txt](https://github.com/python/cpython/blob/main/Objects/listsort.txt#L211) 中,對 "galloping" 作法有以下的說明: > In galloping mode, we first look for A[0] in B. We do this via "galloping", comparing A[0] in turn to B[0], B[1], B[3], B[7], ..., B[2**j - 1], ..., until finding the k such that B[2**(k-1) - 1] < A[0] <= B[2**k - 1]. This takes at most roughly lg(B) comparisons, and, unlike a straight binary search, favors finding the right spot early in B (more on that later). 在原描述的定義中,"galloping" 主要是以 0, 1, 3, 7, ..., 2^k+1^ 的節點定位去找到節點大略會插入的範圍。不過,由於每個 run 的最低限定大小並不大(根據程式的設定,每條 run 的長度都不大於 32),因此我使用兩個指標 `curr` 以及 `prev` 去存取兩兩相鄰的節點,並以最大兩個節點的距離(`curr->next->next`)做走訪,搜尋合適節點插入點,從而降低單一節點距離(`curr->next`)走訪所帶來的比較次數差距。 >TODO: >- [X] 將新舊版本的程式分開 >- [X] 尋找自動測試的方法,可能需有以下的功能: 1. 能多重複運作整個程式,紀錄每次的結果 2. 根據結果生出圖表 - [ ] binary searching during insertion sort 不過,另一方面,我還是想要測試如果真使用二分搜尋法尋找插入節點的話,它所需要的比較次數與運行時間的差距究竟為何。 在本程式中的 binary search,首先依靠變數 `len` 得知本次 run 的長度,接下來依序迭代尋找每一輪搜尋的中點。只是相比於上面的線性走訪來說,這方法在 linked-list 可能會需要更多的指標操作(例如說以 while 迴圈定位 run 的中點),以找到合適的目的地。為了知道它們之間的比較次數和運行時間差距,所以我寫了 binary insertion sort for minimum run size 做實驗 > commit [78aa968](https://github.com/randyuncle/lab0-c/commit/78aa9681bc2472b646795bc8ba05862393019dd3) commit [78aa968](https://github.com/randyuncle/lab0-c/commit/78aa9681bc2472b646795bc8ba05862393019dd3) 是我將原本實作給 min run strategy 的 linear insertion sort 改成 binary insertion sort。中點的求尋主要由以下的程式碼所取得: ```c int middle = (x & y) + ((x ^ y) >> 1); ``` - [ ] 測試結果 本次的測試,是為了測試使用 linear insertion sort 或 binary insertion sort min run strategy 的 Tim sort,和原本的 Tim sort 程式之間的比較次數和運行時間的差距。測試程式的製作可見[這連結](https://hackmd.io/jX0N-0D4S_yxXipGlRRBIg?view#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F%E7%9A%84%E8%A3%BD%E4%BD%9C),且本次的函式測試皆在 lab0-c 的環境中運作。 測試方式: 1. 從直譯器 `qtest.c` 執行 `stest` 命令,啟動測試程式 `sort_test.c`。 2. 測試的節點數範圍為 4 ~ 8192,且每個節點數都會重複生成資料及排序 15 次(原本是想效訪 dudect 的測試,每個節點數都跑 150 次,但這樣跑一個星期也跑不完)。 測試可分為三個項目: 1. Comparisons:每次排序所需要的比較次數。 2. K-value:參考 [kdnvt 的共筆](https://hackmd.io/byNYeoGvQv-a9TNDc2CKFQ?view#comparison-%E6%AC%A1%E6%95%B8)的方法。在此篇筆記中,作者參閱了 [Bottom-up Mergesort: A Detailed Analysis](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.5260),藉由裡面對於比較次數和排序序列的元素數量的關係,了解其中 K 值的意義,並以此關係寫出計算 average k value 的程式碼。不過,在本次的測試中,我沒有要計算 average k value,因此只將 k value 的計算引入進測試程式之中。本次加入 k value 運算有一個好處 -- **能夠精確地觀察到每個節點數所對應的比較次數週期,以及比較的穩定性。** 3. Duration time:計算每次排序所需要的時間。本次測試中,測量時間的工具用的是 `dudect` 資料夾中的 `cpucycle.h` 標頭檔,分別取得排序開始前和結束後的 cpu cycle,以得到排序過程所經歷的 cpu cycles。 測試完成後的 `gnuplot` 結果如下: ##### 完全隨機的資料 ![comparison_r_minrun](https://hackmd.io/_uploads/BkOYHVXQA.png) ![kvalue_r_minrun](https://hackmd.io/_uploads/B1dcBNQm0.png) ![time_r_minrun](https://hackmd.io/_uploads/BkDorVQmR.png) ##### 升冪資料,隨機 3 個資料換成隨機資料 ![comparison_r3_minrun](https://hackmd.io/_uploads/r1PWLNm7R.png) ![kvalue_r3_minrun](https://hackmd.io/_uploads/HyTbUEQXC.png) ![time_r3_minrun](https://hackmd.io/_uploads/BySGINm7A.png) ##### 升冪資料,最後 10 個資料換成隨機資料 ![comparison_rl10_minrun](https://hackmd.io/_uploads/HJhNUEXm0.png) ![kvalue_rl10_minrun](https://hackmd.io/_uploads/HkXrI4Xm0.png) ![time_rl10_minrun](https://hackmd.io/_uploads/ByuPL4XX0.png) ##### 升冪資料,隨機 1% 個資料換成隨機資料 ![comparison_r1p_minrun](https://hackmd.io/_uploads/SJkqUNXQA.png) ![kvalue_r1p_minrun](https://hackmd.io/_uploads/rJ3c847QC.png) ![time_r1p_minrun](https://hackmd.io/_uploads/rysjI4mQA.png) ##### 有多個重複的資料 ![comparison_dup_minrun](https://hackmd.io/_uploads/B1ra847XA.png) ![kvalue_dup_minrun](https://hackmd.io/_uploads/Bk0aLEmQA.png) ![time_dup_minrun](https://hackmd.io/_uploads/H1_AU4QQR.png) ##### Worst case scenario for merge sort ![comparison_w_minrun](https://hackmd.io/_uploads/HkSZv47m0.png) ![kvalue_w_minrun](https://hackmd.io/_uploads/ryc-wN7Q0.png) ![time_w_minrun](https://hackmd.io/_uploads/HkGGP4mQ0.png) ##### Discussion 從以上的 gnuplot 可以發現,使用 binary insertion sort 作為 Tim sort 中的 minimum run insertion strategy,可以使得 Tim sort 的比較次數,以及其對應的 k-value,隨著序列中節點數量的增加,皆以直線穩定的增長,尤以隨機資料和 worst case scenario 的結果可以很明顯的看到此現象。 如果我們只看 k-value 分佈圖的結果的話,藉由每個節點數中不同的 Tim sort 實作的表現,可以得知 linear insertion sort 所造成的 k-value 都是最低的,變相的表示其之比較次數在這三個實作中,是最高的;而另一方面,binary insertion sort 則會控制整體的比較次數,使其在 k-value 的分佈處於原本的 Tim sort 和實作於 minimum run strategy 的 linear insertion sort 之間。 不過,若要執行 minimum run strategy,會導致在 `find_run()` 階段時,因為要以 insertion sort 的方式插入節點,會產生額外的比較和指標操作,所以原本的 Tim sort 的比較次數(包含 k-value 分佈的觀察)會是三個實作中最容易出現最少比較次數,且在時間分佈的中的 lower bound 也會是三個實作中最低的(除了在 worst case 中,timsort /w binary minrun 在某些節點數會出現最小的排序時間)。因此,如果要降低比較次數,要在後續將 gallopping mode 實作出來,才能知道原先 Tim sort 的構想,在鏈結串列的實作中,是否會比其他的排序演算法(例如說 lib/list_sort)要好。 #### The galloping mode 在 [listsort.txt](https://github.com/python/cpython/blob/main/Objects/listsort.txt) 中,galloping mode 可以分成兩個部分: * *exponential searching the boundaries* * *binary searching within the identified boundaries*。 我在 [Minimum run size](https://hackmd.io/nsZV7ErKSBewIhls7wgrsQ?both#Minimum-run-size) 小節中已經提過 exponential searching。簡單來說,就是以 2 的冪次做為間距的搜尋。在原本的 Tim sort 應用中,作者將此動作命名為 "galloping",其作用是在排序合併時,於另一條 run `B` 中尋找可以插入輸入最小 run 中節點 `A[0]` 的節點區間。 在做完 "galloping" 後,和填入 find run 中的方法一致,作者用 binary insertion sort 的方式,尋找節點 `A[0]` 在被找到的區間的插入點。不過,這次的 binary insertion sort 有搜尋次數的限制,當搜尋次數超過作者限定的上限值時,就會停止進行 galloping mode,回到原本的合併操作。 由於作者在 Python 的實作中,使用的是陣列,所以可以簡單的運用此方法做搜尋及合併。但是,在 Linux 核心,或者 lab0-c 的環境中,使用的資料結構都是鏈結串列。因此,在不管是在 galloping mode 做區間的尋找,或者是找到區間後的二元搜尋,都一定會少不了指標操作。且在[第一週測驗二](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)中,其 Tim sort 的實作和 lib/list_sort 有一個共通點,就是 `merge()` 和 `merge_final()` 兩個函式的合併實作是不同調的 -- `merge()` 用的是指標的指標;而 `merge_final()` 用的是指標指向輸入的 `head` 鏈結串列直接操作,原因是此函式是用來將最終鏈結串列的 `prev` 指標建立起來。此場景增加了實作 galloping mode 的困難度。 目前我先將 galloping mode 實作於 `merge()` 函式中,且其在找到該元素可插入的區塊後,使用的是 linear insertion,而非原作者使用的 binary insertion。以兩個變數 `gallop_cnt_a` 和 `gallop_cnt_b` 分別掌握串列 `a` 和 `b` 誰先被連續合併超過 `min_gallop` 次。若有某一變數超過 `min_gallop`,則會啟動 galloping mode。 - [ ] 測試結果 在經過和 Minimum run size 小節中一樣的實驗後,可以得到以下的結果: ##### 完全隨機的資料 ![comparison_r_minrun](https://hackmd.io/_uploads/B1UpHKJEC.png) ![kvalue_r_minrun](https://hackmd.io/_uploads/B1YzLFyN0.png) ![time_r_minrun](https://hackmd.io/_uploads/SkcVUYyER.png) ##### 升冪資料,隨機 3 個資料換成隨機資料 ![comparison_r3_minrun](https://hackmd.io/_uploads/Hkl1RrFyNC.png) ![kvalue_r3_minrun](https://hackmd.io/_uploads/BkGGItk4R.png) ![time_r3_minrun](https://hackmd.io/_uploads/rkzNUFkEA.png) ##### 升冪資料,最後 10 個資料換成隨機資料 ![comparison_rl10_minrun](https://hackmd.io/_uploads/r1rASY14R.png) ![kvalue_rl10_minrun](https://hackmd.io/_uploads/Bk8zLtkNC.png) ![time_rl10_minrun](https://hackmd.io/_uploads/Sk4VUYyV0.png) ##### 升冪資料,隨機 1% 個資料換成隨機資料 ![comparison_r1p_minrun](https://hackmd.io/_uploads/r1ARSYyVA.png) ![kvalue_r1p_minrun](https://hackmd.io/_uploads/ryh-8F1NA.png) ![time_r1p_minrun](https://hackmd.io/_uploads/BJ0m8FJ4R.png) ##### 有多個重複的資料 ![comparison_dup_minrun](https://hackmd.io/_uploads/ry0lIYJ40.png) ![kvalue_dup_minrun](https://hackmd.io/_uploads/rkwWIKkNR.png) ![time_dup_minrun](https://hackmd.io/_uploads/Bki78YyVC.png) ##### Worst case scenario for merge sort ![comparison_w_minrun](https://hackmd.io/_uploads/rkXyLFkVR.png) ![kvalue_w_minrun](https://hackmd.io/_uploads/rJTM8K1EA.png) ![time_w_minrun](https://hackmd.io/_uploads/HkaVUFJNA.png) ##### Discussion 從以上的 user space 實驗結果中,可以觀察到,除了隨機資料分佈和多個重複資料分佈以外,有 galloping mode 實作的排序運行時間,比起原本的 Tim sort,以及只實作 min run strategy 的 Tim sort,都要快。 除此之外,從排序時的比較次數分佈可以很明顯的看到,有實作 galloping mode 以及 min run 的 Tim sort,比只有實作 min run 的 Tim sort 的比較次數要少。但在部份的資料分佈中(隨機資料分佈、多個重複資料分佈、合併排序的最差資料分佈),它們的最小比較次數還是無法突破原本的 Tim sort 實作中的最小比較次數。 在 [fennecJ](https://hackmd.io/@fennecJ/linux2024-q1q2#Adaptive-ShiversSort) 和 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-timsort) 的筆記中,都提到過 Tim sort 的優化型態 -- [Adaptive ShiversSort](https://arxiv.org/pdf/1809.08411)、和 Powersort。前者的筆記提供了實作的範例和它們在 user space 的實驗成果,其中關於 Adaptive ShiversSort 的排序穩定性吸引了我的目光,因此,接下來我嘗試將 adaptive shiverssort 的合併策略實作於有 galloping mode 以及 binary insertion sort during min run strategy 的 Tim sort 中,以了解 Adaptive ShiversSort 的合併策略是否真如同其原論文所述的這麼神奇。 #### [Adaptive Shivers Sort: An Alternative Sorting Algorithm](https://arxiv.org/pdf/1809.08411) 一個優化 Tim sort 合併流程的排序策略。在這篇論文中,除了分析 Tim sort 以及 Adaptive ShiversSort 演算法以外,藉由 [Buss and Knop](https://arxiv.org/pdf/1801.04641) 發明的方法,證明了此演算法為 stable merge sort,也證明了一個合併排序演算法是 stable merge sort 的條件。 在此篇論文中,作者將 Shivers sort 和 Tim sort 中的特性混合,提出 Adaptive ShiversSort 的合併策略為以下: ```diff while true: + if h >= 3 and l[h - 2] <= max{l[h - 1], l[h]}: + merge(r[h - 2], r[h - 1]) else if runs != NULL: remove a run R from runs and push R onto S else: break +while h >= 2: + merge(r[h - 1], r[h]) ``` 和 Tim sort 的不同之處已以 `diff` 標記起來。Adaptive ShiversSort 的合併策略只有兩個條件: * **當 run 堆疊的數量超過 3 個,且前兩項(`tp->prev->prev`)的 run 長度比當前(`tp`)或當前之前一項(`tp->prev`) run 長度要小時**:執行當前 run 指標之前兩項(`tp->prev->prev` 和 `tp->prev`)的合併。 * **當 run 堆疊的數量超過 2 個**:執行當前 run 指標(`tp`)以及前一項 run 指標(`tp->prev`)的合併。 相比於 Tim sort,作者在論文中以理論的方式,證明 Adaptive ShiversSort 可以優化 Tim sort 在其最差情況的表現,也可以擁有更穩定的排序上限及下限。 此外,從虛擬碼中可以看出,Adaptive ShiversSort 的實作與 Tim sort 高度相似,因此兩者之間的實作轉換成本非常低。所以,針對原本的 Tim sort 合併實作,我只做了以下的改變: ```diff -if ((n >= 3 && - run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) || - (n >= 4 && run_size(tp->prev->prev->prev) <= - run_size(tp->prev->prev) + run_size(tp->prev))) { - if (run_size(tp->prev->prev) < run_size(tp)) { - tp->prev = merge_at(priv, cmp, tp->prev); - } else { - tp = merge_at(priv, cmp, tp); - } +if (n >= 3 && run_size(tp->prev->prev) <= run_size_cmp(tp, tp->prev)) { + tp->prev = merge_at(priv, cmp, tp->prev); ``` 其中,`run_size_cmp()` 函式是用來回傳兩個輸入的串列中的最大值。 至於在 ``` while h >= 2: merge(r[h - 1], r[h]) ``` 得虛擬碼實作中,由於從測驗題中引入的 Tim sort 的 run 合併實作和原本的有出入,若直接套用會額外增加許多的比較次數,因此就不做更動。 - [ ] 測試結果 測試環境一樣在 lab0-c 環境中,使用 `char` 作為結構體資料的資料型態。測試的項目和資料分佈和 Tim sort 的測試是一樣的。 測試結束後,可以得到以下的結果: ##### 完全隨機的資料 ![comparison_r_minrun](https://hackmd.io/_uploads/rkcjbZjVR.png) ![kvalue_r_minrun](https://hackmd.io/_uploads/SyfQfboEA.png) ![time_r_minrun](https://hackmd.io/_uploads/H1URfbs4R.png) ##### 升冪資料,隨機 3 個資料換成隨機資料 ![comparison_r3_minrun](https://hackmd.io/_uploads/r18hWWiEC.png) ![kvalue_r3_minrun](https://hackmd.io/_uploads/SkBfGWo40.png) ![time_r3_minrun](https://hackmd.io/_uploads/HySTzZiER.png) ##### 升冪資料,最後 10 個資料換成隨機資料 ![comparison_rl10_minrun](https://hackmd.io/_uploads/H1jh-bjEA.png) ![kvalue_rl10_minrun](https://hackmd.io/_uploads/HyKGz-jEA.png) ![time_rl10_minrun](https://hackmd.io/_uploads/Sy_aMbsE0.png) ##### 升冪資料,隨機 1% 個資料換成隨機資料 ![comparison_r1p_minrun](https://hackmd.io/_uploads/SJbn-boNC.png) ![kvalue_r1p_minrun](https://hackmd.io/_uploads/rJI5MbjEA.png) ![time_r1p_minrun](https://hackmd.io/_uploads/rJZ6G-jE0.png) ##### 有多個重複的資料 ![comparison_dup_minrun](https://hackmd.io/_uploads/SJqF--sVA.png) ![kvalue_dup_minrun](https://hackmd.io/_uploads/HkIWGZjNA.png) ![time_dup_minrun](https://hackmd.io/_uploads/rJi2GWjNA.png) ##### Worst case scenario for merge sort ![comparison_w_minrun](https://hackmd.io/_uploads/SJIa-ZsNC.png) ![kvalue_w_minrun](https://hackmd.io/_uploads/rJ1oG-iVA.png) ![time_w_minrun](https://hackmd.io/_uploads/HJo6MWiV0.png) ##### Discussion <!-- ## 第二週測驗題 ### 測驗一 ### 測驗二 ### 測驗三 -->