2025q1 Homework2 (quiz1+2)

contributed by < tsaiiuo >

quiz1

測驗1

在這題所提出的資料結構如下，就是是一個標準的單向鏈結串列。

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

透過 Graphviz 圖呈現大致如下。

這測驗一中主要是要實做list_insert_before這個函式，函式的敘述如下：

實做可以透過指標的指標與迴圈去找到放置 before 的指標，並且將此指標指向的指標改成要插入的元素，最後再將插入的元素的 next 指向 before 即可完成list_insert_before的功能。

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

AAAA = &l->head (初始化第一個)
BBBB = before (透過迴圈尋找存放 before 的指標)
CCCC = &(*p)->next (指標的指標更新)
DDDD = item->next (將新的元素的 next 指向 before)

測驗1 延伸問題

程式碼解釋

首先定義了兩個巨集
my_assert用來判斷回傳 error ，在程式碼中就用來盼對是否 list size 在不同操作過後是否正確， list value 是否在進行完list_insert_before後是否正確，若不正確的話則回傳參數 message 告訴我們哪裡出錯了。
my_run_test用來執行測試程式碼，如果有收到回傳的 message 則終止回傳。

函式的部分
list_insert_before上述介紹過。
list_reset用來初始化整個 list_item 分別為1~1000，並且將 next 指向 NULL。
list_size獲取 list 的長度。
test_list測試程式碼本身，透過判斷執行list_insert_before後 list value 和 list size 在操作後是否正確，來確認list_insert_before的功能是否正確。

程式運作脈絡：
呼叫巨集test_suite執行test_list，在test_list中執行一系列圍繞著list_insert_before的操作，並透過巨集my_assert判斷是否操作符合預期，若有問題則回傳錯誤消息; 沒有的話回傳 NULL 回傳的結果會給 result ，若 result 不等價於 NULL 代表有錯誤，則輸出錯誤資訊，反之則輸出測試通過。

在現有的程式碼基礎上，撰寫合併排序操作

Commit 50e111c

透過遞迴呼叫的方式撰寫合併排序，並且配合 list_insert_before 等先前定義好的函式，實做測試函式 test_merge_sort 去驗證正確性。

測驗2

這題所提出用來操作的資料結構為 block_t 如下：

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

就是一個實現二元搜尋樹的類資料結構。
要尋求的答案EEEE、FFFF其實也不用懂remove_free_tree的整個操作就可得出先觀察敘述

/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
    /* Find the in-order predecessor:
    * This is the rightmost node in the left subtree.
    */
    block_t **pred_ptr = &(*node_ptr)->l;
    while (EEEE)
        pred_ptr = FFFF;

....

可以知道這段程式碼的用意是要找到左子樹中最大的點(也就是左子樹中最右邊的點)，因此EEEE = (*pred_ptr) -> r 、 FFFF = &(*pred_ptr) -> r，這樣這個迴圈才可以不斷的向右遍歷找到答案。

測驗2延伸問題

程式碼解釋

首先定義了兩個函式
find_free_tree 應該是個搜尋函式，會回傳指向 target 的指標，在remove_free_tree中有使用到回傳值被保存在 node_ptr。
find_predecessor_free_tree應該是個搜尋函式，用來尋找參數 node 的 in-order predecessor。

主函式
remove_free_tree負責移除二元搜尋樹的指定節點，並且要確保移除後樹還保持著二元搜尋樹的定義。

程式運作脈絡：
先透過find_free_tree取得要指向預計刪除節點的子樹主要分為三種狀況

狀況1：左右子樹皆有
這種情況會先透過find_predecessor_free_tree找到左子樹的 in-order predecessor 而find_predecessor_free_tree的結果也有可能為 node_ptr 的左子樹本身或 node_ptr 的左子樹有右子樹兩種情況：

若為 node_ptr 的左子樹本身，則先紀錄原先的 node_ptr 的右子樹 在這裡透過 old_right 儲存（因為接下來會透過指標的指標直接更新 node_ptr 指向的指標），接著更新 node_ptr 指向的指標的元素為 左子樹的 in-order predecessor(這裡在程式碼內是*pred_ptr)，最後再將更新完後的 node_ptr 指向的元素的右子樹指向 old_right。

若為不是 node_ptr 的左子樹本身，則原先 node_ptr 的左右子樹皆需先記錄起來，理由跟上面一樣，只是因為現在要拿來取代刪除節點不是 node_ptr 的左子樹本身，因此左子樹也須記載(會透過指標的指標直接更新 node_ptr 指向的指標的元素)為新節點做後續的左右子樹更新。

狀況2：左右子樹只擁有其中一個
直接將 node_ptr 指向存在的那一個的 root 的指標更新即可。
狀況3：左右子樹皆沒有
直接將 node_ptr 指向的指標更新為 NULL 。

