2025q1 Homework2 (quiz1+2)

contributed by <davidshiao55>

2025q1

測驗 `1`

實作 list_insert_before 函式，其中測試程式碼，測試插入鏈結串列的頭和尾且利用串列大小和出入數列的排列來檢查程式碼執行結果。

my_assert(list_size(&l) == N, "Final list size should be N");
size_t k = N - 1;
list_item_t *cur = l.head;
while (cur) {
    my_assert(cur->value == k, "Unexpected list item value");
    k--;
    cur = cur->next;
}

實作同你所不知道的 C 語言: linked list 和非連續記憶體中 remove_list_node 的做法，使用間接指標避免考慮特例情況：before 節點為 head。

當使用間接指標 p 指向 head 時可不用考慮是否需要更動 head，且不用紀錄一個 prev 指標執行插入並維持串列結構，在迴圈中每次迭代只需將 p 指向節點的 next，直接更動當前節點的 next 指標即可。

static inline void list_insert_before (list_t *l, list_item *before, list_item *item)
{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    item->next = before;
}

原始實作：當插入節點為第一個節點是會有例外情況產生，需要改變 head 指標

間接指標實作：直接更改 indirect 避免掉了例外情況

原始實作：當插入節點到串列中時需維持一個 prev 指標來插入節點維持串列結構。

間接指標實作：透過間接指標直接指向前一個節點的 next 直接更動 next 指標。

測驗 `2`

此程式依照 Binary Search Tree 的刪除節點方式，當刪除一個節點時會產生幾種不同情況：

刪除節點為 leaf：直接刪除節點即可。

對應程式碼：

else {
    /* No children: remove the node. */
    *node_ptr = NULL;
}

刪除節點有一個非空子樹：刪除節點並讓其子樹取代原本位置。

對應程式碼：

/* If the target node has one child, simply splice it out. */
else if ((*node_ptr)->l || (*node_ptr)->r) {
    block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
    *node_ptr = child;
}

刪除節點有兩非空子樹：尋找刪除節點 inorder predecessor 取代刪除節點。當中又分兩種情況，當 predecessor 是刪除節點的左子節點，或是在左子樹更深層。

/* Find the in-order predecessor:
 * This is the rightmost node in the left subtree.
 */
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

(1) 當 predecessor 是刪除節點的左子節點：用 predecessor 取代刪除節點後重新接上刪除節點的右子樹。

對應程式碼：

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

(2)當 predecessor 在左子樹更深層中：將 predecessor 移除原本位置，再取代刪除節點，並接上刪除節點的左右子樹。

對應程式碼：

else {
    /* 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);
}

測驗 `3`

使用 linux list api 實作迭代快速排序法。

測試程式碼透過 shuffle 和 list_is_ordered 來檢測排序演算法的正確性。shuffle 演算法類似 lab0 中的 Fisher-Yates shuffle。

/* shuffle array, only work if n < RAND_MAX */
void shuffle(int *array, size_t n)
{
    if (n <= 0)
        return;

    for (size_t i = 0; i < n - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
        int t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

由於 linux kernel linked list 採用雙向環狀鏈結串列，在實作排序時不好維護，實作中先斷開環狀結構且只維護單向的鏈結串列，所以在排序後需重新建構環狀雙向鏈結串列。

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

有別於 Optimized Quicksort 的實作，只維護 begin 一堆疊，使用 list_tail 在每次迴圈中重找 end，犧牲時間來換取空間的策略。

-     node_t *begin[max_level], *end[max_level];
+     struct list_head *begin[max_level];
-     node_t *L = begin[i], *R = end[i];
+     struct list_head *L = begin[i], *R = list_tail(begin[i]);

其餘操作同 Optimized Quicksort:

將 L 和 R 指向當前堆疊上的兩端
當 L 和 R 未相遇前，設最左邊元素為 pivot 使用指標 p 走訪當前堆疊上的串列將小於 pivot 的節點至於 left 串列，大於的至於 right 串列
將 left，pivot，right 推上堆疊。

演算法分析：遞迴的快速排序透過分割再遞迴操作左右兩個分割來實作，在迭代快速排序中使用區域變數 begin 堆疊陣列來模擬遞迴呼叫。這個實作在時間複雜度仍跟遞迴呼叫一樣，但可以避免掉函式呼叫時間，空間複雜度則因為要確保在 Worst Case 也正確執行，必須讓堆疊空間寫死在 $O (n)$ 失去了遞迴呼叫中的平均 $O (l o g n)$ 。

2025q2

測驗 `1`

linux list api 遞迴快速排序法實作，將 head 的 list_first_entry 設為 pivot ，與第一次測驗中實作方法相同將大於 pivot 的插入一個串列，小於 pivot 的插入另一個串列，最後再用 list_add，list_splice 和 list_splice_tail 重構串列。

list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting：list_move 會將插入元素加到串列的頭，但我們走訪原串列時是由左而右，若遇到相同元素則會造成 unstable。

改進 random_shuffle_array：使用 Fisher Yate 實作

static inline void random_init_array(uint16_t *operation, uint16_t len)
{
    // Step 1: Fill arr in ascending order
    for (uint16_t i = 0; i < len; i++)
        operation[i] = i;

    // Step 2: Fisher–Yates shuffle
    for (uint16_t i = 0; i < len; i++) {
        // pick a random index from [0..i]
        uint16_t j = get_unsigned16() % (i + 1);

        // swap arr[i] and arr[j]
        uint16_t tmp = operation[i];
        operation[i] = arr[j];
        operation[j] = tmp;
    }
}

測驗 `2`

clz2 藉由 binary search 的方式尋找 leading zero。
mask：每次 shift 的量會是前一次的 $+ 2^{4 - c}$ ，c 為 0 的時候不 shift。
0 -> 8 -> 12 -> 14
magic：剩兩 bit 的時候的最後結果
00 -> 2 + 2
01 -> 2 + 1
10 -> 2 + 0
11 -> 2 + 0

sqrti 先指出小於 x 的最小的 power of 4，利用 clz64 找出 MSB 的位元再對 ~1 做 mask 清除 LSB。

2025q1 Homework2 (quiz1+2)

2025q1

測驗 1

測驗 2

測驗 3

2025q2

測驗 1

測驗 2

Read more

2025q1 Homework1 (lab0)

2025q1 Homework1 (ideas)

測驗 `1`

測驗 `2`

測驗 `3`

測驗 `1`

測驗 `2`