2025q1 Homework2 (quiz1+2)

contributed by < tyj513 >

Week 1 Q1

函式 list_insert_before 的目的是在鏈結串列中，將一個新節點 item 插入到 before 指定的節點前面。這個實作使用了 "pointer to pointer" 技巧，通過雙重指標來簡化操作。
完整的函式如下：

void list_insert_before(list_t *list, list_item_t *before, list_item_t *item) {
​   list_item_t **p;
​   for (p = &list->head; *p != before; p = &(*p)->next)
​       ;
​   *p = item;
​   item->next = before;
}

運作原理

此函式使用「指標指向指標」技術，透過 list_item_t **p 操作指標的位址，讓插入操作更靈活。步驟如下：

• 初始化：p 指向 list->head 的位址。
• 尋找插入點：迴圈遍歷直到 *p 等於 before。
• 插入新節點：將 *p 設為 item，更新鏈結。
• 連結後續：將 item->next 設為 before。

這個技巧的優點是統一了在開頭插入和在中間插入的邏輯，不需要特別處理鏈結串列為空或在開頭插入的情況。

Graphviz 視覺化

插入前（head -> 2 -> 3）：

插入 1 到 2 前：

實作合併排序 (Merge Sort)

/* 拆分鏈結串列為兩半 */
void list_split(list_item_t *head, list_item_t **front, list_item_t **back) {
​   list_item_t *fast;
​   list_item_t *slow;
​   
​   if (head == NULL || head->next == NULL) {
​       *front = head;
​       *back = NULL;
​       return;
​   }
​   
​   slow = head;
​   fast = head->next;
​   
​   while (fast != NULL) {
​       fast = fast->next;
​       if (fast != NULL) {
​           slow = slow->next;
​           fast = fast->next;
​       }
​   }
​   
​   *front = head;
​   *back = slow->next;
​   slow->next = NULL;
}

/* 合併兩個已排序的鏈結串列 */
list_item_t *list_merge(list_item_t *a, list_item_t *b) {
​   list_item_t dummy = {0, NULL};
​   list_item_t *tail = &dummy;
​   
​   while (a && b) {
​       if (a->value <= b->value) {
​           tail->next = a;
​           a = a->next;
​       } else {
​           tail->next = b;
​           b = b->next;
​       }
​       tail = tail->next;
​   }
​   
​   tail->next = (a) ? a : b;
​   return dummy.next;
}

/* 合併排序主函式 */
void list_merge_sort(list_item_t **headRef) {
​   list_item_t *head = *headRef;
​   list_item_t *a, *b;
​   
​   if (head == NULL || head->next == NULL)
​       return;
​   
​   list_split(head, &a, &b);
​   
​   list_merge_sort(&a);
​   list_merge_sort(&b);
​   
​   *headRef = list_merge(a, b);
}

/* 整合到list操作中 */
void list_sort(list_t *list) {
​   if (!list || !list->head)
​       return;
​   
​   list_merge_sort(&list->head);
}

Week 1 Q2

測驗二要求實作 remove_free_tree 函式，從二元搜尋樹（BST）中移除一個自由記憶體區塊。結構定義如下：

typedef struct block {
    size_t size;      // 區塊大小
    struct block *l;  // 左子節點
    struct block *r;  // 右子節點
} block_t;

未完成程式碼處理具有兩個子節點的情況：

if ((*node_ptr)->l && (*node_ptr)->r) {
    block_t **pred_ptr = &(*node_ptr)->l;
    while ((*pred_ptr)->r)
        pred_ptr = &(*pred_ptr)->r;
    
}

運作原理

二元搜尋樹節點刪除步驟如下：

1. 先找到要刪除的節點在樹中的位置
2. 根據該節點的子節點數量，有不同的處理策略：
   • 無子節點：直接移除
   • 有一個子節點：用子節點替換當前節點
   • 有兩個子節點：找到該節點的中序前驅或後繼替換它

在這個實作中，我們使用中序前驅替換有兩個子節點的目標節點。
中序前驅是指在中序遍歷中，排在目標節點之前的節點，即左子樹中的最大節點。

Graphviz 視覺化

移除前（根節點 50）：

移除 50 後（由 40 替換）：

延伸問題：完整實作

完整的移除函式：