並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

Commit cadf2b9

先將上述完整的 remove_free_tree 函式實做出來。

Commit b42eac7

實做 find_predecessor_free_tree 和 find_free_tree ， find_predecessor_free_tree 利用二元搜尋樹的特性利用迴圈配合判斷大小即可找到目標元素， find_free_tree 沒有左子樹的情況回傳 NULL ; 反之，利用找到第一個左子樹並且配合迴圈找到最右邊的子樹就是答案。

Commit b805364

撰寫相對應測試，主要利用二元搜尋樹的特性用 inorder_traversal 去拜訪的話會得到由小到大的元素，因為 inorder_traversal 的拜訪順序是 Left->Root->Right 。

測驗3

此題用來操作的資料結構 node_t 如下：

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

也是具有 Linux 核心風格的 List API 的雙向鏈結串列

先看GGGG的答案為何，他在rebuild_list_link的函式中出現，就必須要了解這個函式的用途：

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;
    /* GGGG */;
}

可以看到這個函式的作用是在執行 quick_sort 完後要對 prev 重新鏈結，因 quick_sort 只利用 next 指標進行排序的操作。這邊迴圈的用意就是在根據節點的 next 跟節點進行 prev 的鏈結，並取在最後的時候需將最後一個節點的 next 鏈結到 head ，也須將 head 的 prev 鏈結到最後一個節點，因此GGGG答案是 head -> prev = prev。

接下來HHHH ->KKKK就需要了解 quick_sort函式的實作了，先看向程式碼，一開始先將雙向鏈結串列的結尾 head -> prev -> next = NULL 防止有循環無法中止遍歷鏈結串列， L 和 R 透過 begin[i] 儲存的起點配合list_tal取得結尾去宣告，並且將第一個元素宣告為 p 也就是 pivot 得簡寫，並且透過迴圈將大與 pivot value 的元素儲存在 right 這個鏈結串列上; 反之儲存在 left 這格鏈結串列上，因此可以先得知HHHH答案為 pivot -> value ; IIII答案為 n -> value 。之後根據 quick_sort 的描述可以看到將 begin[i] 更新為 left ， JJJJ 答案為pivot ， KKKK 答案為right，再執行 i +=2 進行後續的迴圈，透過這個操作可以優先對大於 pivot 的鏈結串列進行分割。在分割到 L = R 時代表分割出來只有一個元素，然後由於我們是優先對大於 pivot 的鏈結串列進行分割，因此這邊的第一個元素會是最大的元素將他與 result 鏈結串列進行連結並且更新 result 為該元素，同時執行 i- - 這樣可以讓迴圈下一次存取相較於本身的次高鏈結串列，若需分割則繼續分割，不需則執行 L = R 一樣的 result 更新，最後則可得到升序順利的鏈結串列，但此時這個鏈結串列只有維護 next 並沒有維護 prev 因此需執行 rebuild_list_link 去重新連結正確的 prev。

測驗3延伸問題

程式碼解釋

函式：
list_tail 透過迴圈去尋找鏈結串列的尾巴。
list_length 透過 list_for_each 這個 API 去計算鏈結串列的長度。
list_construct 創建一個 value 為 n 的 node_t 並透過 list_add API 加進鏈結串列裡。
list_free 透過 list_for_each_entry_safe 這個 API 去釋放鏈結串列的記憶體。
list_is_ordered 透過 list_for_each_entry API 去檢測鏈結串列式經過排序的。
shuffle 實現 Fisher-Yates Shuffle 打亂陣列的元素。
quick_sort 上面已有詳細解釋。
rebuild_list_link 上面已有詳細解釋。

程式運作脈絡：
先使用 malloc 分配陣列的記憶體，再透過迴圈賦予值，之後執行 shuffle 打亂陣列的排序，接著配合迴圈去創建鏈結串列，創建完成之後執行 quick_sort 函式，並執行 list_is_ordered 去檢測是否排序正確，若正確的話則 list_free ; 反之 assert 會中斷程式碼。

quiz2

測驗1

AAAA -> FFFF 是圍繞在函式 list_quicksort 裡面，因此須先了解該如何使用 quick_sort 並且使用 Linux 核心 API 來回答問題，程式碼本身先定義了 list_less 和 list_greater 分別保存小於 pivot 和大於 pivot 的元素， pivot 是鏈結串列的第一個點，因此 AAAA 答案是 list_first_entry ，接著需將 pivot 從原先的鏈結串列中移除，在這裡 BBBB 答案是 list_del，再來透過 list_for_each_entry_safe 遍歷鏈結串列並對每個元素對 pivot 的 value 比大小，將結果透過 list_move_tail 與 list_less 和 list_greater 分別鏈結起來，因此 CCCC 答案為 list_move_tail ，接著透過遞迴呼叫 list_quicksort 對 list_less 和 list_greater 做處理，最後分別透過 list_add list_splice 將 pivot 和 list_less 鏈結回 head ，最後再將 list_greater 透過 list_splice_tail 鏈結回尾巴，因此 DDDD 和 EEEE 答案分別為 list_add 、 list_splice ，FFFF 答案為 list_splice_tail ，這樣就有升序排序的結果。

