# 2025q1 Homework2 (quiz1+2)
contributed by <```Charlie-Tsai1123```>
## 第一周測驗題 - [測驗1](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-1)
### ```list_insert_before```
```cpp
static inline void list_insert_before(list_t *l,
list_item_t *before,
list_item_t *item)
{
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
```
下圖的黑色部份是題目所用的 ```linked list``` ，紅色是 ```list_insert_before``` 傳入的參數，藍色則是指標的指標，這裡用箭頭來表示指標，所以由圖可以知道 ```p``` 初始話的位子在指向 ```head``` 指標的位子
```cpp
p = &l->head
```
由於要從 ```linked list``` 中找到 ```before``` 的位子 ```p``` 要移動到指向下一個指標的位子，由 ```*p``` 先找到現在指向的指標，再取下一個指標，最後藉由 ```&``` 取指向下一個指標的位子
```cpp
p = &(*p)->next
```
由下圖可知當找到 ```before``` 時（ ```*p = before```），需要變動指標，可以直接改動 ```p``` 所指向的指標，就可以直接變動 ```linked list``` 了，最後新元素的 ```next``` 也要指向 ```before``` 所在位子
```cpp
*p = item;
item->next = before;
```
### 解釋測試程式碼
### 合併排序
## 第一周測驗題 - [測驗2](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-2)
### 解釋程式碼運作原理
程式在執行 binary search tree (BST) 的 remove ，以下為 BST 的架構，每個節點會有指向左子樹的指標跟指向右子樹的指標，而 ```size``` 是記憶體區塊的大小
```cpp
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
```
```find_free_tree``` 是從 BST 中找到要被釋放的記憶體區塊位子 (```target```)
```cpp
block_t **find_free_tree(block_t **root, block_t *target);
```
```find_predecessor_free_tree``` 則是找到 ```node``` 左子樹中的最大值
```cpp
block_t *find_predecessor_free_tree(block_t **root, block_t *node);
```
在 ```remove_free_tree``` 中，把操作分成了三個 case :
* case 1 : 被 remove 的節點有左子樹跟右子樹
* 左子樹沒有右子樹 （左子樹的 root 是最大的點）
* 左子樹有右子樹 （左子樹有比左子樹 root 更大的點）
```cpp
if ((*node_ptr)->l && (*node_ptr)->r)
```
* case 2 : 被 remove 的節點只有左子樹或右子樹
```cpp
else if ((*node_ptr)->l || (*node_ptr)->r)
```
* case 3 : 被 remove 的節點沒有左子樹或右子樹
#### case 1 : If the target node has two children, we need to find a replacement.
在 ```remove``` 節點之前要找到代替它位子的節點，那就是左子樹中最大的點
==step 1 : 求左子樹最大的點==
因為最大的節點會在右子樹中，所以從左子樹不斷往右找，找到底就是左子樹中最大的節點了（ step 2 兩張圖中藍色的節點就是要找的，而紅色是要移除的節點 ）
```cpp
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
/* Verify the found predecessor using a helper function (for debugging).
*/
block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);
```
==step 2 : 移除節點並加上代替位子的節點==
左子樹的 ```root``` 是最大的節點 ：
1. 紀錄欲刪除節點右子樹的位子 ```old_right```
2. 將左子樹最大的節點 ```pred_ptr``` 移過去
3. 將右子樹 ```old_right``` 加到節點 ```*node_ptr``` 中
```cpp
/* If the predecessor is the immediate left child. */
if (*pred_ptr == (*node_ptr)->l) {
block_t *old_right = (*node_ptr)->r;
*node_ptr = *pred_ptr; /* Replace target with its left child. */
(*node_ptr)->r = old_right; /* Attach the original right subtree. */
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
}
```
左子樹更深的地方才是最大的節點：
1. 紀錄左節點 ```old_left``` , 右節點 ```old_right``` , 左子樹最大節點 ```pred_node```
2. 用 ```remove_free_tree``` 移除左子樹最大節點 ```pred_ptr``` （做完後可能變成 NULL）
3. 將左子樹最大節點 ```pred_node``` 代替欲移除的節點
4. 將左子樹 ```old_left``` , 右子樹 ```old_right``` 接到節點 ```*node_ptr``` 中
>[!Note]為什麼還要再存一次左子樹最大節點明明已經有 ```pred_ptr```
>因為經過 ```remove_free_tree(&old_left, *pred_ptr)``` 後，可能會變成 ```NULL```
```cpp
/* The predecessor is deeper in the left subtree. */
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
block_t *pred_node = *pred_ptr;
/* Remove the predecessor from its original location. */
remove_free_tree(&old_left, *pred_ptr);
/* Replace the target node with the predecessor. */
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
```
#### case 2 : If the target node has one child (or none), simply splice it out.
刪除的點是紅色的點，如果只有一個子樹，代替的點就是子樹的 root （藍色點）
<div style="display: flex;">
<img src="https://hackmd.io/_uploads/Hy19i0SnJx.png" style="width: 45%; margin-right: 10px;" />
<img src="https://hackmd.io/_uploads/BJO6iCH3kg.png" style="width: 45%;" />
</div>
#### case 3 : No children: remove the node.
<div style="display: flex;">
<img src="https://hackmd.io/_uploads/SJSO60B3Jx.png" style="width: 45%; margin-right: 10px;" />
<img src="https://hackmd.io/_uploads/ryr56ArnJx.png" style="width: 45%;" />
</div>
### 補完 ```find_free_tree``` 及 ```find_predecessor_free_tree``` 並測試
### 效能評比
## 第一周測驗題 - [測驗3](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)
### 解釋程式碼運作原理
#### ```rebuild_list_link```
黑色是原本的 ```linked list``` 可以發現一開始是 ```singly linked list``` ，那 ```rebuild_list_link``` 是將這種結構變成 ```circular doubly linked list```
* 8 ~ 12 行是完成 ```circular doubly linked list``` 中的藍色部份， ```prev``` 指標指向前一個 node
* 13 ~ 14 行完成 ```circular doubly linked list``` 中 cirsular 的部份，也就是紅色部份
```cpp=
static void rebuild_list_link(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *prev;
prev = head;
node = head->next;
while (node) {
node->prev = prev;
prev = node;
node = node->next;
}
prev->next = head;
head->prev = prev;
}
```
```graphviz
digraph G {
nodesep=0.8
node [shape=rect];
{ rankdir=LR; rank=same; "head"; "10"; "20"; "30"; "40"; "50"; "NULL";}
"NULL" [style=dotted];
"head" -> "10" [constraint=false];
"10" -> "head" [constraint=false, color = blue]
"10" -> "20" [constraint=false];
"20" -> "10" [constraint=false, color = blue]
"20" -> "30" [constraint=false];
"30" -> "20" [constraint=false, color = blue]
"30" -> "40" [constraint=false];
"40" -> "30" [constraint=false, color = blue]
"40" -> "50" [constraint=false];
"50" -> "40" [constraint=false, color = blue]
"50" -> "head" [dir=both, color=red, constraint=false];
"50" -> "NULL"[style=dotted];
}
```
#### ```quick_sort```
實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼，用 ```begin``` 儲存切割的每個片段起始點，而對片段的處理分成以下幾種 :
1. 片段長度為 1 :
加入到 ```result``` 內 (不需要排序了)
2. 片段長度不為 1 :
分成三個片段， ```pivot``` (最左邊的節點)、比 ```pivot``` 還要小的片段、比 ```pivot``` 還要大的片段
### 研讀 〈[A comparative study of linked list sorting algorithms](https://dl.acm.org/doi/pdf/10.1145/225890.225893)〉
### 用 ```List API``` 實作排序
## 第二周測驗題 - [測驗1](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-1)
### 解釋程式碼運作原理
與上週測驗不同的是這周採用遞迴的方式實作，而相同的點是一樣會用三個 ```linked list``` 來存(```pivot``` 、較大、較小)，首先找到 ```pivot``` (最左邊的點)並移除
```cpp
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
```
接著找到較大跟較小的節點分別存到 ```list_greater``` 跟 ```list_less``` 中
```cpp
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
```
用遞迴方式排序好 ```list_less``` 跟 ```list_greater```
```cpp
list_quicksort(&list_less);
list_quicksort(&list_greater);
```
到這步時理論上 ```head``` 會是 singular 的節點，節點都分布在 ```pivot```、```list_less```、```list_greater``` 當中，接下來將節點依序放入 ```head``` 中
```cpp
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
```
### 改進 ```random_shuffle_array```
### 若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
>Stable sorting & unstable sorting
Stable sorting 代表相同數值的元素在經過排序後，相對順序不會改變，這對於多索引排序很重要；unstable sorting 則不能保證相同數值的元素排序後的相對順序能不改變。
因為 ```list_for_each_entry_safe``` 是由前到後去遍歷的，如果用 ```list_move``` 會移到 linked list 前面，相對的順序就改變了
```graphviz
digraph g {
node[shape = plaintext];
pivot [fontcolor="red"];
"list_less" [fontcolor="purple"];
"list_greater" [fontcolor="purple"];
"head"
"item"
null1 [label=""];
null2 [label=""];
null3 [label=""];
null4 [label=""];
node[shape=box];
n0 [label="0"];
n2_1 [label="2", color=orange];
n2_2 [label="2", color=blue];
n3 [label="3"];
n4 [label="4"];
n5 [label="5"];
{
rank="same";
}
pivot -> n4 -> null1 [dir=both];
list_less -> n0 -> null2 [dir=both];
list_greater -> n5 -> null3 [dir=both];
head -> n2_1 -> n2_2 -> n3 -> null4 [dir=both];
item -> n2_1
}
```
使用 ```list_move``` 加在 linked list 前面 (兩個 2 順序對調了) :
```graphviz
digraph g {
node[shape = plaintext];
pivot [fontcolor="red"];
"list_less" [fontcolor="purple"];
"list_greater" [fontcolor="purple"];
"head"
"item"
null1 [label=""];
null2 [label=""];
null3 [label=""];
null4 [label=""];
node[shape=box];
n0 [label="0"];
n2_1 [label="2", color=orange];
n2_2 [label="2", color=blue];
n3 [label="3"];
n4 [label="4"];
n5 [label="5"];
{
rank="same";
}
pivot -> n4 -> null1 [dir=both];
list_less -> n2_2 -> n2_1 -> n0 -> null2 [dir=both];
list_greater -> n5 -> null3 [dir=both];
head -> n3 -> null4 [dir=both];
item -> n3
}
```
使用 ```list_move_tail``` 加在 linked list 後面 (兩個 2 順序不會對調) :
```graphviz
digraph g {
node[shape = plaintext];
pivot [fontcolor="red"];
"list_less" [fontcolor="purple"];
"list_greater" [fontcolor="purple"];
"head"
"item"
null1 [label=""];
null2 [label=""];
null3 [label=""];
null4 [label=""];
node[shape=box];
n0 [label="0"];
n2_1 [label="2", color=orange];
n2_2 [label="2", color=blue];
n3 [label="3"];
n4 [label="4"];
n5 [label="5"];
{
rank="same";
}
pivot -> n4 -> null1 [dir=both];
list_less -> n0 -> n2_1 -> n2_2 -> null2 [dir=both];
list_greater -> n5 -> null3 [dir=both];
head -> n3 -> null4 [dir=both];
item -> n3
}
```
## 第二周測驗題 - [測驗2](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-2)
### 解釋 counting leading zero ```clz```
### 解釋 ```sqrti```
#### 十分逼近法
實作 ```sqrti``` 其實是用到二分逼近法，那什麼是二分逼近法呢？可以聯想到國中所教的十分逼近法。
想想國中是如何求 $\sqrt{2}$ 的小數，首先找到它介於哪兩個整數間
$$1 < \sqrt{2} < 2$$
接著往更小的精度下去找
$$1.4 < \sqrt{2} < 1.5$$
$$1.41 < \sqrt{2} < 1.42$$
$$...重複此步驟$$
$$1.41421356 < \sqrt{2} < 1.41421357$$
所以 $\sqrt{2}$ 可以表示成
$$
1 \times \color{red}{10^1} +
4 \times \color{red}{10^{-1}} +
1 \times \color{red}{10^{-2}} +
4 \times \color{red}{10^{-3}} +
2 \times \color{red}{10^{-4}} +
1 \times \color{red}{10^{-5}} +
3 \times \color{red}{10^{-6}} + \dots
$$
#### 二分逼近法
有了十分逼近法的概念就能對二分逼近法有更深的理解了，假設我們想要求 $y$ 使的 $y^2 = x$
那我們可以先求 $x$ 跟 $y$ 的精度，若 $x$ 換成二進位後，第 $k$ 位元是最高為 1 的位元，那可以獲得以下資訊 :
$$
2^k <= x < 2^{k+1}
$$
$$
2^{k/2} <= y < 2^{(k+1)/2}
$$
$$
y = a_1 \times \color{red}{2^{k/2}} + a_2 \times \color{red}{2^{k/2 - 1}} + a_3 \times \color{red}{2^{k/2 - 2}} + \dots + a_{k/2} \times \color{red}{2^{1}} + a_{k/2 + 1} \times \color{red}{2^{0}}
$$
因此我們只需要求得 $a_1$ ~ $a_{k/2 + 1}$ 的係數值 ( 0 或 1 )就能算出 $\sqrt{x}$ 的估計值，以下說明如何只用二分逼近的概念實作效率超極低的開更號程式
首先找出 $y$ 的範圍， total_bits - 1 - clz64(x) 可以算出 $x$ 最大為 1 的位元位子也就是上述的 $k$ ，接著除以 2 (>>1) 就能找出 $y$ 可能最大為 1 的位元位子也就是 $k/2$ (shift) 而 **m 就是 2^k/2^** ，m 就是檢查的第一個值
eg:
x = 11001
| k | k/2 (shift) | m |
| --- |:-----------:|:--------:|
| 5 | 2 | 2^2^ = 4 |
```cpp
int shift = (total_bits - 1 - clz64(x)) >> 1;
m = 1ULL << shift;
```
接著開始找係數也就是估計， b 是估計值看看係數補上 1 後也就是加上 m 的值看看是否會大於 x 如果不會將 y 加上 m ，最後檢查下一位 (k/2 - 1) 然後重複直到 m = 0
eg:
x = 11001 = 25
k/2 = 2
\
\begin{array}{c c c}
\textbf{1st} & \textbf{2nd} & \textbf{3rd} \\
\underset{\text{這裡!}}0 \quad {0} \quad 0 & 1 \quad \underset{\text{這裡!}}{0} \quad 0 & 1 \quad {0} \quad \underset{\text{這裡!}}0 \\
\text{(檢查第二位係數)} & \text{(檢查第一位係數)} & \text{(檢查第零位係數)} \\
m = 0b100 = 4 & m = 0b10 = 2 & m = 0b1 = 1 \\
y = 0 & y = 0b100 = 4 & y = 0b100 = 4 \\
b = y + m = 0 + 4 & b = y + m = 4 + 2 & b = y + m = 4 + 1 \\
x \geq b \cdot b \quad (\text{符合}) & \cancel{x \geq b \cdot b} \quad (\text{不符合}) & x \geq b \cdot b \quad (\text{符合}) \\
y = 4 & y = 4 & y = 5
\end{array}
1 0 1
y = 4 + 1 = 5
```cpp
while (m) {
uint64_t b = y + m;
if (x >= b*b) {
y += m;
}
m >>= 1;
}
```
以下是第一版沒效率算法
```cpp
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) >> 1;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
if (x >= b*b) {
y += m;
}
m >>= 1;
}
return y;
}
```
>[!Tip]為甚麼說沒效率呢?
因為乘除法相較於 bitwise 的操作使用了更多的 CPU cycles
#### 使用乘法公式優化
原本的 b 是估計值，用來估計 y 可能得值，那在優化的版本，我們將 ==b 的定義改為相較於上次的 y^2^ 新的 (y + m)^2^ 增加的值== :
y + m 是預估的值 (y 是上一次的值)
$$
(y + m)^2 = y^2 + 2 \times y \times m + m^2
$$
$$
b = (y + m)^2 - y^2 = \color{red}{2 \times y \times m} + \color{red}{m^2}
$$
讓 2^shift^ 保持等於 m ，所以乘上 m 只用往左移動 shift 就好
```diff
- uint64_t b = y + m;
+ uint64_t b = y << (shift + 1) + m << shift; // 2my + m^2
```
然後將 x 減掉，相較於上次的 y^2^ ， (y+m)^2^ 所增加的值， if 的條件也變為只用判斷增加的值會不會超過 x 的範圍
```diff
- if (x >= b*b) {
+ if (x >= b) {
+ x -= b;
y += m;
}
```
由於要保持 2^shift^ 等於 m ，所以 shift 要 -1
```diff
+ shift -= 1;
```
以下是第二版完整的 code ，可以發現已經沒有使用乘法了，效率理論上會好上許多，但我們可以再簡化
>測試效率 [To do]
```cpp
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) >> 1;
m = 1ULL << shift;
while (m) {
uint64_t b = y << (shift + 1) + m << shift;
if (x >= b) {
x -= b;
y += m;
}
m >>= 1;
shift -= 1;
}
return y;
}
```
#### 善用 2 的冪簡化
在第二版每次計算新增的值時，都會使用 ```shift``` 對 y 跟 m 處理，我們是否有辦法不要使用 shift ?
以下針對 b = m^2^ + 2my 中的 ==m^2^ 、 y 以及 b== 分開討論
##### m^2^
仔細觀察第二版中 m^2^ 的變化，因為 m 每次都向右位移一個 bit 也就是檢查完 2^k^ 下一個會檢查 2^k-1^ ，所以 m^2^ 其實每次是變化兩個 bit，所以我們把 m 的定義直接改成 m^2^ ，每次變化 2 bit
```diff
- uint64_t b = y << (shift + 1) + m << shift;
+ uint64_t b = y + m
```
```diff
- m >>= 1;
-shift -= 1;
+ m >>= 2;
```
##### y
那改成 m^2^ 後 y 會有什麼變化呢 ?
首先我們先想想第二版中的 while 迴圈會跑幾次，若從 2^k^ 開始估計，迴圈會跑 k + 1 次
接著可以思考若 y += m 在第三版中要怎麼修改 :
以第一次 while 迴圈來說，若 m 是 2^2k^ ，實際上估計值要加上 2^k^ 但因為直接加上 m ，所以會多乘以 2^k^ ，那我們就讓倒數第 k 次迴圈時 y 的值是實際估計值乘上 2^k^。以下面為例還剩 k 次迴圈
$$
y = y + 2^{2k} = 0 + 2^{2k} = 2^k \times 2^k = 2^k \times 實際估計值
$$
第二次 while 迴圈時， m 變成 2^2k-2^ ，實際估計值要加上的是 2^k-1^ ，那我們先把 y (上一個實際估計值乘以 2^k^) 除以 2 (y >>= 1) ，y 就會是上一個實際估計值的 2^k-1^ 倍，那在加上 m 時 :
$$
y + m = 2^{k-1} \times (上一個實際估計值) + 2^{k-1} \times 2^{k-1}
$$
$$
y + m = 2^{k-1} \times ((上一個實際估計值) + 2^{k-1}))
$$
$$
y + m = 2^{k-1} \times (這次的實際估計值)
$$
所以 y 的定義變成了 ==2^倒數第k次迴圈^ x (實際估計值)==
那到最後一次是
$$
y = 2^{倒數第0次迴圈} \times (實際估計值) = 2^0 \times (實際估計值) = 實際估計值
$$
```diff
while (m) {
- uint64_t b = y << (shift + 1) + m << shift;
+ uint64_t b = y + m;
+ y >>= 1
if (x >= b) {
x -= b;
y += m;
}
- m >>= 1;
+ m >>= 2;
- shift -= 1;
}
```
##### b
那確認了 y 跟 m 的定義後，接著我們要來驗證 b 的定義是否跟第二版相同 :
假設
m' 是理論上估計值要加上的值
y' 是上一個理論上的估計值
b 是現在理論上的估計值與上一個理論上估計值的差值
所以 $$b = (y' + m')^2 - y'^2 = m'^2 + 2m'y'$$
根據上面所提
m = m'^2^
y = 2^倒數第k次迴圈^ x y'
所以 $$b = y + m = m'^2 + 2^{倒數第k次迴圈} \times y'$$
所以接下來只要證明
$$
\begin{cases}
b = m'^2 + 2m'y'\\
b = m'^2 + 2^{倒數第k次迴圈} \times y'
\end{cases}
$$
也就是 $$ 2m'y' = 2^{倒數第k次迴圈} \times y'$$
$$ 2m' = 2^{倒數第k次迴圈}$$
$$2m' = 2 \times 2^{(倒數第k次迴圈) - 1}$$
$$m' = 2^{(倒數第k次迴圈) - 1} = 2^{(倒數第k-1次迴圈)}$$
確實因為倒數第 k-1 次回圈就是檢查第 k-1 個 bit ，也就是 2^k-1^ ，所以 m' 的值就是 2^k-1^ 由此得證
以下是最終版的程式碼
```cpp
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
Sign in with Wallet
Connect another wallet