block_t** find_free_tree(block_t **root, block_t *target) {
    block_t **p = root;
    while (*p && *p != target) {
        p = (target->size < (*p)->size) ? &(*p)->l : &(*p)->r;
    }
    return p;
}

void remove_free_tree(block_t **root, block_t *target) {
    block_t **node_ptr = find_free_tree(root, target);
    if ((*node_ptr)->l && (*node_ptr)->r) {
        block_t **pred_ptr = &(*node_ptr)->l;
        while ((*pred_ptr)->r)
            pred_ptr = &(*pred_ptr)->r;
        block_t *pred = *pred_ptr;
        block_t *old_left = (*node_ptr)->l;
        block_t *old_right = (*node_ptr)->r;
        if (pred != old_left) {
            remove_free_tree(&old_left, pred);
        }
        *node_ptr = pred;
        pred->l = (pred == old_left) ? NULL : old_left;
        pred->r = old_right;
    } else {
        *node_ptr = (*node_ptr)->l ? (*node_ptr)->l : (*node_ptr)->r;
    }
    target->l = target->r = NULL;
}

時間複雜度：O(log n)，由 BST 高度決定。

Week 1 Q3

測驗 3 要求我們完成一個非遞迴版本的快速排序法，運用堆疊模擬遞迴呼叫。經過分析，解答為：

CCCC: p->next
DDDD: list_tail(&left)
EEEE: list_tail(&right)

對於 Linux 核心風格 List API 的改寫：

GGGG: head->prev=prev
HHHH: list_entry(pivot,node_t,list)->value
IIII: list_entry(n,node_t,list)->value
JJJJ: pivot
KKKK: right

運作原理解釋

非遞迴快速排序的基本思想
這個實作使用堆疊來模擬遞迴呼叫。傳統的快速排序法是遞迴實作的，但可能會導致深度遞迴時的堆疊溢位問題。非遞迴版本透過明確管理自己的堆疊來避免這個問題。
主要步驟：

• 初始化一個堆疊儲存待處理的子序列範圍
• 迴圈處理堆疊，每次從堆疊取出一個範圍
• 如果範圍內有多個元素，進行快速排序的分割操作
• 將分割後的子範圍再次壓入堆疊
• 重複直到堆疊為空
  

這個非遞迴快速排序的關鍵在於如何管理待處理的子序列。程式使用 begin[] 陣列作為堆疊，儲存各個子序列的開始節點。然後使用迴圈不斷從堆疊中取出子序列進行處理，直到堆疊為空。

在每次迴圈中：
1.檢查當前子序列的開始節點( L )和結束節點( R )

2.如果 L≠R，表示子序列有多個元素，需要進行分割：

• 選擇最左邊的元素作為 pivot
• 將剩餘元素分成兩部分：小於等於 pivot 的放入 left，大於的放入 right
• 將 left, pivot, right 三個子序列放回堆疊中

3.如果 L=R，表示子序列僅有一個元素，直接加入結果列表

Linux 核心風格的 List API 採用入侵式鏈結串列設計。入侵式鏈結串列將串列節點結構嵌入到資料結構中，而不是將資料包在節點結構中。這種設計有以下特點：

• 更有效率地使用記憶體，避免過多的記憶體配置與釋放操作
• 可以從鏈結節點（struct list_head）反向找到包含該節點的結構體
• 一個結構體可以同時屬於多個不同的鏈結串列

在這個實作中，list_entry 巨集用於從 struct list_head 指標獲取包含它的 node_t 結構體指標。

延伸思考：雙向鏈結串列排序演算法的比較研究

根據《A comparative study of linked list sorting algorithms》論文，針對雙向鏈結串列的排序演算法有以下考量：
雙向鏈結串列排序的主要挑戰與考量

記憶體存取模式：雙向鏈結串列節點在記憶體中通常不連續，導致較差的快取效能
連結操作成本：排序過程需要大量的指標重新連結操作
隨機存取限制：鏈結串列無法高效地隨機存取元素，影響排序演算法的效能

主要排序演算法在鏈結串列上的表現

• 合併排序 (Merge Sort)：

  優點：合併操作非常適合鏈結串列，只需要重定向指標而不需要額外空間
  缺點：遞迴深度可能較大

• 快速排序 (Quick Sort)：

  優點：分割操作可以透過指標調整高效實現
  缺點：隨機存取受限，樞紐點選擇較困難