測驗1延伸問題

程式碼解釋

函式：
cmpint 用來比較兩個無號16位元的整數。
getnum 透過三個靜態變數(只會在第一次呼叫初始化一次)進行不同的乘法和算餘數，再將三個變數進行 XOR 運算，是用來生成隨機無號8位元數的。
get_unsigned16 16位元就是兩個 byte 因此透過兩次 getnum 函式配合 |= 運算可以生成一個隨機的無號16位元整數。
random_shuffle_array 是一個 shuffle 函數但不是用標準 Fisher–Yates 演算法實現。
list_quicksort 上述已有詳細描述。

程式運作脈絡：
宣告陣列，透過迴圈賦值，並執行 random_shuffle_array 擾亂順序，使用 list_add_tail 配合迴圈將陣列內的值分配給新的元素插入鏈結串列，在執行 list_quicksort 完後使用 list_for_each_entry_safe 檢查是否元素的值是正確的，主程式中間有錯誤都會透過 assert 中斷。

改進 random_shuffle_array

1. 使用 get_unsigned16() % (i + 1) 的方式可能會引入 modulo bias，因為若隨機數生成器的值域不是 (i+1) 的整數倍，則某些值被抽到的機率會略高。
2. 從尾開始（標準 Fisher–Yates）： 每一次交換都只影響當前未固定的區間，交換過程是局部且獨立的，因此能夠證明最終的排列是均勻的。
   從頭開始（forward variant）： 如果直接在原陣列上修改，交換或覆蓋的順序會使得前面產生的結果在後續迭代中再次被更改，而這就容易導致某些排列的出現機率與其他排列不同。

更改後的程式碼如下：

static inline uint16_t get_uniform_random(uint16_t n)
{
    uint16_t x;
    uint16_t max_usable = (UINT16_MAX / n) * n;
    do {
        x = get_unsigned16();
    } while (x >= max_usable);
    return x % n;
}

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = len - 1; i > 0; i--) {
        uint16_t j = get_uniform_random(i + 1);
        uint16_t tmp = operations[i];
        operations[i] = operations[j];
        operations[j] = tmp;
    }
}

get_uniform_random 先計算 (i+1) 在最大為 UINT16_MAX 下的最大公倍數 max_usable 並且呼叫原本的 get_unsigned16 但多做一個檢查是是否在 0 ~ max_usable 的值域下，若是的話就 return 代表這次抽樣是公平的; 反之則重新抽取。
random_shuffle_array 就更改為標準的 Fisher-Yates Shuffle。

為什麼 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting ?

因為 stable sorting 的定義是若兩個元素相同，那在經歷排序後他們的順序會符合原始順序。那假設我們採用 list_move 就會發生順序顛倒的情況。

範例：
初始狀況假設以 3 為 pivot

在執行原版list_for_each_entry_safe 建構的迴圈後

list_move 版本

雖然兩種都不影響最終數值排序的結果，但可以看到在 list_move 版本中排序的過程會照成順序顛倒，那在假設有元素相同的存在出現時就無法保證排序完的順序會是他們的初始順序。

測驗2

完整的程式碼：

static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {HHHH, 1, 0, IIII};

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 == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}

此函數要回傳前導零有多少個，並透過題目原本的敘述可以得知他要達到遞迴呼叫直到僅剩 2 位元（bits）需要檢查 leading zero ，因此這邊每一層的 upper 他是用 (x >> (16 >> c)); 來進行獲取，而這邊觀察遞迴呼叫的順序是當有 upper 時 c + 1 那可得知 c 的範圍就是0~3 ，分別用來分割 16、8、4、2 位元，並且 lower 也須透過與 mask[c] 進行 & 運算取得該取得，並且當 c = 3時應該要終止，因為分割到2位元了就可以直接查表獲取前導零。
最後透過觀察可得：
GGGG = 14
HHHH = 2 ( 00₂ 的前導數為 2 )
IIII = 0 ( 11₂ 的前導數為 0 )
JJJJ = 3
KKKK = 2 (若 upper 為零則前導數為 upper 所關注的位元數，像在這裡 c = 3 代表 upper 關注二位元)

