# 2024q1 Homework2 (quiz1+2)
contributed by < `Leo5307` >
## 第 1 周測驗題
### 測驗 1 Optimized QuickSort — C Implementation (Non-Recursive)
特點：利用堆棧的方式來取代遞迴
運作原理：
``` graphviz
digraph G
{
rankdir=LR; # 順序由左至右(上下是"TD")
graph [fontname="DFKai-SB"]; # 此三行是設定字型
node [fontname="DFKai-SB"]; # 中文務必指定
edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼
A->B->C->D->E->F->G;
A[label = 3];
B[label = 2];
C[label = 4];
D[label = 7];
E[label = 5];
F[label = 8];
G[label = 1];
}
```
將**最左邊的節點**作為 ```pivot```，比 ```pivot``` 小的放在 ```left``` 子串列，比 ```pivot``` 大的放在 ```right``` 子串列
則第一回如下：
- ```pivot```:
``` graphviz
digraph G
{
rankdir=LR; # 順序由左至右(上下是"TD")
graph [fontname="DFKai-SB"]; # 此三行是設定字型
node [fontname="DFKai-SB"]; # 中文務必指定
edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼
A;
A[label = 3];
}
```
- ```left```:
``` graphviz
digraph G
{
rankdir=LR; # 順序由左至右(上下是"TD")
graph [fontname="DFKai-SB"]; # 此三行是設定字型
node [fontname="DFKai-SB"]; # 中文務必指定
edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼
A->B;
A[label = 2];
B[label = 1];
}
```
- ```right```:
``` graphviz
digraph G
{
rankdir=LR; # 順序由左至右(上下是"TD")
graph [fontname="DFKai-SB"]; # 此三行是設定字型
node [fontname="DFKai-SB"]; # 中文務必指定
edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼
A->B->C->D;
A[label = 4];
B[label = 7];
C[label = 5];
D[label = 8];
}
```
然後再不停地對 ```left``` ```right``` 兩個子串列做以上動作，就能完成排序。
因此：
``` cpp
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
中的 ```CCCC``` 為 ```p->next``` ，從而能夠利用 p 指標走訪整個鏈結串列。
而這份排序的特點是利用堆棧的方式來取代遞迴，因此利用```begin``` 和 ```end``` 記錄各個子串列的開頭與結尾以及節點。
``` cpp
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
```
``` cpp
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
left = right = NULL;
```
因此 ```DDDD``` 就為 ```list_tail(&left)```，而```EEEE```為```list_tail(&right)```
圖示大致如下：
``` graphviz
digraph {
node [shape=box];
// 创建方块
rankdir=LR; // 順序由左至右
A->B->C->D;
A[label = 4];
B[label = 7];
C[label = 5];
D[label = 8];
E->F;
E[label = 2];
F[label = 1];
G;
G[label = 3];
// 垂直箭头
{
rankdir=TD; // 順序由上至下
B1 -> E [arrowhead="normal"];
E1 -> F [arrowhead="normal"];
B2 -> G [arrowhead="normal"];
E2 -> G [arrowhead="normal"];
B3 -> A [arrowhead="normal"];
E3 -> D [arrowhead="normal"];
B1[label = "begin[0]"];
B2[label = "begin[1]"];
B3[label = "begin[2]"];
E1[label = "end[0]"];
E2[label = "end[1]"];
E3[label = "end[2]"];
}
}
```
最後從最右的子串列（最大值）開始，將各個節點添加到```result```中就完成排序。
``` cpp
if (L)
list_add(&result, L);
i--;
```
``` cpp
void list_add(node_t **list, node_t *node_t)
{
node_t->next = *list;
*list = node_t;
}
```
操作函式的填空：
``` cpp
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
```AAAA``` 遞回```left```以找到最尾端的節點，因此```AAAA```為```(*left)->next```。
同理和```BBBB``` 也是為了遞回也設定的，因此和```AAAA```答案一樣。
#### 可嘗試的改進：
1. 將```pivot```從選擇最左邊的節點改成隨機選取
- 避免每次選擇```pivot```都正巧選到該子串列中節點的最大、最小的值（QuickSort 的 worst case）。
2. 將```end```移除
- 因為已經有```list_tail```這個函式了，因此不需要再多一個空間儲存子串列的尾部位置資訊。
### 測驗 ２ Timsort
Timsort 結合了合併排序和插入排序，旨在利用原始資料中已排序好的 run 來加快排序速度。
以下為例子：
``` graphviz
digraph G
{
rankdir=LR; # 順序由左至右(上下是"TD")
graph [fontname="DFKai-SB"]; # 此三行是設定字型
node [fontname="DFKai-SB"]; # 中文務必指定
edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼
A->B->C->D->E->F->G->H->I->J;
A[label = 3];
B[label = 2];
C[label = 1];
D[label = 4];
E[label = 5];
F[label = 5];
G[label = 3];
H[label = 7];
I[label = 8];
J[label = 9];
}
```
為了使合併過程中更加均衡，讓run的數量等於或者略小於 2 的冪，需要利用```minrun```控制每個 run 的最小長度並在連續序列不足時利用二分插入排序將後面的元素插入，```minrun```要選擇在64以內的數字，因為在較短的序列中 insertion sort 表現較好
假設 minrun 為 4
上述例子就會變成：
``` graphviz
digraph G
{
rankdir=LR; # 順序由左至右(上下是"TD")
graph [fontname="DFKai-SB"]; # 此三行是設定字型
node [fontname="DFKai-SB"]; # 中文務必指定
edge [fontname="DFKai-SB"]; # 不然可能會出現亂碼
I->J;
E->F->G->H;
A->B->C->D;
A[label = 1];
B[label = 2];
C[label = 3];
D[label = 4];
E[label = 3];
F[label = 5];
G[label = 5];
H[label = 7];
I[label = 8];
J[label = 9];
}
```
```minrun```可透過不斷將序列長度`n`除以2直到`n`小於預設的`MIN_MERGE`(一般選擇32或16)，並在過程中只要有一次不能整除，最終結果就加一的方式來得到理想的值。
除此之外Timsort還採用多種方式來避免佔用太多記憶體
詳見:
- [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
- [最貼近現實的排序演算法- Timsort](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)
Timsort中的合併可分為兩種：
1. one pair at a time(即是合併排序所采用的模式)
2. Galloping mode
- 假設A,B兩個 run ，且A run比 B run 短
- 尋找A[0] 在 B中哪個位置的後面，假設是B[k]
- 把B[0]~B[k]放到輸出的序列
- 尋找B[0]在A中哪個位置的後面，假設是A[j]
- 把A[0]~A[j]放入輸出的序列
- 循環以上步驟直到完全合併
- Galloping mode 只有在序列具有部分排序時才會有優勢，因此 Tim 規定只有當兩個序列比較到第七次（`min_gallop = 7`）都是由同一個序列取值時，才啟動 Galloping mode
- 因此如是隨機序列，則永遠也不會觸發 Galloping mode
#### Timsort 程式碼運作原理
1. 以下程式碼需組合起來看:
``` cpp
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);
}
```
``` cpp
// 截取自 find_run
head->next->prev = (struct list_head *) len;
```
算法透過將每個 run 的長度```len```強制轉型後儲存在```head->next->prev```，來儲存每個 run 的長度
::: warning
但我不確定說這樣強製轉型是否在維護程式碼上是一個好的做法
:::
這段程式碼負責找尋順序/逆序的序列，但和我所了解的Timsort不同，在這裡並沒有考慮把每個run都補成一樣最小長度
``` cpp
static struct pair find_run(void *priv,
struct list_head *list,
list_cmp_func_t cmp)
{
size_t len = 1;
struct list_head *next = list->next, *head = list;
struct pair result;
if (!next) {
result.head = head, result.next = next;
return result;
}
if (cmp(priv, list, next) > 0) {
/* decending run, also reverse the list */
struct list_head *prev = NULL;
do {
len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;
} while (next && cmp(priv, list, next) > 0);
list->next = prev;
} else {
do {
len++;
list = next;
next = list->next;
} while (next && cmp(priv, list, next) <= 0);
list->next = NULL;
}
head->prev = NULL;
head->next->prev = (struct list_head *) len;
result.head = head, result.next = next;
return result;
}
```
四個函數```merge_at``` ```merge_force_collapse``` ```merge_collapse``` ```merge_final```則負責在過程中把序列合併。
由於在 timsort 中一開始就把雙向環狀鏈結串列打斷成單向的鏈結串列，因此需要```build_prev_link```在最後重新把鏈結串列恢復成環狀的。
將 [Timsort 實作並整合到lab0-c](https://github.com/Leo5307/lab0-c/commit/800d85e3369cb5054364c858a6207ea0782b67fe)
嘗試的改進：
1. **選定合理的minrun**
測試的程式碼並沒有包括選定一個合理的minrun，因此嘗試在程式碼中加入：
```cpp
int find_minrun(int n)
{
int count = 0;
int min_merge = 32;
bool mod = false;
if (n == 0) {
return 0;
}
while (n > min_merge) {
if (n % 2 != 0) {
mod = true;
}
n /= 2;
// printf("n = %d",count);
count++;
}
int minrun = 1;
for (int i = 0; i < count; i++) {
minrun *= 2;
}
if (mod) {
return (minrun + 1);
} else {
return minrun;
}
}
```
並把minrun加入迴圈的判斷式：
```cpp
while (next && (cmp(priv, list, next) > 0 || len < minrun));
```
以及
```cpp
while (next && (cmp(priv, list, next) <= 0 || len < minrun));
```
但卻導致排序錯誤，目前還在排查錯誤中。(發現是沒考慮 insertion sort 的部分)
::: success
待做 : Gallloping mode
:::
## 參考資料：
1. [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
2. [Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)
3. [最貼近現實的排序演算法- Timsort](https://jason18153.medium.com/%E6%9C%80%E8%B2%BC%E8%BF%91%E7%8F%BE%E5%AF%A6%E7%9A%84%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-timsort-a75da75b65a2)
## 第 2 周測驗題
Sign in with Wallet
Connect another wallet