• 插入排序 (Insertion Sort)：

  優點：對小規模資料集或接近有序的資料效率高
  缺點：對大型隨機資料效率低

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "list.h"

typedef struct __node {
    long value;
    struct list_head list;
} node_t;
 
static void list_split(struct list_head *head, 
                      struct list_head **front, 
                      struct list_head **back)
{
    struct list_head *fast = head->next;
    struct list_head *slow = head;
    
    /* 使用快慢指標找到中點 */
    while (fast != head) {
        fast = fast->next;
        if (fast != head) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    
    *front = head;
    *back = slow->next; 
    slow->next->prev = slow;
    slow->next = head;
    head->prev = slow;
}
 
static struct list_head *list_merge(struct list_head *a, 
                                  struct list_head *b,
                                  bool (*cmp)(struct list_head *, struct list_head *))
{
    struct list_head dummy;
    struct list_head *tail = &dummy;
     
    INIT_LIST_HEAD(&dummy);
    
    while (!list_empty(a) && !list_empty(b)) {
        struct list_head *item;
        
        if (cmp(a->next, b->next)) {
            item = a->next;
            list_del(item);
        } else {
            item = b->next;
            list_del(item);
        }
        
        list_add_tail(item, &dummy);
    }
     
    if (!list_empty(a))
        list_splice_tail(a, &dummy);
    else
        list_splice_tail(b, &dummy);
    
    return dummy.next;
}

static bool list_value_less(struct list_head *a, struct list_head *b)
{
    return list_entry(a, node_t, list)->value < 
           list_entry(b, node_t, list)->value;
}

void merge_sort(struct list_head *head)
{
    struct list_head *a = NULL, *b = NULL;
    
    if (list_empty(head) || list_is_singular(head))
        return;
    
    list_split(head, &a, &b);
    
    merge_sort(a);
    merge_sort(b);
    
    head->next = list_merge(a, b, list_value_less);
    head->next->prev = head;
}

void list_construct(struct list_head *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->value = n;
    list_add_tail(&node->list, list);
}

/* 測試用串列釋放函式 */
void list_free(struct list_head *head)
{
    node_t *entry, *safe;
    list_for_each_entry_safe(entry, safe, head, list) {
        list_del(&entry->list);
        free(entry);
    }
}

static bool list_is_ordered(struct list_head *head)
{
    node_t *prev = NULL, *current;
    
    list_for_each_entry(current, head, list) {
        if (prev && current->value < prev->value)
            return false;
        prev = current;
    }
    
    return true;
}

int main(void)
{
    struct list_head test_list;
    int test_values[] = {5, 3, 8, 1, 7, 2, 6, 4};
    int test_size = sizeof(test_values) / sizeof(test_values[0]);
    
    INIT_LIST_HEAD(&test_list);
    
    for (int i = 0; i < test_size; i++) {
        list_construct(&test_list, test_values[i]);
    }
    
    merge_sort(&test_list);
    
    assert(list_is_ordered(&test_list));
    
    printf("排序結果: ");
    node_t *entry;
    list_for_each_entry(entry, &test_list, list) {
        printf("%ld ", entry->value);
    }
    printf("\n");
    
    list_free(&test_list);
    
    return 0;
}

Week 2 Q1

在測驗 1 中，我們需要完成 Linux 核心風格的快速排序函式 list_quicksort，該函式使用 Linux 核心的雙向鏈結串列 API 操作。函式骨架已經提供，需要填入適當的巨集或內聯函式

{
    struct list_head list_less, list_greater;
    struct listitem *pivot;
    struct listitem *item = NULL, *is = NULL;

    // 如果串列為空或只有一個元素，不需排序
    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

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

    // 遍歷串列，根據大小將元素分配到兩個子串列
    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_quicksort(&list_less);
    list_quicksort(&list_greater);

    // 重新組合排序完的串列
    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}

運作原理解釋

這個快速排序演算法的實作基於 Linux 核心的雙向鏈結串列 API，主要步驟如下：

1.基本檢查：如果串列為空或只有一個元素，則無需排序
2.選擇樞紐：使用 list_first_entry 取得串列的第一個元素作為樞紐(pivot)
3.分割串列：

• 移除樞紐節點，使用 list_del 將它從原串列中斷開
• 遍歷原串列中的其餘元素，將小於樞紐的元素放入 list_less，大於等於樞紐的元素放入 list_greater
• 使用 list_move_tail 操作確保元素在子串列中保持原來的相對順序

4.遞迴排序：對 list_less 和 list_greater 遞迴應用快速排序
5.重組串列：

• 先用 list_add 將樞紐節點加入目標串列的開頭
• 用 list_splice 將 list_less（所有小於樞紐的元素）添加到目標串列的開頭
• 用 list_splice_tail 將 list_greater（所有大於等於樞紐的元素）添加到目標串列的末尾

digraph G {
    rankdir=TD;
    node [shape=box];

    subgraph cluster_0 {
        label="Using list_move_tail (Stable Sort)";
        orig1 [label="Original List: A1=5, B1=5, C1=5"]; 
        step11 [label="Process A1"];
        less11 [label="list_less: A1"];
        step12 [label="Process B1"];
        less12 [label="list_less: A1, B1"];
        step13 [label="Process C1"];
        less13 [label="list_less: A1, B1, C1"];
        result1 [label="Result: Maintains original order A1, B1, C1"];

        orig1 -> step11 -> less11;
        step11 -> step12 -> less12;
        step12 -> step13 -> less13;
        step13 -> result1;
    }

    subgraph cluster_1 {
        label="Using list_move (Unstable Sort)";
        orig2 [label="Original List: A2=5, B2=5, C2=5"]; 
        step21 [label="Process A2"];
        less21 [label="list_less: A2"];
        step22 [label="Process B2"];
        less22 [label="list_less: B2, A2"];
        step23 [label="Process C2"];
        less23 [label="list_less: C2, B2, A2"];
        result2 [label="Result: Reversed order C2, B2, A2"];

        orig2 -> step21 -> less21;
        step21 -> step22 -> less22;
        step22 -> step23 -> less23;
        step23 -> result2;
    }
}

隨機洗牌函式的分析與改進

原始random_shuffle_array 函式的問題

原始的 random_shuffle_array 函式存在兩個主要問題：

1. 洗牌有偏見（Biased Shuffling）

• 問題描述：
  在每一輪迭代中，隨機索引 j 是透過 get_unsigned16() % (i + 1) 計算的，其中 get_unsigned16() 返回 0 到 65535 的隨機數。當 (i + 1) 無法整除 65536 時，取模操作導致 j 的分佈不均勻。
• 範例分析：
  當 i = 2 時，(i + 1) = 3，get_unsigned16() % 3 將 0 到 65535 映射到 0、1、2：
  • j = 0：出現 21846 次（0, 3, 6, …, 65535）。
  • j = 1 和 j = 2：各出現 21845 次。
  • 機率：
    • P(j=0) = 21846/65536 ≈ 0.3334
    • P(j=1) = 21845/65536 ≈ 0.3333
    • P(j=2) = 21845/65536 ≈ 0.3333
  • 結論：j = 0 的機率略高，導致洗牌結果偏向某些特定排列。

2. 更新陣列的方式不正確

• 問題描述：
  程式碼使用 operations[i] = operations[j]; operations[j] = i; 更新陣列，這不是標準的交換操作。它將 operations[j] 的值複製到 operations[i]，然後將索引 i 賦值給 operations[j]，而不是交換兩者的值。這會破壞陣列元素的完整性。
• 錯誤範例：
  假設陣列初始為 [10, 20, 30]，長度 len = 3：
  • i = 0:
    • j = get_unsigned16() % 1 = 0
    • operations[0] = operations[0] = 10（無變化）
    • operations[0] = i = 0
    • 結果：[0, 20, 30]
  • i = 1:
    • 假設 get_unsigned16() = 3，j = 3 % 2 = 1
    • operations[1] = operations[1] = 20（無變化）
    • operations[1] = i = 1
    • 結果：[0, 1, 30]
  • i = 2:
    • 假設 get_unsigned16() = 4，j = 4 % 3 = 1
    • operations[2] = operations[1] = 1
    • operations[1] = i = 2
    • 結果：[0, 2, 1]
• 問題總結：
  最終結果 [0, 2, 1] 不是原始陣列 [10, 20, 30] 的排列，原始元素被索引值替換，且由於 j 的偏見，某些排列出現機率更高。

---

改進後的函式

改進後的函式採用 Fisher-Yates 洗牌演算法，程式碼如下：

/* Fisher-Yates 洗牌算法的改進版本 */
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        uint16_t range = len - i;
        uint16_t j = i + (get_unsigned16() % range);   
        uint16_t temp = operations[i];
        operations[i] = operations[j];
        operations[j] = temp;
    }
}