之後 MMMM -> PPPP 在函式 uint64_t sqrti 裡，首先這個函式是想實做開平方根，而看向函式 (total_bits - 1 - clz64(x)) 這邊是想做取最高位 1 的位置，並且希望 shift 是 4 的冪次方因此還做了 & MMMM 的操作，為了達成 m 為 4 的冪次方，因此 MMMM 的值為 -1，因為 (-1)₂ = 11111111 11111111 11111111 11111110₂，這樣可以幫助他去除最低位元，這樣 m << 的操作的值只會是 2 的冪次方，而 m 又是 1ULL << 2 的冪次方的數，以數學表示為

$2^{2^k=shift}$ ，接下來就是逼近法的實作，在迴圈中 NNNN = 1 透過這樣在運算的結尾才會得到該 m 的平方根， PPPP = 2，這邊保持 m 四進位的看法下去看很直觀詳細解釋參考

allen chao的解釋

在迴圈中，會將m加到y，因為最後的答案應為每次加到y的m的開根號，因此每次迴圈均會將y除以2，讓y透過位元右移對其中不同的m值開根號，以 x = 1000 為例
y = 0
y = 256
y =

$\frac{256}{2}$ = 128
y =

$\frac{256}{2}$ + 64 = 192
y =

$\frac{256}{4}$ +

$\frac{64}{2}$ = 96
y =

$\frac{256}{4}$ +

$\frac{64}{2}$ + 16 = 112
y =

$\frac{256}{8}$ +

$\frac{64}{4}$ +

$\frac{16}{2}$ = 56
y =

$\frac{256}{8}$ +

$\frac{64}{4}$ +

$\frac{16}{2}$ + 4 = 60
y =

$\frac{256}{16}$ +

$\frac{64}{8}$ +

$\frac{16}{4}$ +

$\frac{4}{2}$ = 30
y =

$\frac{256}{16}$ +

$\frac{64}{8}$ +

$\frac{16}{4}$ +

$\frac{4}{2}$ + 1 = 31

這也可以驗證為何一開始要找偶數位元且每次m要右移2位(

$m÷4$)而不是1位，因為奇數位所表達的數值無法開根號為整數且

$\sqrt{2}$不是整數

測驗2延伸問題

在迴圈之後加入以下判斷式即可對

$\sqrt{x}$向上取整數，代表有剩下的數字，因此直接把 y ++ 即可涵蓋，達成向上取整數的效果。

if(x > 0){
  y++;
}

測驗3

這題是要用 Two Sum 來帶出 hash table 的應用和實作，這邊題目所提出的資料結構如下：

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

詳細結構設計解釋我覺得老師已經講得很清楚了，這邊直接看到題目本身，
首先先定義 hash 函式，這個函式是利用黃金比例 32 位元黃金比例常數 0x61C88647 與輸入的參數相乘，並保存當作哈希值。
再來看到 find_key 函式，這裡函式得目標是要取得輸入 key 所對應的 hashkey ，在一開始 struct hlist_head *head = &(map->ht)[hash(key, AAAA)]; 這個操作是想獲取這個 key 所對應的哈希值的起頭，因此 AAAA = map->bits ，這樣才能正確獲取 map 的位元的哈希值，獲取哈希值後透過迴圈則可配合 container_of 獲取 hashkey 本身並回傳。

map_get 配合 find_key 回傳 key 所對應的 data。

map_add 用意是要新增一個 hashkey 進入相對應的 map 內， BBBB = maps->bits ，跟先前的 find_key 一樣是用來取得正確的哈希值，CCCC = first->pprev ，更新原先第一個元素的 pprev 為西增的元素的 next 指標， DDDD = n->pprev，直接指向 h->first 的記憶體位址。

map_deinit 這個函式是要用來釋放記憶體， EEEE = n->pprev ，這段程式碼是要將前一個節點的 next 指向現在要刪除節點的下一個元素，也就是把目前的元素從表上移除。

測驗3延伸問題

程式碼解析上述解釋的差不多了，剩下最後的 two_sum 函式：
透過一個迴圈 O(N) 的時間複雜度，透過 map_get 去檢查有沒有 target - 目前的陣列的值，若有則回傳這兩個數字; 沒有則透過 map_add 新增目前陣列的值，最後透過 map_deinit 釋放整個 hash map 的記憶體，回傳答案。

測試程式碼

int main() {
    int nums[] = {2, 6, 27, 18, 12}; 
    int target = 24;
    int returnSize;
    
    int *result = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target, &returnSize);
    
    if (returnSize == 2) {
        printf("Answer: [%d, %d]\n", result[0], result[1]);
        free(result); 
    } else {
        printf("No answer found.\n");
    }
    
    return 0;
}