# 2024q1 Homework2 (quiz1+2)
contributed by < `LindaTing0106` >
## 第一週測驗題
### 測驗 1
此函式目的在於找到串列的尾端，故在 `*left` 和 `(*left)->next` 不等於 null 的情況下，
`left` 應該要等於 `&(*left)->next` ，也就是 `*left` 下一個節點的地址。
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
此函式是在計算整個串列的長度，所以 `while` 中只需要判斷 `*left` 當下的節點是否為 null ，如有指向節點，則可以持續往下一個節點，並計算長度。
則 `left` = `&(*left)->next`。
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
此處 `CCCC` 填入 `p->next` ，因為此函式需要去遍歷串列的每個節點，並根據他們大於或是小於 pivot 的值，決定應該插入 `right` 或是 `left` 。
```c
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
原本想法是因為 begin 和 end 儲存一段串列的頭與尾，像是前面的
```c
begin[0] = *list;
end[0] = list_tail(list);
```
所以 `DDDD` = `list_tail(left)`， `EEEE` = `list_tail(right)`。
後來發現是傳進去的型態問題， `node_t *list_tail(node_t **left)` 傳入的型態應該為 pointer of pointer of node_t ，故將答案改為 `DDDD` = `list_tail(&left)`， `EEEE` = `list_tail(&right)`。
```c
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
```
#### 延伸問題：
##### 解釋上述程式碼的運作原理。
上述的快速排序法是使用非遞迴的方式實作。
還沒進入迴圈之前， `begin[0]` 和 `end[0]` 分別會指向串列的頭與尾。
```graphviz
digraph First {
#rankdir = LR;
node[shape=box];
{rank="same"; 4; 1 ;3 ;5 ; 2 ; 7;}
4 -> 1 -> 3 -> 5 -> 2 -> 7;
node[shape=none];
{rank="same"; 4; 1 ;3 ;5 ; 2 ; 7;NULL}
7->NULL
subgraph subgraph_name{//子图
rankdir = BT;
node[shape=none];
"begin[0]" -> 4;
"end[0]" -> 7;
}
}
```
先選定 4 作為 pivot ，並且將 pivot 從串列移除，之後開始比較 pivot 與串列各個節點之間的大小，將小於 pivot 的節點 `list_add` 進 `left` ，大於 pivot 的節點 `list_add` 進 `right`。
```graphviz
digraph pivot_is_4 {
node[shape=box];
4;
node[shape=none];
pivot;
pivot->4
}
```
```graphviz
digraph move_p {
#rankdir = LR;
node[shape=box];
{rank="same"; 1 ;3 ;5 ; 2 ; 7;}
1 -> 3 -> 5 -> 2 -> 7;
node[shape=none];
{rank="same"; 1 ;3 ;5 ; 2 ; 7;NULL}
7->NULL
subgraph subgraph_name{//子图
rankdir = BT;
node[shape=none];
p -> 3;
n -> 1;
}
}
```
排列好大小後，利用 `begin[i]` 和 `end[i]` 指標指向串列的頭跟尾。
`begin[i]` 和 `end[i]` 指向的是比 pivot 小的串列， `begin[i+2]` 和 `end[i+2]` 指向的是比 pivot 大的串列， `begin[i+1]` 和 `end[i+1]` 則指向 pivot 。
```graphviz
digraph begin_end {
rankdir = LR
subgraph subgraph_name{
node[shape=box];
7->5;
}
subgraph subgraph_name{
node[shape=box];
2->3->1;
}
subgraph subgraph_name{
node[shape=box];
4;
}
node[shape=none];
right->7;
left -> 2;
"begin[0]"->2
"end[0]"->1
"begin[1]"->4
"end[1]"->4
"begin[2]"->7
"end[2]"->5
}
```
由於 `i += 2;` 所以先從上一回合比 pivot 大的串列開始執行上述動作。
將 7 當作 pivot 所以在比大小的時候， 將節點 5`list_add` 進 `left`，而`right` 只能指向 NULL 。
```graphviz
digraph pivot2 {
rankdir = TB
subgraph subgraph_name{//子图
node[shape=box];
7;
}
node[shape=none];
"begin[3]"->7
"end[3]"->7
pivot->7
}
```
```graphviz
digraph round2 {
#rankdir = LR
subgraph subgraph_name{//子图
node[shape=box];
5;
}
subgraph subgraph_name{//子图
node[shape=none];
NULL;
}
node[shape=none];
left->5;
"begin[2]"->5
"end[2]"->5
right->NULL
"begin[4]"->NULL
"end[4]"->NULL
}
```
再下一回合 `i = 4` 時，因為 `begin[4]` 和 `end[4]` 都指向 NULL ，所以進到else中，並且 `i--` ，來到 `i = 3` ，由於 `begin[3]` 和 `end[3]` 都指向節點 7，故將 7 `list_add` 進 `result` ，且 `i--` ， `i = 2` 時也是相同操作，將 5 `list_add` 進 `result` 。重複以上步驟，最終 `result` 則會為一個遞增串列，以上及為程式碼的運作原理。
##### 提出改進方案並予以實作。
從上述程式碼可以看出他永遠都是選擇第一個節點作為 pivot ，但當最差情況發生時的時間複雜度會來到 O(n²) ，像是 `[1, 2, 3, 4, 5]` 則每次選到的 pivot 都為最左邊的數字，如此 `left` 都為 NULL 而 `right` 為除了 pivot 以外的節點。如此每次選擇 pivot 後，都要遍歷剩下的節點，那麼就可以使用 Median of Medians Algorithm 的方法去規避最差情況發生。
##### 使用 Linux 核心風格的 List API 改寫上述程式碼
[程式碼](https://github.com/LindaTing0106/linux2024-homework2/blob/main/QuickSort/QuickSort.c)
在程式碼中引入 list.h 函式，並將 node_t 改為串列連接。
```diff
+#include "list.h"
typedef struct __node {
- struct __node *left, *right;
- struct __node *next;
+ struct list_head list;
long value;
} node_t;
```
將程式碼內部用到 node_t 的函式，都改寫為 list_head 的型態。
由於改為 list_head 的型態，故可以將 list_tail 的函式刪除，直接使用 list->prev 的方式表示最尾端的端點，故也將 end 移除。但因為要保存每次分治的串列，故這裡的 begin 需要配置 list_head 的空間。
```diff
- begin[0] = *list;
- end[0] = list_tail(list);
+ for (int be = 0; be < max_level; be++){
+ begin[be] = list_new();
+ }
+ begin[0] = list;
while (i >= 0) {
- node_t *L = begin[i], *R = end[i];
+ struct list_head *L = begin[i]->next, *R = begin[i]->prev;
```
此外將原本很多單純用 = 賦予值的部分，改為運用 `list_splice_init` 、 `list_move` 。
##### 並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
### 測驗 2
`AAAA` 填入 `&head` ，則可以透過指標的指標進行編寫。
```c
struct list_head *head;
struct list_head **tail = AAAA;
```
當此處的priv不為 NULL ，則會將型態轉為整數的指標，使用*取值後再加 1 。初步認為這裡應是對應到最後算出比較次數的計算。
```c
int compare(void *priv, const struct list_head *a, const struct list_head *b)
{
if (a == b)
return 0;
int res = list_entry(a, element_t, list)->val -
list_entry(b, element_t, list)->val;
if (priv)
*((int *) priv) += 1;
return res;
}
```
在比較完兩個節點的大小後，使用 `*tail` 將較小的節點連接到 head ，而後應該要將 `tail` 指向此節點的 next ，讓下次比較大小時，較小的節點可以繼續接在 `*tail` 處，也就是讓尾端的 next 可以放入下一個節點的地址。
故 `BBBB` 應該填入 `&(*tail->next)` ， 但因為要填入最精簡的程式碼，故寫成 `&a->next` 。
而 `CCCC` 只是換成在如果節點 b 比 a 的值小的情況，所以可以直接填入 `&b->next` 。
```c
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB;
```
從此段程式碼來看， `list` 最終會指向 NULL ，而需要補上 `DDDD` 和 `EEEE` 才能使整個串列變成雙向環狀鏈結串列，所以需要將 `list` 的前一個節點，也就是 `tail` 的下一個節點變為 `head` ，並且 `head` 的上一個節點也應該要為 `tail` 。故 `DDDD` 填入 `tail->next` ，而 `EEEE` 為 `head->prev` 。
```c
static void build_prev_link(struct list_head *head,
struct list_head *tail,
struct list_head *list)
{
tail->next = list;
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
/* The final links to make a circular doubly-linked list */
DDDD = head;
EEEE = tail;
}
```
在這段程式碼中我們可以觀察到 `stk_size` 此變數，一開始是設為 0 ，而在後面找 run 的迴圈裡，此變數也會更著增加，從這裡我們可以判斷 `stk_size` 是表示著切了幾個 run 的個數，並且在各個合併的函示中， `stk_size` 的數量也會減少。
而在 `build_prev_link(head, head, stk0);` 此函式中，我們可以得知是在將最後合併出來，只剩下一個 run 的串列修正為雙向環狀鏈結串列，故 `FFFF` 填入 1。
```c
void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
```
#### 延伸問題：
##### 解釋上述程式碼的運作原理。
在上述程式碼內，並無設定 minrun 的部分，假設被傳入 `find_run` 的 list 。
```graphviz
digraph find_run {
rankdir = LR;
node[shape=box];
5->4->3->6->1;
}
```
因為 5 > 4 的關係想辦法讓這段 run 反轉。
```graphviz
digraph de {
rankdir = LR;
node[shape=box];
5;
4->3->6->1;
node[shape=none];
5-> NULL;
list->4
next->3
head->4
prev->5
}
```
最後回傳回主程式遞增的 run ( 稱 run1 ) ，以及另一個還沒被排序過的串列。
```graphviz
digraph de2_break {
rankdir = LR;
node[shape=box];
5;4;3;
6->1;
node[shape=none];
3->4->5-> NULL;
list->3
next->6
head->3
prev->4
"result.head"->3
"result.next"->6
}
```
`tp` 會將排序過的 run 的 `head` 串接在一起，經過剛剛的 `find_run` ，現在 run 的數量等於 1 ，接著進入 `merge_collapse` ，但因為 run==1 ，所以直接跳出。
再跑一次迴圈後，剛剛剩下來沒有被排序的串列，經過 `find_run` 的處理後， `result.head` 的指針會指向處理好的 run ，在這裡程式是用 `result.head->prev` 指向 run1 。
```graphviz
digraph run2 {
rankdir = LR;
node[shape=box];
1;6;
node[shape=none];
1->6->NULL
"result.head"->1
"result.next"->NULL
}
```
之後再次進到 merge_collapse 函式，根據是否滿足上面提到的原則，來決定要不要進行合併。
##### 提出改進方案並予以實作。
明顯可以發現上述程式碼中並沒有包含 minrun 的實作，故應將 minrun 加入程式的實作。 minrun 的大小為，將總資料長度轉為二進位後的前 6 位數字，若 6 位數字後不為 0 ，則加 1。
## 第二週測驗題
### 測驗 1
```graphviz
digraph hashTable {
rankdir= "LR";
node [shape= "record"];
node2 [label= "<0>|<1>|<2>|<3>|<4>"];
node3 [label= "<0>val = 3|idx = 1"];
node4 [label= "<0>val = 9|idx = 0"];
node2:<0>->node4;
node2:<1>->node3;
node [shape="none"];
node2:<2>->NULL;
}
```
這段重建二元樹的程式碼，是先從 `TreeNode *buildTree` 開始，首先程式會先創一個空的 hash table ，並且利用 `void node_add` 將 `inorder` 的節點放入 hash table 中，其中節點資訊包含了數值和位置。
```graphviz
digraph hashTable {
rankdir= "LR";
node [shape= "record"];
node2 [label= "<0>|<1>|<2>|<3>|<4>"];
node3 [label= "<0>val = 3|<1>idx = 1"];
node4 [label= "<0>val = 9|<1>idx = 0"];
node2:<0>->node4;
node2:<1>->node3;
node3[fontcolor=red];
node [shape="none"];
node2:<2>->NULL;
}
```
之後在 `TreeNode *dfs` 中，會利用指標 `*tn` 去存取目前在前序中最前面的節點的數值，當作此子樹的頭，以及利用這個數值在 `int find` 中找尋其在中序裡的位置。
```graphviz
digraph tnleft {
node [shape= "record"];
node1 [label="<0>3|<1>9|<2>20|<3>15|<4>7"];
node [shape="none"];
pre_low->node1:1;
pre_high->node1:1;
}
```
```graphviz
digraph tnleft {
node [shape= "record"];
node1 [label="<0>9|<1>3|<2>15|<3>20|<4>7"];
node [shape="none"];
in_low->node1:0;
in_high->node1:0;
}
```
其中 `tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size);` ，會持續遞迴出左子樹的函式。 `pre_low + 1` 做為下輪的 `int pre_low` 是因為第一個已經被當作頭了，所以 `pre_low` 就往前一格。 `pre_low + (idx - in_low)` 做為下輪的 `int pre_high` ，則是利用 `idx - in_low` 可以算出左子樹有的節點數量，所以用 ```
pre_low +
左子樹有的節點數量
```，得出後面 `pre_low + (idx - in_low)` 格的節點都是左子樹的節點。 `idx - 1` 做為下輪的 `int in_high` 是因為在中序中，頭左邊的所有節點都是左子樹的節點。
```graphviz
digraph tnleft {
node [shape= "record"];
node1 [label="<0>3|<1>9|<2>20|<3>15|<4>7"];
node [shape="none"];
pre_low->node1:2;
pre_high->node1:4;
}
```
```graphviz
digraph tnleft {
node [shape= "record"];
node1 [label="<0>9|<1>3|<2>15|<3>20|<4>7"];
node [shape="none"];
in_low->node1:2;
in_high->node1:4;
}
```
而 `tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size);` ， `pre_high - (in_high - idx - 1)` 做為下輪的 `int pre_low` 是因為 `(in_high - idx - 1)` 可以得出在前序中右子樹的尾到右子樹的頭中間的節點數量，故用 `pre_high` 減去，可得右子樹的頭的節點的位置。 `idx + 1` 做為下輪的 `int in_low` ，則是因為在中序中頭的右側即全為右子樹節點。
### 測驗 2
`LRU Cache` 是將一種快取的實做方式，當有新資料進來時，將快取中最後一次被存取的部分給替代掉。
需要寫一般串列和 hash table 的串列，來去串接節點是因為可以利用 hash table 提升我們在取值時的速度，如果只有一般串列，那我們必須遍歷 `count` 個節點找尋我們要的節點。而需要一般串列是因為我們這樣才有哪個節點是最後被使用的紀錄。
```c
typedef struct {
int capacity; // 其LRUCache的大小
int count; // 目前使用的數量
struct list_head dhead; // 串接所有的節點
struct hlist_head hhead[]; // 用 hash table 的方式儲存節點
} LRUCache;
```
`LRUCache *lRUCacheCreate(int capacity)` 會根據其容量大小來為其配置記憶體大小。
`void lRUCacheFree(LRUCache *obj)` 利用傳入的指標，將其指向的快取給刪除，程式裡面用到 `list_entry` 函式，來取得快取中的串列的物件，再將其各個刪除。應該也可以使用 `hlist_del` 將 hash table 中串列的節點移除。
`int lRUCacheGet(LRUCache *obj, int key)` 程式碼中會先遍歷對應的 hash table 中的串列，如果有找到對應的值，則將 dlist 中該節點，搬去串列的最前方，並回傳該值，如果找不到，則回傳 `-1` 。
`void lRUCachePut(LRUCache *obj, int key, int value)`
是希望將給定的值放入快取中，首先會利用 key 求出 hash 值，再利用 hash 值來檢查是否此 key 值已經使用過了。
- 如果**使用過了**，則將此節點移動至串列最前方並且將 value 改為新的值。
- 如果**沒有使用過**，則比對傳進來的快取是否已經滿了。
- 如果**空間滿了**，則將最後一個使用的節點移至串列的最前方，並將其在 hash 中對應的位置刪除，並且再將其放入 hash table 中。
- 如果**空間沒有滿**，則新配置一個空間，並將節點加入串列，也加入 hash table 中，並將 count++ 。
這段程式碼相當為將 &cache->node move 至 &obj->hhead[hash] ，既然都有 list_move 了，也可以實作出 hlist_move 。
```c
hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);
```
### 測驗 3
`find_nth_bit` 在指定的記憶體空間找出第 N 個設定的位元。
`__ffs(unsigned long word)` 是用來找一段 long 中，最高的位元是哪一位，程式碼當中用了多個判斷式。
其中原理為，當 word & 0xf 為 0 則表示在 4 位元內 word 的值都為 0 ，故 word 必大於 $2^4$ ，以此類推。
```c
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
```
`find_nth_bit` 的程式碼運作原理為，先比較要找的數字有無超過限制的 `size` ，並檢查 `size` 的設置是否符合規範， `GENMASK(h, l)` 是將 `h` 到 `l` 間的位元變為 1 ， 故 `val` 為 `addr` `h` 到 `l` 間的值，如果 `val` 有值，則利用 `fns` 找到為 1 的最高位元並回傳。
Sign in with Wallet
Connect another wallet