改進之處

1. 使用標準 Fisher-Yates 演算法

• 原理：
  從索引 i 開始，隨機選擇一個位置 j（範圍從 i 到 len - 1），然後交換 operations[i] 和 operations[j]。
• 實現細節：
  • range = len - i 表示剩餘未處理的元素數量。
  • j = i + (get_unsigned16() % range) 從當前位置到末尾均勻隨機選取。
• 優勢：
  每個元素有均等機會被交換到當前位置，所有排列的機率幾乎相等。

2. 正確的交換操作

• 方法：
  使用臨時變數 temp 實現 operations[i] 和 operations[j] 的交換。
• 效果：
  保留原始陣列的所有元素，僅改變它們的位置。

3. 減少偏見

• 分析：
  雖然 get_unsigned16() % range 在 range 不整除 65536 時仍有微小偏見，但由於 range 通常遠小於 65536，且 Fisher-Yates 的結構分散了這種影響，偏見幾乎可忽略。

改進後範例

假設陣列初始為 [10, 20, 30]，長度 len = 3：

• i = 0:
  • range = 3，假設 get_unsigned16() = 4，j = 0 + (4 % 3) = 1
  • 交換 operations[0] 和 operations[1]：[20, 10, 30]
• i = 1:
  • range = 2，假設 get_unsigned16() = 3，j = 1 + (3 % 2) = 2
  • 交換 operations[1] 和 operations[2]：[20, 30, 10]
