2025q1 Homework2 (quiz1+2)

contributed by <lum1nar>

quiz1

測驗一

main 函式

main() 中呼叫 test_suite() ，使用 my_run_test(test_list) 進行測試。一開始我疑惑 my_run_test 內部的 test() 是什麼，文件中都沒有定義，但後來發現要替換成傳入的函式 test_list()。

#define my_run_test(test)       \
    do {                        \
        char *message = test(); \ /* message = test_list() */
        tests_run++;            \
        if (message)            \
            return message;     \
    } while (0)

使用巨集來呼叫函式

我一直認爲巨集會把左方的內容全部展開成右方的內容，但其實是可以傳入參數的。

#define sqrt(x) x*x

sqrt(5) -> 5 * 5

再來，爲何要使用 do{} while(0) 呢？這是安全定義巨集的方法，考慮以下代碼

/* 巨集定義 */
#define my_assert(test, message) if (!(test)) return message;

/* 我們展開以下判斷式 */
if (condition)
    my_assert(some_test, "error");
else
    do_something();  // 這裡會導致語法錯誤

/* 展開後 */
if (condition)
    if (!(some_test)) return "error";  /* 這裡會因為沒有大括號導致 else 無法正確匹配 */
else
    do_something();

/* 如果加上do{}while(0) */
if (condition)
    do {
        if (!(some_test)) return "error";
    } while (0);

    do_something();  /* 這樣就不會有問題 */

test_list

這段程式首先做了 list_reset ， 將 items[i] 初始化爲 i。用意在於 list_insert_before 所傳入的是節點，而非整數，因此這一步先將要插入的數值放進節點中。最後，把 l.head 設爲 NULL 初始化鏈接串列。初始化完成後，使用迴圈在頭部插入節點，並透過 my_assert 來檢查是否有錯誤，後續的插入尾部也是相同的步驟。但不確定最後一次的插入和倒數第二次的有何區別。

圖示

以插入 999 爲例
首先，我們呼叫 list_insert_before

當 *p == before 時，我們將 *p 設爲 999，即把 head 指向 999

再來把後續節點接上，就完成了插入。

測驗二

測驗三

程式脈絡

陣列經過 shuffle 函數隨機排列過後，使用 list_construct 來插入節點。進行排序之後，使用 list_is_ordered 檢查是否結果正確，最後使用 list_free 來釋放所有節點。max_level 設爲 2n 有點讓我疑惑，即使每次分割後left 或 right 只有一個元素的情況下，應該也只需要 n 的空間就足夠了。

quicksort

首先，我們透過以下代碼將原本鏈接串列轉爲非環狀鏈接串列，並且傳入鏈接串列中第一個元素作爲開頭。

list->prev->next = NULL;
begin[0] = list->next;

將 L 和 R 指向當前鏈接串列的兩端，Pivot 設爲 L

將小於 Pivot 值的節點放入 left ，反之，則放入 right，再將 pivot、left、right分別放入 begin[i] 到 begin[i+2] 中，方便後續取出。

由 begin[i+2] 繼續進行分割，目的是用新的 left 覆蓋掉已經拆開的 right，就不會重複取到值

當分割到鏈接串列中只剩一個元素，或是 Right 不存在時，前者代表 Right 之中有最大值，我們直接取出。後者代表當前 pivot 擁有最大值，我們回到 begin[i-1] 去取出節點。

取完最大值之後，到了 begin[2] ，發現內部有大於一個節點，因此我們能夠用相同方法繼續分割

全部分割完後，我們可以確保，越大的節點，會放在 begin 中越後面的位置。因此我們只有從尾巴走訪到開頭，沿途將節點放入 result 中，即可完成排序。

最後再使用以下 rebuild_list_link 函式，將鏈接串列恢復成環狀，並且將開頭連結起來，就完成了。

    list->next = result;
    rebuild_list_link(list);

實際畫圖時會發現將節點移動到 left、right 時，鏈接串列之間的鏈接變得不好展示，時間因素影響，沒有全部畫出來，也因此對於細節的掌握度還不夠。

quiz2

測驗一

圖例

考慮以下鏈接串列

首先,我們將串列中第一個元素設爲 pivot 並且從鏈接串列中移除，再來把大於 Pivot 的元素移動到 list_greater，反之則移動到 list_less。

再來，分別對 less 和 greater 進行 quicksort，由於 less 只有一個元素，因此不必再拆分。

由於 less 爲空， greater 僅有一個元素，我們將三者依照 less，pivot，greater 的順序合併。

再次合併

做圖到最後一步時發現忘記加上 prev 指標。

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

考慮以下鏈接串列

我們依照上面的方式進行拆分，但把 list_move_tail 改成 list_move

拆開 greater

接下來依照 less，pivot，greater 的順序合併。


相同數值的節點重新進行了排序，因此不符合 Stable Sorting。

測驗二

測驗三

• map->bits 的大小決定了 bucket 的大小。
• 雜湊函數
  • 爲何在雜湊函數內部要乘以黃金比例呢？乘以黃金比例可以用來打散 key 的分佈,如果 key 本身的數據有某些模式會導致連續 key 落入相鄰的 bucket
  • 爲何要右移 (32 - bit) 呢？前面說道，map->bits 決定了 bucket 大小，因此我們僅需要 map->bits 個 bit。而更高位的 bit 更能使得 hash 分佈更平均。