2025q1 Homework2 (quiz1+2)

contributed by <Charlie-Tsai1123>

第一周測驗題 - 測驗1

list_insert_before

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 指標的位子

p = &l->head

由於要從 linked list 中找到 before 的位子 p 要移動到指向下一個指標的位子，由 *p 先找到現在指向的指標，再取下一個指標，最後藉由 & 取指向下一個指標的位子

p = &(*p)->next

由下圖可知當找到 before 時（ *p = before），需要變動指標，可以直接改動 p 所指向的指標，就可以直接變動 linked list 了，最後新元素的 next 也要指向 before 所在位子

*p = item;
item->next = before;

解釋測試程式碼

合併排序

第一周測驗題 - 測驗2

解釋程式碼運作原理

程式在執行 binary search tree (BST) 的 remove ，以下為 BST 的架構，每個節點會有指向左子樹的指標跟指向右子樹的指標，而 size 是記憶體區塊的大小

typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;

find_free_tree 是從 BST 中找到要被釋放的記憶體區塊位子 (target)

block_t **find_free_tree(block_t **root, block_t *target);

find_predecessor_free_tree 則是找到 node 左子樹中的最大值

block_t *find_predecessor_free_tree(block_t **root, block_t *node);

在 remove_free_tree 中，把操作分成了三個 case :

• case 1 : 被 remove 的節點有左子樹跟右子樹
  • 左子樹沒有右子樹 （左子樹的 root 是最大的點）
  • 左子樹有右子樹 （左子樹有比左子樹 root 更大的點）

if ((*node_ptr)->l && (*node_ptr)->r)

• case 2 : 被 remove 的節點只有左子樹或右子樹

 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 兩張圖中藍色的節點就是要找的，而紅色是要移除的節點 ）

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 中

