---
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
<!-- ## 第二週測驗題
### 測驗一
### 測驗二
### 測驗三 -->