# 2024q1 Homework2 (quiz1+2)
contributed by < `v0103` >
## 第一周測驗題
### 測驗`1`
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
因為這裡使用的是單向鏈結串列，因此需要確保傳入的指標在該函式執行完依舊指向串列的頭，參考[你所不知道的 C 語言: linked list 和非連續記憶體](/YA7RMqd6RE2UL8OmmjU9PQ)提到的 indirect pointer，該函式用 `node_t **left`，而非 `node_t *left`。由於 `left` 是指向 `list` 的指標，`*left` 是 `list` ，`*left->next` 則是 `node1`，`left = &(*left->next)` 就會將 `left` 更新為 `node1`，經過while迴圈不斷往後找就可以找到串列的尾。
```mermaid
graph LR
subgraph linked list
list==>node1==>node2
end
subgraph pointer to pointer
left==>list
end
```
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
`list_length` 函式要計算串列總長，跟上面的 `list_tail` 一樣，使用 while 迴圈不斷的找下一個 `node` ，解題思路跟上面一樣，所以 `BBBB` 會是 `*left->next`。
### `quick_sort`
原方法 [ Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 首先選定最左邊的數字為 `pivot`，分別使用 `L` 由左往右移動，`R` 由右往左移動，在 LR 移動過程會把小於 `pivot` 的數字放到左側，大於的則放到右側，最後 LR 相遇後再把 `pivot` 放到該點，以此完成排序。再來就是對 `pivot` 右側做排序，右側排序完了再對 `pivot` 左側做排序。
有了原方法的排序概念接下來看看題目 `quick_sort` 和原方法有何異同。
```c
node_t *L = begin[i], *R = end[i];
```
這裡一樣使用 `begin` 和 `end` 作為堆疊，去儲存尚未排列好的序列。
```graphviz
digraph {
node [shape=box];
rankdir = LR;
4 -> 1 -> 3 -> 5 -> 2 -> 7;
node [shape=plaintext, fontsize=15];
7 -> NULL;
node [fontcolor=green];
L ->4;
rank=same {L 4};
R ->7;
rank=same {R 7};
}
```
```c
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
```
一樣選擇 `L` 作為 `pivot`，`value` 則是 `pivot` 的值。這邊多了一個 `node_t *p` 指向 `pivot->next` 目前還不知道其作用。
```graphviz
digraph {
node [shape=box];
rankdir = LR;
4 -> 1 -> 3 -> 5 -> 2 -> 7;
node [shape=plaintext, fontsize=15];
7 -> NULL;
node [fontcolor=red];
pivot -> 4;
rank=same {pivot 4 };
node [fontcolor=red];
p -> 1;
rank=same {p 1 };
node [fontcolor=green];
L ->4;
rank=same {L 4};
R ->7;
rank=same {R 7};
}
```
```c
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
可以看到這是一個 while 迴圈，運行到 `p==NULL` 才會結束，每次會用新指標 `n` 來存取 `p` 所指向的節點，`n->value > value ? &right : &left` 這邊判斷該次迴圈所指到的節點是否大於 `pivot` ，大於則會執行 `list_add(&right, n)` 將該節點放到 `right` 這個串列，反之，則放到`left` 串列。看起來這個迴圈的作用就是走訪串列，並將小於 `pivot` 的節點放左側，大於 `pivot` 的節點放右側。因此可以判斷出 `CCCC` 為 `p->next`。
`n` 指向 `p` 的位置後 `p` 指向 `p->next`。
```graphviz
digraph {
node [shape=box];
rankdir = LR;
4 -> 1 -> 3 -> 5 -> 2 -> 7;
node [shape=plaintext, fontsize=15];
node [fontcolor=red];
pivot -> 4;
// rank=same {pivot 4 };
node [fontcolor=red];
p -> 3;
rank=same {p 3 };
node [fontcolor=red];
n -> 1;
rank=same {n 1 };
node [fontcolor=green];
L ->4;
rank=same {L 4};
R ->7;
rank=same {R 7};
}
```
`n->value` < `pivot->value`，所以 `n` 要放到 `left` 串列。
```graphviz
digraph {
node [shape=box];
rankdir = LR;
1 ;
node [shape=plaintext, fontsize=15];
node [fontcolor=black];
left -> 1;
}
```
下一輪迴圈 `n` 指到 3，因此將 3 也放到 `left`。
```graphviz
digraph {
node [shape=box];
rankdir = LR;
3 -> 5 -> 2 -> 7;
4 ;
node [shape=plaintext, fontsize=15];
node [fontcolor=red];
pivot -> 4;
node [fontcolor=red];
p -> 5;
rank=same {p 5 };
node [fontcolor=red];
n -> 3;
rank=same {n 3 };
node [fontcolor=green];
L ->4;
rank=same {L 4 };
R ->7;
rank=same {R 7};
}
```
最後會將原串列拆成三組串列。
```graphviz
digraph {
node [shape=box];
rankdir = LR;
1 -> 3 -> 2;
node [shape=plaintext, fontsize=15];
node [fontcolor=black];
left -> 1;
node [shape=box];
rankdir = LR;
5 -> 7;
node [shape=plaintext, fontsize=15];
node [fontcolor=black];
right -> 5;
node [shape=box];
rankdir = LR;
4;
node [shape=plaintext, fontsize=15];
node [fontcolor=red];
pivot -> 4;
}
```
```c
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;
i += 2;
```
有了 `left` `right`兩個串列，再來要將他們存起來。`begin` `end` 會做為下一輪迴圈的 `L` `R`，因此如果 `begin[i]` 是 `left` 可以得知 `DDDD` 是 `list_tail(&left)`，同理 `EEEE` 是 `list_tail(&right)`。最後 `i += 2` 所以跟原方法一樣是先排序右側。
:::warning
TODO : 用list API改寫，提出可避免最差狀況的快速排序實作
:::
### 測驗`2`
首先在閱讀題目時講到 minrun 的選擇策略時，有個令我疑惑的點。
:::info
顯然，選擇 minrun 的策略是 Timsort 的關鍵，其中一個實務上的方法是，取資料長度 N 的前 6 位，若剩餘位中任何一位被設置，則加 1。這主要是為了在處理隨機數列時，使得 N 能夠被 minrun 切分成 2 的冪的 run，以便在合併時達到最佳平衡。
:::
其中，**取資料長度 N 的前 6 位**我一直看不懂是甚麼意思，google 後才知道是**將資料長度 N 轉換為二進位表示，並取其前 6 位**的意思。
以題目的例子 N = 2112為例，2112 換成二進位是 100001000000 ，取其前六位也就是 100001 = 33，剩餘的六位都是 0，因此選擇 33 作為 minrun。
---
#### 運行原理
我解這題的方法是先大略理解了 Timsort 的原理，然後按照前後的結構來處理問題，先填補空缺的部分，最後再完全理解每個函式的作用。
首先，我看到了 `timsort` 函式，首先將原本的雙向鏈結串列轉換為單向的，然後使用 `find_run` 函式將原始串列劃分為多個 run。在這個拆分的過程中，同時使用 `merge_collapse` 函式來確保堆疊上的 run 長度保持平衡。接著，使用 `merge_force_collapse` 函式確保 run 的數量少於 3。如果 run 的數量剩餘 2，則執行 `merge_final` 函式進行最後的合併。同時，裡面包含一個 `build_prev_link` 函式，將原本的單向鏈結串列轉換為雙向的。如果 run 的數量剩餘 1，則直接執行 `build_prev_link` 函式。
我覺得一個有趣的地方是，在 `find_run` 函式中，將 run 的長度存儲在 `head->next->prev` 中。這樣做的好處是，在進行合併時可以直接讀取兩個 run 的長度，而不需要額外記錄或者重新掃描一次。
#### 解題思路
:::info
`AAAA` `BBBB` `CCCC` 都在 `merge` 函式。
:::
在 `merge` 函式中 `tail` 負責指向串列的尾部，讓下一次迴圈比較完的較小值可以知道要接在哪，所以 `tail` 初始值應該指向 `head`，`AAAA` 為 `&head`。
```c
struct list_head *head;
struct list_head **tail = AAAA;
```
在這段程式碼中，當 `a` 小於 `b` 時，在第一輪迴圈中，會將 `*tail`，也就是 `head`，設定為 `a`。接著，為了確保下一輪迴圈中較小的值能夠接在 `a` 後面，我們需要更改 `tail` 的指向位置。因此，`BBBB` 為 `&a->next`。
```c
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB;
a = a->next;
if (!a) {
*tail = b;
break;
}
}
```
同理，`CCCC` 為 `&b->next`。
```c
else {
*tail = b;
tail = CCCC;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
```
前面有提到`build_prev_link` 函式的作用是將原本的單向鏈結串列轉換為雙向的。根據註解可以得知這兩行的作用是執行最後一步，讓串列的頭尾相接，因此 `DDDD` 為 `tail->next`， `EEEE` 為 `head->prev`。
```c
/* The final links to make a circular doubly-linked list */
DDDD = head;
EEEE = tail;
```
:::warning
TODO : 提出改進方案，整合進lab0-c
:::
---
## 第二周測驗題
### 測驗`1`
#### 運行原理
#### 解題思路
### 測驗`2`
### 測驗`3`
#### 運行原理
要找出第 N 個設定的位元，要先能找出第 1 個設定的位元，所以看到 `__ffs` 函式，使用多個 mask 逐步找出 `word` 中第 1 個設定的位元。我挑其中一個來講解。
下面條件若成立，表示 `word` 第 1 個設定的位元不在後 16 位，所以 `num` 計數要加 16 並且把 `word` 右移 16 位，檢查更高位元。
```c
if ((word & 0xffff) == 0) {
num += 16;
word >>= 16;
}
```
知道怎麼找第 1 個設定的位元，要找到第 N 個也就沒問題了。
`fns` 函式使用 while 迴圈，找到 `word` 第 1 個設定的位元後，再使用 `__clear_bit` 清除該位元，下一輪迴圈找到的就會是第 2 個設定的位元，以此循環便能找到第 N 個。
```c
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word) {
unsigned int bit = __ffs(word);
if (n-- == 0)
return bit;
__clear_bit(bit, &word);
}
return BITS_PER_LONG;
}
```
#### 解題思路
前面運行原理舉的例子是檢查後 16 位，mask 是 `0xffff`，所以這個檢查後 32 位的 mask `AAAA` 是 `0xffffffff`。
```c
#if BITS_PER_LONG == 64
if ((word & AAAA) == 0) {
num += 32;
word >>= 32;
}
#endif
```
從 `fns` 函式可以知道，`nr` 是第 1 個設定的位元的位置，`BIT_MASK` 的作用是把 `nr` 的位元設為 1 其他設為 0，所以要將 `p` 的第 `nr` 個位元位元清除，`BBBB` 會是 `~mask`。
```c
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
*p &= BBBB;
}
```
如果 `size` > `BITS_PER_LONG` 時，會執行此巨集。
```c
#define FIND_NTH_BIT(FETCH, size, num) \
({ \
unsigned long sz = (size), nr = (num), idx, w, tmp; \
\
for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
if (idx * BITS_PER_LONG + nr >= sz) \
goto out; \
\
tmp = (FETCH); \
w = hweight_long(tmp); \
if (w > nr) \
goto found; \
\
nr -= w; \
} \
\
if (sz CCCC BITS_PER_LONG) \
tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz); \
found: \
sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz); \
out: \
sz; \
})
```
Sign in with Wallet
Connect another wallet