# 2024q1 Homework2
contributed by < [`patri27826`](https://github.com/patri27826) >
## [第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
<s>
#### AAAA
```diff
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
- left = &(AAAA);
+ left = &(*left->next)
return *left;
}
```
第一個`AAAA`是要填充`list_tail`，那具體做法就是我在每一個迴圈中，都先去確認說下一次是不是`null`，是的話就轉到下一個，因此答案為`(*left->next)`
</s>
:::danger
不用列出參考題解，你只要專注在程式碼和你的洞見。
:::
<s>
#### BBBB
```diff
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
- left = &(BBBB);
+ left = &((*left)->next);
}
return n;
}
```
同上一題，也是去找長度，因次這邊也是去`left`的下一個`node`
#### CCCC
```diff
while (p) {
node_t *n = p;
- p = CCCC;
+ p = p->next;
list_add(n->value > value ? &right : &left, n);
}
```
</s>
:::danger
不用列出參考題解，你只要專注在程式碼和你的洞見。
:::
這邊的`while`，目的是要把整個列表依照`pivot`值分到`left` `right`，因此`CCCC`就是`p->next`以 <s>遍歷整個列表</s>
:::danger
linked list 為「鏈結串列」，可簡稱為 list (串列)，但不可稱「链表」，該資料結構不具備任何「表」的寓意，參見中華民國教育部重編國語辭典「[表](https://dict.revised.moe.edu.tw/dictView.jsp?ID=457)」，指「分格或分項以列記事物的文件」，而 linked list 作為資料結構，全然沒有「分格」和「分項」的意涵。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
#### DDDD EEEE
```diff=
begin[i] = left;
- end[i] = DDDD;
+. end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
- end[i + 2] = EEEE;
+ end[i + 2] = list_tail(&right);
```
這裡主要就是要把`begin[i]` `end[i]`分別存`left`的頭尾，而`begin[i+2]` `end[i+2]`存`right`的頭尾，讓我們再下一次迴圈中去分別比較，<s>有點`divide and conquer`的感覺</s>，
:::danger
工程人員說話要精準，避免說「感覺」
:::
:::info
是使用到`divide and conquer`的概念來實作，把大問題拆成小問題來個別解決
:::
### 程式碼解釋
這個快速排序法是使用非遞迴方式，並在 `linked list` 上實作，主要做法如下，
1. 首先假設初始佇列如下
```graphviz
digraph structs {
node[shape=plaintext];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
node[shape=box];
struct0 [label= "4"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "1"];
{
rank="same";
struct0 -> struct1
struct1 -> struct2
struct2 -> struct3
struct3 -> struct4
}
pivot -> struct0;
L -> struct0;
R -> struct4;
p -> struct1;
}
```
2. 我們會先初始化兩個 `begin` `end` 陣列， `size` 為 `2 * n` ， `n` 是佇列的長度
另外初始化兩個 `left` `right` 的指標，以及一個 `i` ，記錄目前 `begin` `end` 內元素的長度
3. 我們挑選最左邊的元素作為 `pivot` ，並<s>遍歷</s> 逐一走訪每個節點，把所有小於 `pivot` 的都放到 `left` ，其他放到 `right` ，結果如下圖
:::danger
注意用語。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
```graphviz
digraph structs{
node[shape=plaintext];
left [fontcolor="blue"];
pivot [fontcolor="red"];
right [fontcolor="blue"];
node[shape=box]
struct0 [label= "4"];
struct1 [label= "5"];
struct2 [label= "3"];
struct3 [label= "2"];
struct4 [label= "1"];
pivot -> struct0;
left -> struct2;
struct2 -> struct3;
struct3 -> struct4;
right -> struct1;
}
```
4. 將`left` 的頭尾分別存到 `begin[i]` `end[i]`
將 `right` 的頭尾分別存到 `begin[i+2] end[i+2]`
最後把 `pivot` 存到`begin[i+1]` `end[i+1]`
5. `pivit` 會逐漸右移，並且每次都先去處理 `pivot` 右邊部分的佇列，等到右邊部分的到達終止條件，終止條件就是 `begin[i] = end[i]` ，也就是只剩下一個元素，這時則將 `right` 的部分加入 `result` ，如下圖。
```graphviz
digraph graphname{
node[shape=box]
rankdir = LR
C[label=7]
D[label=5]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
{
rank="same";
pivot[label="pivot",shape=plaintext,fontcolor=blue]
pivot->D[color=blue];
}
{
rank="same";
left[label="left",shape=plaintext]
left->NULL2;
}
{
rank="same";
right[label="right",shape=plaintext]
right->C->NULL1;
}
pivot->left->right [color=white]
}
```
6. 隨著 `i--` ， 會將所有 `begin[i] = end[i]` 的點加入 `result` ，其餘的長度 `>1` 的佇列，則要再進行一次 `Divide and Conquer` ，直到所有人都變成單一節點，再依次加入 `result`
### 討論及改進
這份程式碼有幾個特點，
1. 會優先處理右邊的子集
2. `pivot` 選擇第一個元素
3. 用 `begin` `end` 陣列來模擬遞迴的情況
改進的方向有如下
1. 在選擇 `pivot` 上，如果只透過挑選最左邊的 `pivot` ，如果遇到已排序的陣列，反而是更消耗運算時間，所以如何有效率地挑選 `pivot` 可以是一個優化方向
1. 參考[避免 Quick Sort 的 Worst Case 發生](https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/#lwptoc4)，可以透過先亂數選取三個點，再取他們之間的中間值作為 `pivot` 值，可以避免選取到最小或是最大值的可能性。
2. 在小規模佇列去使用到 `quick sort` 可能反而會對排序需要花費更多的時間，或許可以設一個 `threshold` ，大於他可以使用 `quick sort` ，小於他就去呼叫較為簡單的排序法，例如 `bubble sort` `insertion sort`
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
### 測驗二
在 `merge` 函式，目的是要把 `a` `b` 合併，接著利用迴圈比較 a , b 的第一個節點,將較小者加入新鏈結串列的尾部, 加入後要將 tail 指標向後移,下次加入節點時才能繼續加入鏈結串列尾端, 因此 BBBB 為 &a->next，CCCC 則為 &b->next。
在 `build_prev_link` 中，目的是要把 `prev` 連接起來，通過一個迴圈，逐一走訪每個節點，並在最後把 `head` `tail` 之間的鏈結接起來，因此 `DDDD` 是 `tail->next` ， `EEEE` 是 `head->prev`
#### 討論及改進
在我看完程式碼後，直覺上會覺得 `merge_final` 跟 `merge` 這兩個函式太像了，只有頭跟尾巴的操作以及參數有差異，我會認為這兩個函式是可以合併的，但就會需要考慮到兩邊的 `input` 跟額外操作等等，但會是一個可以改進的方向
#### Galloping Mode
---
## [第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
<s>
#### AAAA
`hlist_add_head` 是要將節點添加到鏈表的頭部，因此 `AAAA` 要填入 `h->first` ，讓 `n->next` 指向 `h->first` ，把 `n` 接到 `h` 的頭上面
#### BBBB
```diff
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, BBBB) {
+ hlist_for_each (p, &heads[hash]) {
- struct order_node *on = CCCC(p, struct order_node, node);
+ struct order_node *on = list_entry(p, struct order_node, node);
if (num == on->val)
return on->idx;
}
return -1;
}
```
</s>
:::danger
不用列出參考題解，你只要專注在程式碼和你的洞見。
:::
這個 find 函數的目的是在指定的 `hash table` 中查找特定值 num 對應的索引。
### 測驗二
### 測驗三
Sign in with Wallet
Connect another wallet