# 2024q1 Homework2 (quiz1+2)
>contributed by < [`pao0626`](https://github.com/pao0626) >
## [quiz1](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗一
在鏈結串列的資料結構上，實作非遞迴的快速排序法。使用推疊來紀錄每次要處理的資料，進而模擬遞迴呼叫。
#### 解釋程式碼
主要變數:
```c
int i = 0;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list)
```
- `i` 代表堆疊內元素個數。
- `begin` 陣列和 `end` 陣列追蹤每次處理完 `pivot` 後尚未排序的部分，表示區間的頭尾。
- `left` 和 `right` 分別存放每次處理堆疊元素時小於和大於 `pivot` 的節點，以便更新堆疊。
- `result` 用於儲存排序後的結果。
程式初始化時，將 `begin[0]` 和 `end[0]` 設置，表示整個鏈結串列尚未排序，並將其放入堆疊中以便處理。當堆疊不為空時，每次使用 `L` 和 `R` 指標從堆疊中取出待處理的未排序節點區間，可能會出現以下兩種情況：
- 情況1: `L` 和 `R` 指標指向同一位置，表示此區間不需要進行排序，因此將其直接加入 `result` 中，然後更新 `i` ，表示將堆疊中的頂元素彈出
- 情況2: `L` 和 `R` 指標指向不同位置，則表示此區間需要進行排序。將 `pivot` 設置為區間的首節點，走訪區間中的節點，根據它們與 `pivot` 的大小關係將它們分別加入 `left` 和 `right` 中，並同步更新鍊結串列的連接順序。
```c
if (L != R) {
...
while (p) {
node_t *n = p;
p = p->next; //CCCC
list_add(n->value > value ? &right : &left, n);
}
...
} else {
if (L)
list_add(&result, L);
i--;
}
```
如果是情況2，對於未排序區間節點的每次操作僅涉及確保 `pivot` 所指向的節點位置正確，即確保在其左邊的節點都小於它，而在右邊的節點都大於它。然後，在彈出堆疊頂部元素後，將這三種區間分別添加到堆疊中以進行後續處理。
```c
begin[i] = left;
end[i] = list_tail(&left); //DDDD
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right); //EEEE
left = right = NULL;
i += 2;
```
以下以$[4,1,3,5,2]$為例進行圖解：
**步驟1.** 初始化，將整個鍊結串列用 `begin` 和 `end` 表示區間後放入堆疊：
```graphviz
digraph graphname{
node[shape=record];
rankdir = LR
map [label="stack | [4,2] "];
}
```
**步驟2.** 當堆疊非空， `L` 和 `R` 指向堆疊頂元素之區間頭尾節點， `pivot` 指向此區間首元素:
```graphviz
digraph structs {
node[shape=plaintext];
Pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "1"];
struct2 [label= "3"];
struct3 [label= "5"];
struct4 [label= "2"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
}
Pivot -> struct0;
L -> struct0;
R -> struct4;
}
```
**步驟3.** 使用 `n` 和 `p` 一前一後走訪所有節點:
```graphviz
digraph structs {
node[shape=plaintext];
Pivot [fontcolor="red"];
n [fontcolor="black"];
p [fontcolor="black"];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "1"];
struct2 [label= "3"];
struct3 [label= "5"];
struct4 [label= "2"];
{
rank="same";
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
}
Pivot -> struct0;
n -> struct1;
p -> struct2;
}
```
**步驟4.** 將所有小於和大於 `pivot` 得節點分別暫時用 `left` 和 `right` 紀錄後，更新鍊結串列和堆疊：
- 以第一個節點 `1` 為例：
```graphviz
digraph structs {
node[shape=plaintext];
left [fontcolor="blue"];
Pivot [fontcolor="red"];
n [fontcolor="black"];
p [fontcolor="black"];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "1"];
struct2 [label= "3"];
struct3 [label= "5"];
struct4 [label= "2"];
{
rank="same";
struct2 -> struct3
struct3 -> struct4
}
Pivot -> struct0;
left -> struct1;
n -> struct2;
p -> struct3;
}
```
- 全部處理後會變成：
```graphviz
digraph structs {
node[shape=plaintext];
left [fontcolor="blue"];
Pivot [fontcolor="red"];
right [fontcolor="blue"];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "1"];
struct2 [label= "3"];
struct3 [label= "5"];
struct4 [label= "2"];
{
rank="same";
struct4 -> struct2
struct2 -> struct1
}
Pivot -> struct0;
left -> struct4;
right -> struct3;
}
```
- 更新堆疊：
```graphviz
digraph structs {
node[shape=plaintext];
begin_0 [fontcolor="blue"];
begin_1 [fontcolor="blue"];
begin_2 [fontcolor="blue"];
end_0 [fontcolor="red"];
end_1 [fontcolor="red"];
end_2 [fontcolor="red"];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "1"];
struct2 [label= "3"];
struct3 [label= "5"];
struct4 [label= "2"];
{
rank="same";
struct4 -> struct2
struct2 -> struct1
}
begin_0 -> struct4;
end_0 -> struct1;
begin_1 -> struct0;
end_1 -> struct0;
begin_2 -> struct3;
end_2 -> struct3;
}
```
```graphviz
digraph graphname{
node[shape=record];
rankdir = LR
map [label="stack | [5,5] | [4,4] | [2,1] "];
}
```
**步驟5.** 觀察堆疊情形可以看出節點5和節點4已經處理好了，只要重複**步驟2**繼續處理區間[2.1]，直到堆疊為空即可。
- 將堆疊中處理好的節點更新至 `result` 中：
```graphviz
digraph graphname{
node[shape=record];
rankdir = LR
map [label="stack | [2,1] "];
}
```
```graphviz
digraph structs {
node[shape=plaintext];
Pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
result [fontcolor="black"];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "1"];
struct2 [label= "3"];
struct3 [label= "5"];
struct4 [label= "2"];
{
rank="same";
struct0 -> struct3
struct4 -> struct2
struct2 -> struct1
}
Pivot -> struct4;
L -> struct4;
R -> struct1;
result -> struct0;
}
```
#### 改進方法
- 避免選擇鏈結串列中極值作為 pivot 而導致的 worst case ，嚴格制定 pivot 的選擇方式。
- TODO: 設計效能評比的測試程式，證明能避免"最差"狀況。
#### 測驗問題
- 題目敘述提到鏈結串列結構體的程式碼疑似有錯，應該不需要 `*left` 和 `*right` 。
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
### 測驗二
#### Timsort 簡介
其優勢在於對於部分已排序的資料有出色表現，透過找尋資料中已排序的子序列 (run） 來減少合併的次數。但 run 的數量也會影響到效率，因此透過設計 minrun 的長度使其能將資料切分成略小於等於 2 的冪，並用二分插入排序修改某些 run 使其符合條件，就是 Timsort 的關鍵。
Timsort 相較於合併排序，有以下改善。
- [ ] 降低 cache miss
傳統的合併排序非遞迴與遞迴作法都會需要掃過整個序列，而 Timesort 一邊走訪，就一邊找機會合併，類似於 Linux 核心的合併排序實作。
- [ ] 降低記憶體開銷
Timsort 只針對範圍重疊的部份進行合併，且只分配二個要合併的部份中較小那一部份元素數量的記憶體。
- [ ] 降低比較次數
由於二個要合併的數列都是已排序好的，可以使用 Galloping mode 方法。
#### 解釋程式碼
##### `find_run`
```c
static struct pair find_run(void *priv, struct list_head *list, list_cmp_func_t cmp)
```
用於找尋一個升序的 run ，若降序則反轉成升序。其中有趣的部份是在走訪的過程中會維護 `len` 變數來紀錄 run 的大小，並在最後強制轉型給 `head->next->prev` 儲存。這也反應了為什麼 `run_size` 函式中可以使用 `return (size_t) (head->next->prev);` 來取得 run 大小。函式最後回傳一個配對，其中包含指針 head 指向此 run 的開頭，指針 next 指向下個待處理節點。
##### `merge_collapse`
```c
static struct list_head *merge_collapse(void *priv, list_cmp_func_t cmp, struct list_head *tp)
```
使用 `stk_size` 紀錄待合併 run ，當超過 2 個就啟動 `merge_collapse` 進行判斷，一旦符合條件則啟用 `merge_at` 進行合併，確保待合併 run 之間長度的平衡，並將結果回傳給 `tp` 指針紀錄。
##### `merge_at`
```c
static struct list_head *merge_at(void *priv, list_cmp_func_t cmp, struct list_head *at)
```
`at` 指標參數會接受一個 `tp` 指標來判斷預合併的位置以及 run 大小，之後用 `merge` 進行合併。
##### `merge`
`mrege` 作用就是合併兩個 run ，與我習慣的寫法不同，採取指標的指標實作。
以下是我習觀的寫法：
```diff
static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)
{
- struct list_head *head;
- struct list_head **tail = &head;
+ struct list_head head;
+ struct list_head *tail = &head;
for (;;) {
if (cmp(priv, a, b) <= 0) {
- *tail = a;
- tail = &a->next;
+ tail->next = a;
+ tail = tail->next;
a = a->next;
if (!a) {
- *tail = b;
+ tail->next = b;
break;
}
} else {
- *tail = b;
- tail = &b->next;
+ tail->next = b;
+ tail = tail->next;
b = b->next;
if (!b) {
- *tail = a;
+ tail->next = a;
break;
}
}
}
- return head;
+ return head.next;
}
```
##### 過程圖示
> 參考 <[marvin0102](https://github.com/marvin0102/lab0-c)> 畫圖方法
以題目序列作為範例：
```graphviz
digraph list
{
node [shape="record"];
rankdir = "LR";
n0[label = "head"];
n1[label = "1"];
n2[label = "2"];
n3[label = "3"];
n4[label = "4"];
n5[label = "3"];
n6[label = "2"];
n7[label = "4"];
n8[label = "7"];
n9[label = "8"];
n0->n1;
n1->n2;
n2->n3;
n3->n4;
n4->n5;
n5->n6;
n6->n7;
n7->n8;
n8->n9;
}
```
執行第一次 `find_run` 。
```graphviz
digraph list
{
node[shape=plaintext];
"result.head" [fontcolor="blue"];
"result.next" [fontcolor="blue"];
node [shape="record"];
rankdir = "LR"
n0[label = "head"];
n1[label = "1", color = red];
n2[label = "2", color = red];
n3[label = "3", color = red];
n4[label = "4", color = red];
n5[label = "3"];
n6[label = "2"];
n7[label = "4"];
n8[label = "7"];
n9[label = "8"];
n0->n1;
"result.head"->n1;
n1->n2;
n2->n3;
n3->n4;
n4->n5[style = invis];
"result.next"->n5;
n5->n6;
n6->n7;
n7->n8;
n8->n9;
}
```
執行完三次 `find_run` 。
```graphviz
digraph list
{
node[shape=plaintext];
tp [fontcolor="blue"];
"tp->prev" [fontcolor="blue"];
"tp->prev->prev" [fontcolor="blue"];
node [shape="record"];
rankdir = "LR"
n1[label = "1"];
n2[label = "2"];
n3[label = "3"];
n4[label = "4"];
n5[label = "3"];
n6[label = "2"];
n7[label = "4"];
n8[label = "7"];
n9[label = "8"];
"tp->prev->prev"->n1;
n1->n2;
n2->n3;
n3->n4;
n4->n6[style = invis];
"tp->prev"->n6;
n6->n5;
n5->n7[style = invis];
tp->n7;
n7->n8;
n8->n9;
}
```
符合 `merge_collapse` 條件 “`tp->prev->prev`<=`tp->prev`+`tp`，且`tp->prev`<`tp`” ，因此執行 `merge_at` 將 `tp` 和 `tp->prev` 合併。
```graphviz
digraph list
{
node[shape=plaintext];
tp [fontcolor="blue"];
"tp->prev" [fontcolor="blue"];
node [shape="record"];
rankdir = "LR"
n1[label = "1"];
n2[label = "2"];
n3[label = "3"];
n4[label = "4"];
n5[label = "3"];
n6[label = "2"];
n7[label = "4"];
n8[label = "7"];
n9[label = "8"];
"tp->prev"->n1;
n1->n2;
n2->n3;
n3->n4;
n4->n6[style = invis];
tp->n6;
n6->n5;
n5->n7;
n7->n8;
n8->n9;
}
```
再一次的 `merge_collapse` ，條件為 “`tp->prev`<=`tp` ，所以執行 `merge_at` 將 `tp` 和 `tp->prev` 合併。
```graphviz
digraph list
{
node[shape=plaintext];
tp [fontcolor="blue"];
node [shape="record"];
rankdir = "LR"
n1[label = "1"];
n2[label = "2"];
n3[label = "3"];
n4[label = "4"];
n5[label = "3"];
n6[label = "2"];
n7[label = "4"];
n8[label = "7"];
n9[label = "8"];
"tp"->n1;
n1->n2;
n2->n6;
n6->n3;
n3->n5;
n5->n4;
n4->n7;
n7->n8;
n8->n9;
}
```
最後透過 `build_prev_link` 重建雙向鏈結串列。
#### 改進方法
- 此程式碼並沒有使用到 Galloping mode 的合併方法。
- 困惑之處：此程式碼實作透過 merge_collapse 函式確保堆疊上的 run 長度保持平衡，這與設計 minrun 長度的方法是不是只能二選一，因為我的理解是 minrun 就代表了每個 run 的固定長度。
- TODO: 將 timsort 優化後整合進 lab0-c 。
## [quiz2](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
>參考 [核心基礎設施: hlist_head/hlist_node 結構解析](https://linux.laoqinren.net/kernel/hlist/)
>參考 [Linux 核心的 hash table 實作 ](https://hackmd.io/@sysprog/linux-hashtable)
使用 dfs 方法，透過前序走訪結果和中序走訪結果來重建二元樹。需要先將中序走訪結果用雜湊函數儲存，才能確認遞迴參數範圍。
第一次接觸到 c 語言的雜湊函數，詳細內容可見以上兩篇參考文章。
#### 解釋程式碼
> 參考 < [HenryChaing](https://hackmd.io/O_Me7VZOSX2N_yne2I05lQ?view) > 畫圖方法
##### `hlist_add_head`
```c
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
if (h->first)
h->first->pprev = &n->next;
n->next = h->first; /AAAA
n->pprev = &h->first;
h->first = n;
}
```
於雜湊表中找到索引 h ，用 `h->first` 判斷該 bucket 是否已有節點後再插入新節點 n。
假設已有節點 `hlist_node_1` 如下所示：
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}"];
node[shape=plaintext];
NULL;
list_head -> node_1[style = invis] //不可見箭頭確保順序
list_head:n -> node_1:m;
node_1:p -> list_head:n;
node_1:n -> NULL;
}
```
插入節點 n 如下所示：
```graphviz
digraph G {
rankdir = LR;
node[shape = "record"]
list_head[label = "<m>list_head | <n>first"]
node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}"];
n[label = "<m>n | {<p>pprev | <n>next}"];
node[shape=plaintext];
NULL;
list_head -> n[style = invis]
n -> node_1[style = invis]
list_head:n -> n:m[color = red];
n:p -> list_head:n[color = red];
n:n -> node_1:m[color = red];
node_1:p -> n:n[color = red];
node_1:n -> NULL;
}
```
##### `order_node`
```c
struct order_node {
struct hlist_node node;
int val;
int idx;
};
```
用來存放雜湊表的 `hlist_node` 節點、序列的值和中序序列所在位置之索引值的結構體。
##### `find`
```c
static int find(int num, int size, const struct hlist_head *heads)
{
struct hlist_node *p;
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) { //BBBB
struct order_node *on = container_of(p, struct order_node, node); //CCCC
if (num == on->val)
return on->idx;
}
return -1;
}
```
根據雜湊表索引找出對應的鏈結串列串列，再透過 `hlist_for_each` 逐一走訪節點找出對應值的節點，最後返回該節點所存的中序序列索引值。
##### `雜湊表架構圖示`
```graphviz
digraph G {
rankdir=LR;
node[shape=record];
map [label="<ht0>heads[0]| <ht1>heads[1]|<ht2>heads[2]|<ht3>...| <ht4>... | <ht5>...|<ht6>heads[inorderSize - 1]"];
node[shape=plaintext]
in_heads[label=in_heads]
null1[label=NULL]
null2[label=NULL]
subgraph cluster_1 {
style=filled;
color=lightgrey;
node [shape=record];
hn1 [label="<m>hlist_node | {<p>pprev | <n>next}"];
label="order_node 1"
}
subgraph cluster_2 {
style=filled;
color=lightgrey;
node [shape=record];
hn2 [label="<m>hlist_node | {<p>pprev | <n>next} "];
label="order_node 2"
}
subgraph cluster_3 {
style=filled;
color=lightgrey;
node [shape=record];
hn3 [label="<m>hlist_node | {<p>pprev | <n>next}"];
label="order_node 3"
}
in_heads -> map:ht0
map:ht1 -> hn1:m
hn1:p -> map:ht1
hn1:n -> hn2:m
hn2:n -> null1
hn2:p -> hn1:n
map:ht5 -> hn3:m
hn3:n -> null2
hn3:p -> map:ht5
}
```
#### 改進方法
- 取 hash 值的方法可以使用參考文獻中提及的黃金比例。
- 改寫 dfs 函式，因為其實沒有必要追蹤 preorder idx ，只要設置成全域變數後逐一遞增即可，如此即可有效減少遞迴函式所需傳入的參數量。
##### `dfs`
```diff
static struct TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize)
{
struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
for (int i = 0; i < inorderSize; i++)
INIT_HLIST_HEAD(&in_heads[i]);
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
- return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1, in_heads, inorderSize);
+ return dfs(preorder, inorder, 0, inorderSize - 1, in_heads, inorderSize);
}
-static struct TreeNode *dfs(int *preorder, int pre_low, int pre_high, int *inorder, int in_low, int in_high, struct hlist_head *in_heads, int size)
+static struct TreeNode *dfs(int *preorder, int *inorder, int in_low, int in_high, struct hlist_head *in_heads, int size)
{
+ static pre_idx = 0;
if (in_low > in_high)
return NULL;
struct TreeNode *tn = malloc(sizeof(*tn));
- tn->val = preorder[pre_low];
+ tn->val = preorder[pre_idx];
+ pre_idx++;
- int idx = find(preorder[pre_low], size, in_heads);
+ int idx = find(preorder[pre_idx], size, in_heads);
- tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size);
+ tn->left = dfs(preorder, inorder, in_low, idx - 1, in_heads, size);
- tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size);
+ tn->right = dfs(preorder, inorder, idx + 1, in_high, in_heads, size);
return tn;
}
```
### 測驗二
### 測驗三
Sign in with Wallet
Connect another wallet