owned this note
owned this note
Published
Linked with GitHub
---
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` 結果如下：
##### 完全隨機的資料
##### 升冪資料，隨機 3 個資料換成隨機資料
##### 升冪資料，最後 10 個資料換成隨機資料
##### 升冪資料，隨機 1% 個資料換成隨機資料
##### 有多個重複的資料
##### Worst case scenario for merge sort
##### 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 小節中一樣的實驗後，可以得到以下的結果：
##### 完全隨機的資料
##### 升冪資料，隨機 3 個資料換成隨機資料
##### 升冪資料，最後 10 個資料換成隨機資料
##### 升冪資料，隨機 1% 個資料換成隨機資料
##### 有多個重複的資料
##### Worst case scenario for merge sort
##### 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 的測試是一樣的。
測試結束後，可以得到以下的結果：
##### 完全隨機的資料
##### 升冪資料，隨機 3 個資料換成隨機資料
##### 升冪資料，最後 10 個資料換成隨機資料
##### 升冪資料，隨機 1% 個資料換成隨機資料
##### 有多個重複的資料
##### Worst case scenario for merge sort
##### Discussion
<!-- ## 第二週測驗題
### 測驗一
### 測驗二
### 測驗三 -->
Google Drive
Gist
Clipboard
Sign in with Wallet