/* 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 中

為什麼還要再存一次左子樹最大節點明明已經有 pred_ptr

因為經過 remove_free_tree(&old_left, *pred_ptr) 後，可能會變成 NULL

/* 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 （藍色點）

case 3 : No children: remove the node.

補完 find_free_tree 及 find_predecessor_free_tree 並測試

效能評比

第一周測驗題 - 測驗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 的部份，也就是紅色部份

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;
}

quick_sort

實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼，用 begin 儲存切割的每個片段起始點，而對片段的處理分成以下幾種 :

1. 片段長度為 1 :
   加入到 result 內 (不需要排序了)

2. 片段長度不為 1 :
   分成三個片段， pivot (最左邊的節點)、比 pivot 還要小的片段、比 pivot 還要大的片段

研讀 〈A comparative study of linked list sorting algorithms〉

用 List API 實作排序

第二周測驗題 - 測驗1

解釋程式碼運作原理

與上週測驗不同的是這周採用遞迴的方式實作，而相同的點是一樣會用三個 linked list 來存(pivot 、較大、較小)，首先找到 pivot (最左邊的點)並移除

pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);

接著找到較大跟較小的節點分別存到 list_greater 跟 list_less 中

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

list_quicksort(&list_less);
list_quicksort(&list_greater);

到這步時理論上 head 會是 singular 的節點，節點都分布在 pivot、list_less、list_greater 當中，接下來將節點依序放入 head 中

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 前面，相對的順序就改變了

使用 list_move 加在 linked list 前面 (兩個 2 順序對調了) :

使用 list_move_tail 加在 linked list 後面 (兩個 2 順序不會對調) :

第二周測驗題 - 測驗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$$

$$...\mathrm{重}\mathrm{複}\mathrm{此}\mathrm{步}\mathrm{驟}$$

$$1.41421356<\sqrt{2}<1.41421357$$
所以

$\sqrt{2}$ 可以表示成

$$1\times \text{color}red{10}^1+4\times \text{color}red{10}^{-1}+1\times \text{color}red{10}^{-2}+4\times \text{color}red{10}^{-3}+2\times \text{color}red{10}^{-4}+1\times \text{color}red{10}^{-5}+3\times \text{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 \text{color}red{2}^{k/2}+a_2\times \text{color}red{2}^{k/2-1}+a_3\times \text{color}red{2}^{k/2-2}+\cdots +a_{k/2}\times \text{color}red{2}^1+a_{k/2+1}\times \text{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	22 = 4

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}{ccc}\mathbf{\text{1st}}& \mathbf{\text{2nd}}& \mathbf{\text{3rd}}\\ \underset{\text{這裡!}}{0}00& 1\underset{\text{這裡!}}{0}0& 10\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\ge b\cdot b(\text{符合})& \text{cancel}x\ge b\cdot b(\text{不符合})& x\ge b\cdot b(\text{符合})\\ y=4& y=4& y=5\end{array}$$

1 0 1
y = 4 + 1 = 5

while (m) {
    uint64_t b = y + m;
    if (x >= b*b) {
        y += m;
    }
    m >>= 1;
}

以下是第一版沒效率算法

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;
}

為甚麼說沒效率呢?

因為乘除法相較於 bitwise 的操作使用了更多的 CPU cycles

使用乘法公式優化

原本的 b 是估計值，用來估計 y 可能得值，那在優化的版本，我們將 b 的定義改為相較於上次的 y² 新的 (y + m)² 增加的值 :
y + m 是預估的值 (y 是上一次的值)

$$(y+m{)}^2=y^2+2\times y\times m+m^2$$

$$b=(y+m{)}^2-y^2=\text{color}red2\times y\times m+\text{color}red{m}^2$$

讓 2^shift 保持等於 m ，所以乘上 m 只用往左移動 shift 就好

- uint64_t b = y + m;
+ uint64_t b = y << (shift + 1) + m << shift; // 2my + m^2

然後將 x 減掉，相較於上次的 y² ， (y+m)² 所增加的值， if 的條件也變為只用判斷增加的值會不會超過 x 的範圍

- if (x >= b*b) {
+ if (x >= b) {
+   x -= b;
    y += m;
}

由於要保持 2^shift 等於 m ，所以 shift 要 -1

+ shift -= 1;

以下是第二版完整的 code ，可以發現已經沒有使用乘法了，效率理論上會好上許多，但我們可以再簡化

測試效率 [To do]

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² + 2my 中的 m² 、 y 以及 b 分開討論

m²

仔細觀察第二版中 m² 的變化，因為 m 每次都向右位移一個 bit 也就是檢查完 2^k 下一個會檢查 2^k-1 ，所以 m² 其實每次是變化兩個 bit，所以我們把 m 的定義直接改成 m² ，每次變化 2 bit

- uint64_t b = y << (shift + 1) + m << shift;
+ uint64_t b = y + m

- m >>= 1;
-shift -= 1;
+ m >>= 2;

y

那改成 m² 後 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 \mathrm{實}\mathrm{際}\mathrm{估}\mathrm{計}\mathrm{值}$$

第二次 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 (\mathrm{上}\mathrm{一}\mathrm{個}\mathrm{實}\mathrm{際}\mathrm{估}\mathrm{計}\mathrm{值})+2^{k-1}\times 2^{k-1}$$

$$y+m=2^{k-1}\times ((\mathrm{上}\mathrm{一}\mathrm{個}\mathrm{實}\mathrm{際}\mathrm{估}\mathrm{計}\mathrm{值})+2^{k-1}))$$

$$y+m=2^{k-1}\times (\mathrm{這}\mathrm{次}\mathrm{的}\mathrm{實}\mathrm{際}\mathrm{估}\mathrm{計}\mathrm{值})$$

所以 y 的定義變成了 2^{倒數第k次迴圈} x (實際估計值)
那到最後一次是

$$y=2^{\mathrm{倒}\mathrm{數}\mathrm{第}0\mathrm{次}\mathrm{迴}\mathrm{圈}}\times (\mathrm{實}\mathrm{際}\mathrm{估}\mathrm{計}\mathrm{值})=2^0\times (\mathrm{實}\mathrm{際}\mathrm{估}\mathrm{計}\mathrm{值})=\mathrm{實}\mathrm{際}\mathrm{估}\mathrm{計}\mathrm{值}$$

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^{\prime }+m^{\prime }{)}^2-y^{\prime 2}=m^{\prime 2}+2m^{\prime }{y}^{\prime }$$

根據上面所提
m = m'²
y = 2^{倒數第k次迴圈} x y'

所以

$$b=y+m=m^{\prime 2}+2^{\mathrm{倒}\mathrm{數}\mathrm{第}k\mathrm{次}\mathrm{迴}\mathrm{圈}}\times y^{\prime }$$
所以接下來只要證明

$$\{\begin{array}{l}b=m^{\prime 2}+2m^{\prime }{y}^{\prime }\\ b=m^{\prime 2}+2^{\mathrm{倒}\mathrm{數}\mathrm{第}k\mathrm{次}\mathrm{迴}\mathrm{圈}}\times y^{\prime }\end{array}$$
也就是

$$2m^{\prime }{y}^{\prime }=2^{\mathrm{倒}\mathrm{數}\mathrm{第}k\mathrm{次}\mathrm{迴}\mathrm{圈}}\times y^{\prime }$$

$$2m^{\prime }=2^{\mathrm{倒}\mathrm{數}\mathrm{第}k\mathrm{次}\mathrm{迴}\mathrm{圈}}$$

$$2m^{\prime }=2\times 2^{(\mathrm{倒}\mathrm{數}\mathrm{第}k\mathrm{次}\mathrm{迴}\mathrm{圈})-1}$$

$$m^{\prime }=2^{(\mathrm{倒}\mathrm{數}\mathrm{第}k\mathrm{次}\mathrm{迴}\mathrm{圈})-1}=2^{(\mathrm{倒}\mathrm{數}\mathrm{第}k-1\mathrm{次}\mathrm{迴}\mathrm{圈})}$$

確實因為倒數第 k-1 次回圈就是檢查第 k-1 個 bit ，也就是 2^k-1 ，所以 m' 的值就是 2^k-1 由此得證
以下是最終版的程式碼

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;
}