• i = 2:
  • range = 1，j = 2 + (get_unsigned16() % 1) = 2
  • 交換 operations[2] 和 operations[2]（無變化）：[20, 30, 10]
• 結果：
  [20, 30, 10] 是 [10, 20, 30] 的一個有效排列，每個排列的機率近似為 1/6。

為何使用 list_move 取代 list_move_tail 時無法滿足 stable sort？

list_move_tail 會將元素移到目標串列的尾部，保持了元素的相對順序
若改用 list_move，元素會被移到目標串列的頭部，導致原本的相對順序被反轉
在排序中，如果兩個元素的比較鍵值相同，穩定排序要求它們的相對順序保持不變

Week 2 Q2

在測驗 2 中，我們需要分析並補完整數開平方根的實作。首先補完 clz2 函式中的空缺部分：

static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {0, 1, 0, 2};

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == 3)
        return upper ? magic[upper] : 4 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

對於 sqrti 函式，需要填入的表達式為：

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

GGGG: 14
HHHH: 0
IIII: 2
JJJJ: 3
KKKK: 4
LLLL: 1
MMMM: ~1
NNNN: 1
PPPP: 2

運作原理解釋
整個實作包含兩個核心功能：計算前導零和整數開平方根。

1. clz2 函式：計算前導零
   這個函式使用分治法遞迴計算 32 位元整數中的前導零數量：

基本情況：如果輸入為 0 且 c 為 0，則返回 32（表示全為零）
分割：將輸入 x 分為高位（upper）和低位（lower）部分
遞迴：

如果 upper 不為 0，則遞迴處理 upper 部分
如果 upper 為 0，則將 (16 >> c) 加到結果中，並遞迴處理 lower 部分

終止條件：當 c 達到 3（分割到最小單位）時停止遞迴

mask 和 magic 陣列用於在遞迴過程中處理位元操作和結果轉換。
2. sqrti 函式：計算整數開平方根
這個實作基於牛頓方法的變體，使用二進位數位一個一個尋找：

初始化：

找到輸入 x 的最高設置位，並將其向下取整到偶數位（shift = (total_bits - 1 - clz64(x)) & ~1）
設置 m = 2^shift，作為第一個測試位
初始化結果 y = 0

迭代：

計算 b = y + m
將 y 右移 1 位
如果 x ≥ b，則 x -= b 且 y += m
將 m 右移 2 位（測試下一個二進位位置）
重複直到 m 變為 0

結果：返回 y，即 x 的整數平方根

Week 2 Q3