2025q1 Homework2 (quiz1+2)

contributed by < HeatCrab >

第一周測驗一

解釋上方程式碼運作原理
- 首先，我們先定義串列：
```
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;
```
  這是一個簡單的單向鏈結串列。 list_item_t 是每個節點，裡面有個整數 value 跟一個指向下個節點的指標 next 。 list_t 是整個串列的結構，只存一個指向第一個節點（頭）的指標 head 。
- 接著，我們定義 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;
}
```
  這個函式的目標就是，找到 before 的位置，將 item 插入，並更新整個鏈結串列。
  1. 首先定義 list_item_t **p：
    我們用 list_item_t **p 的目的是為了能夠修改指標的指向，讓 p 能指向某個指標的位址。簡單講，p 是一個「指向指標的指標」 (list_item_t **) ，用來指向某個 list_item_t * 的位址。
    而 *p 會拿到 p 所指的內容，也就是一個 list_item_t * 。
  2. 接著透過 for 迴圈尋找 before：
    - 定義 &l->head ： 初始化 p ，讓他從串列的起點開始走訪，其中 p = &l->head 讓 p 指向 head 的位址，這樣 *p 可以檢查 head 後續指向的所有節點。
    - *p != before：確認當前 *p 是否已經指向了 before 的位址。
    - p = &(*p)->next 的作用：這步驟很重要，我們每一次都會將 *p 更新到下一個節點的 next 指標位址。
      如下圖：
      假設 node C 是我們的 before 。我們目前確認到 node B 不是 before ，所以我們指向了 node B -> next 這個位址，也就是 node C。進入到下一次迴圈的時候，我們發現我們找到的 node C 就是我們要找的 before ，那我們就可以在跳出 for 迴圈時，剛好就在我們要插入的位置，也就是 &(node B)->next 這個位置，插入我們的 item 。
  3. 更新我們的 *p 。
  4. 最後將 item->next 的位址重新接上 before 。
  5. 完成整個 list_insert_before 的函式。
- **p 與 &(*p) 的不同
  因為我忘記老師當時解釋的時候說的了，所以我直接透過規格書再查詢了一遍：
  1. 首先先確認 *p 的意義：
    - 根據 6.5.3.2
      
      The unary * operator denotes indirection. If the operand points to an object, the result is an lvalue designating the object.
    - 這裡 *p 是解參考 p 所指的內容。因為 p 是 list_item_t **，所以 *p 的型別是 list_item_t *，代表一個 list_item_t 節點的指標。
  2. &(*p) 的意義：
    - 對 *p 再取位址，&(*p) 會返回 *p 所指的記憶體位址。
    - 根據 6.5.3.2
      
      The operand of the unary & operator shall be either a function designator or an lvalue that designates an object that is not a bit-field and is not declared with the register storage-class specifier.
    - 因為 *p 是一個左值（指向某個 list_item_t * 的指標），所以 &(*p) 的型別是 list_item_t **，也就是 *p 的位址。
    - 在實作中，這是用來取得下一個節點指標的位址，方便修改鏈結（例如在 list_insert_before 中改 next 的指向）。
  3. **p 的意義：
    - **p 是對 *p 再做一次解參考。
    - 因為 *p 是 list_item_t *，所以 **p 的型別是 list_item_t，代表直接存取 *p 所指的節點本身（例如節點的 value 或 next 欄位）。
    - 根據 6.5.3.2
      
      If the operand [of *] has type ‘‘pointer to type’’, the result has type ‘‘type’’
    - 這是用來直接操作節點內容，而不是修改指標的連結。
- 最後簡單講解一次完整程式碼：
  1. 定義：
    - 根據 man-pages 中對於 assert 這個巨集的定義，是用來確保程式碼沒有出錯，若是出錯，我們就會 abort 我們的程式碼，並回傳提示訊息。
    - 定義一個固定大小的陣列 item[N] ，並初始化一個串列 l 。
    - 透過 list_reset 這個函式，初始化整個串列 l ，將每一個節點的 value 設為索引值（ 0 - 999 ），將next 設為 NULL ，並清空 l->head ，最後回傳初始化完成的串列 l 的位址。
  2. 測試內容：
    - 測試插入到開頭：用 list_insert_before(&l, l.head, &items[i]) 將 1000 個節點插入到串列開頭，檢查串列大小和值是否正確（應從 999 到 0 遞減）。
    - 測試插入到尾端：用 list_insert_before(&l, NULL, &items[i]) 將 1000 個節點插入到串列尾端，檢查串列大小和值是否正確（應從 0 到 999 遞增）。
    - 再次測試插入到尾端：重置串列後，再次用 list_insert_before(&l, NULL, &items[i]) 插入 1000 個節點，驗證一致性。
  3. 可能結果：
    - 答案無誤：
      ---=[ List tests ALL TESTS PASSED Tests run: 1
    - 答案有誤（報錯）：
      ---=[ List tests ERROR: Final list size should be N Tests run: 1

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

首先根據在 lab0-c 也就是作業一實作的 q_sort() ，想法直接去實作合併排序，但是後來發現，並沒有很直觀得使用到 list_insert_before ，但又沒什麼想法，所以決定去看看動畫， merge sort 的動畫，希望透過畫面感來找到感覺。
看完之後很有感覺，也就想到以下程式碼的解法。在實作合併排序的程式碼，在處理合併這個動作時，通常會在左串列與右串列中尋找最小值，再依序排序好做合併的動作。但是現在有了 list_insert_before 這個函式，就不再需要同時確認左右兩個串列，確認其中一個就好了。
我的做法是讓右串列維持，並依序將左串列的元素依依比較後，找到要插入的位址，用 list_insert_before 這個函式完成排序。
其中我使用了一個暫時的 temp_list 串列來協助我做排序。因為我在實作時發現，如果我直接用原先的串列來排序鏈結的話，會發生記憶體上的問題，因此我決定拉出來做排序合併，等處理完後再重新把鏈結接回去。如下圖舉例：

我們接下來要先將3插入到右串列中，透過 while 迴圈我們找到 before 是6。

最後插入的結果如下：

程式碼如下：

// 合併兩個已排序的子串列，將 left 插入 right，使用 list_insert_before
static void merge(list_t *l, list_item_t *left, list_item_t *right, list_item_t **result) {
    if (right == NULL) {
        *result = left;
        return;
    }
    if (left == NULL) {
        *result = right;
        return;
    }

    // 遍歷 left，將每個節點插入 right 的正確位置
    list_t temp_right = { .head = right };
    while (left != NULL) {
        list_item_t *to_insert = left;
        left = left->next;

        // 找到 right 中的插入位置
        list_item_t *before = temp_right.head;
        list_item_t *prev = NULL;
        while (before != NULL && before->value < to_insert->value) {
            prev = before;
            before = before->next;
        }

        // 使用 list_insert_before 插入到 temp_right
        list_insert_before(&temp_right, before, to_insert);
        if (prev == NULL) {
            temp_right.head = to_insert;
        } else {
            prev->next = to_insert;
        }
    }

    *result = temp_right.head;
}

但是我後來發現，因為我這樣做是要不斷重新找到 before 的節點，也就是我必須重複遍歷串列，才能找到我要插入的位址，當我的左右串列長度接近時，我的時間複雜度會變成

O (n^{2})

。於是我新增了一個變數 last_before 來記錄上一次的 before ，這樣就可以不用重複遍歷已經確認過的串列，從上一次插入後的位址開始繼續插入即可。

        list_item_t *before = (last_before != NULL && 
                               last_before->next != NULL) ? 
                        last_before->next : temp_right.head;
        list_item_t *prev = last_before; // 從上一次的 prev 開始
        ...
        list_insert_before(&temp_right, before, to_insert);
        if (prev == NULL) {
            ...
        }
        last_before = prev; // 更新 last_before
        ...

最後透過以下程式碼測試：

static char *test_suite(void) {
    my_run_test(test_list);
    my_run_test(test_merge_sort);
    return NULL;
}

預期結果

---=[ List tests
ALL TESTS PASSED
Tests run: 2

第一週測驗二

解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

remove_free_tree：
BST 移去節點的方法可以分成以下三大類：
1. 移去的目標有兩個子節點：
  
  if ((*node_ptr)->l && (*node_ptr)->r)
  
  在 remove_free_tree 這個函式中，當出現要刪除的目標節點有兩個子節點得情況時，做法上會先找到中序的 predecessor ，也就是移去目標節點後，要補上位置來完善整個樹的節點。
  接著先來簡單地說一下中序：左->中->右。
  所以用我們上圖中的樹來舉例的話，他的中序就是：1->2->3->4->5->6->7
  那這跟我們要尋找用來取代目標節點的節點有什麼關係呢？因為在樹的移去方法中，目標節點的左子樹中的最右節點，即是用來取代我們移去目標節點後的節點，也就是目標節點在中序上的 predecessor。
```
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r) 
    pred_ptr = &(*pred_ptr)->r; 
```
  我們令 predecessor 為 pred_ptr ，並使用指標的指標來接受位址上的賦值，也就是定義為目標節點的左子樹的 head 。接著透過 while 迴圈，一路向右節點搜尋，直到找到最右的節點為止，那個節點就是目標節點在中序排列上的 predecessor。
  但這時候會發生兩個問題：
  - 如果目標節點的左子樹中，沒有右子樹，或者說沒有任何的右節點的話，這個左節點就會是 predecessor，如下圖，若是目標節點是 4 ：
    我們的 pred_ptr 就是2，也就是我們要找的 predecessor 。
    接著就將原本目標節點4的右子樹接上，形成一個全新的樹，如下圖：
  - 那如果不是這樣的前述的情況，也就是有目標節點有右子樹的情況，一樣假設我們要移去的節點是4：
    我們的 pred_ptr 也就是 predecessor 就是3。
    那首先，我們會先將目標節點的左右子樹的鏈結定義好，也就是圖中的綠色箭頭與紅色箭頭。接著用遞迴的手法，呼叫 remove_free_tree 這個函式來移去3。如下圖：
    最後確認3這個節點再遞迴的呼叫下，樹都已經處理完畢，我們就將目標節點4取代為3，並將左右子樹，也就是綠色與紅色的箭頭接回去，如下圖：
2. 移去的目標只有一個子節點：
  
  else if ((*node_ptr)->l || (*node_ptr)->r)
  
  先判斷這個唯一的子節點是不是在左邊，是的話，將他當成新的節點，取代目標節點，不是的話，改用右節點將目標節點取代。
```
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
```
3. 移去的目標沒有子節點：
  
  else
  
  目標節點沒有子節點，那我們就直接將節點移去。
最後將目標節點的左右子樹指標設為 NULL 防止迷途指標的發生。
```
    target->l = NULL;
    target->r = NULL;
```

find_free_tree：
尋找目標節點，並回傳記憶體位址。透過 BST 的特性，使用遞迴的方式，透過 size 來判斷應該在左子樹還是右子樹。

block_t **find_free_tree(block_t **root, block_t *target) 
{
    if (!root || !*root) return NULL;
    if (*root == target) return root;
    if (target->size < (*root)->size) {
        return find_free_tree(&(*root)->l, target);
    } else {
        return find_free_tree(&(*root)->r, target);
    }
}

find_predecessor_free_tree：

block_t *find_predecessor_free_tree(block_t **root, block_t *node) 
{
    if (!node || !node->l) return NULL;
    block_t *pred = node->l;
    while (pred->r) {
        pred = pred->r;
    }
    return pred;
}

實驗：
下圖是實驗時使用的初始樹：

分別操作以下步驟：

移去55: 當目標節點有兩個子節點（樹）的情況。
移去2: 當目標節點只有一個子節點（樹）的情況。
移去17: 當目標節點沒有子節點（樹）的情況。
移去16: 當目標節點有兩個子節點（樹），且會需要使用遞迴處理 deprecessor 的子節點的情況。
移去72: 當目標節點有兩個子節點（樹）的情況。
移去16: 確認是否有成功移去，且沒有發生記憶體問題。

最後得到下圖結果：

以下實驗用部分程式碼：

block_t *build_test_tree() 
{
    block_t *root = NULL;
    size_t values[] = {16, 6, 55, 2, 11, 18, 72,
                       1, 8, 17, 23, 62, 80};
    int num_values = sizeof(values) / sizeof(values[0]);
    for (int i = 0; i < num_values; i++) {
        insert_node(&root, values[i]);
    }
    return root;
}

int main() {
    block_t *root = build_test_tree();
    size_t targets[] = {55, 2, 17, 16, 72, 16};
    int num_targets = sizeof(targets) / sizeof(targets[0]);

    printf("初始中序遍歷：");
    print_inorder(root);
    printf("\n");
    /* 也可以使用 assert() */
    if (!is_bst_valid(root, 0, SIZE_MAX)) {
        printf("錯誤：初始樹無效\n");
        free_tree(root);
        return 1;
    }

    for (int j = 0; j < num_targets; j++) {
        block_t *target = find_node_by_size(root, targets[j]);
        // block_t *target = find_node_by_size(root, targets[j]);

        printf("移去節點：%zu\n", targets[j]);
        if (target) {
            remove_free_tree(&root, target);
        } else {
            printf("找不到目標節點：%zu\n", targets[j]);
        }
        printf("移去後中序遍歷：");
        print_inorder(root);
        printf("\n");

        if (!is_bst_valid(root, 0, SIZE_MAX)) {
            printf("錯誤：移除節點 %zu 後樹無效\n", targets[j]);
            break;
        }
    }

    free_tree(root);
    return 0;
}

以下是輸出結果：

初始中序遍歷：1 2 6 8 11 16 17 18 23 55 62 72 80 
移去節點：55
移去後中序遍歷：1 2 6 8 11 16 17 18 23 62 72 80 
移去節點：2
移去後中序遍歷：1 6 8 11 16 17 18 23 62 72 80 
移去節點：17
移去後中序遍歷：1 6 8 11 16 18 23 62 72 80 
移去節點：16
移去後中序遍歷：1 6 8 11 18 23 62 72 80 
移去節點：72
移去後中序遍歷：1 6 8 11 18 23 62 80 
移去節點：16
找不到目標節點：16
移去後中序遍歷：1 6 8 11 18 23 62 80

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

todo

第一週測驗三

解釋上述程式碼運作原理

其實我覺得老師在測驗題裡講解的就很淺顯易懂了，所以我想比較一下使用 list.h 或者說 Linux API ? 來微調程式後的 quick_sort 與根據〈Optimized QuickSort — C Implementation (Non-Recursive)〉實作的程式碼的異同。
我參考了在 NCKU wiki 上2024第一週測驗的第一題題目與 weihsinyeh 實作的題解。我就偷懶一下，直接借用了別人寫的正解：

void quick_sort(node_t **list)
 {
     int n = list_length(list);
     int value;
     int i = 0;
     int max_level = 2 * n;
     node_t *begin[max_level], *end[max_level];
     node_t *result = NULL, *left = NULL, *right = NULL;

     begin[0] = *list;
     end[0] = list_tail(list);

     while (i >= 0) {
         node_t *L = begin[i], *R = end[i];
         if (L != R) {
             node_t *pivot = L;
             value = pivot->value;
             node_t *p = pivot->next;
             pivot->next = NULL;

             while (p) {
                 node_t *n = p;
                 p = p->next;
                 list_add(n->value > value ? &right : &left, n);
             }

             begin[i] = left;
             end[i] = list_tail(&left);
             begin[i + 1] = pivot;
             end[i + 1] = pivot;
             begin[i + 2] = right;
             end[i + 2] = list_tail(&right);

             left = right = NULL;
             i += 2;
         } else {
             if (L)
                 list_add(&result, L);
             i--;
         }
     }
     *list = result;
 }

commit 803b10d by weihsinyeh

接下來我會稱上方程式碼為初版，稱使用 list.h 的程式碼為 Linux 版，方便比較與辨別。^[1]

初始化：
- 初版：
  - 使用 node_t（含 left、right、next 和 value），但僅利用 next 作為單向鏈結串列。
  - 定義 begin 和 end 陣列，分別儲存子串列的頭節點和尾節點。
  - 將串列頭放入 begin[0]，尾節點由 list_tail 計算並存入 end[0]。
- Linux 版：
  - 使用 list.h 的 struct list_head（含 prev 和 next），嵌入 node_t 中，支援雙向鏈結串列。
  - 僅定義 begin 陣列，尾節點由 list_tail 動態計算。
  - 將第一個節點放入 begin[0]，斷開循環結構以適應單向處理。
- 優化：
  Linux 版減少記憶體使用（移除 end），適應雙向結構，提升通用性。
if (L != R)：
- 初版：
  - 從 node_t 直接取基準值（pivot->value）。
  - 更新 begin 和 end，儲存 left、pivot 和 right 的頭尾節點。
- Linux 版：
  - 使用 list_entry 從 list_head 提取 node_t 的值。
  - 僅更新 begin，尾節點由 list_tail 計算。
- 優化：
  Linux 版提升結構通用性，減少記憶體使用，簡化堆疊管理。
while (p) 迴圈：
- 初版：
  - 直接從 node_t 取值（n->value）。
  - 使用 list_add 將節點插入 left 或 right（假設為頭部插入）。
- Linux 版：
  - 使用 list_entry 提取值。
  - 手動操作 next 指標插入節點。
- 優化：
  Linux 版避免函數呼叫，提升效能並增加控制性。

排序完成後的串列定義：

初版：
- 直接更新頭指標，生成單向鏈結串列。
- node_t 的 left 和 right 未使用，未初始化 prev。

Linux 版：

設置 list->next 並呼叫 rebuild_list_link，生成雙向鏈結串列。
rebuild_list_link 重建 prev 指標，形成完整結構。

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

透過 while 迴圈，遍歷單向串列，設置每個節點的 prev 指標，並連回頭節點，生成循環雙向鏈結串列。

優化：
Linux 版提升穩定性與功能性，支援雙向操作。

除此之外，在兩段程式碼皆定義了 max_level 這個變數。定義為要排序串列長度的兩倍。會這樣定義是因為當我們發生 worst case ，像是串列已經是升序或是降序排列的狀態，就會需要多花最多一倍的空間來處理。

[1]: 使用 GROK3 協助整理與潤飾

研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

todo

第二週測驗一

解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting

在完善程式碼前發現，老師提供的選項裡 list_for_each_entry_reverse 並沒有存在，所以我寫了一個整合進 list.h
根據 Linux kernal api 、 torvalds \ linux 以及參考老師的 list.h 中實作的 list_for_each_entry 程式碼做調整。

#if __LIST_HAVE_TYPEOF
#define list_for_each_entry_reverse(entry, head, member)           \
    for (entry = list_entry((head)->prev, typeof(*entry), member); \
         &entry->member != (head);                                 \
         entry = list_entry(entry->member.prev, typeof(*entry), member))
#else
#define list_for_each_entry_reverse(entry, head, member) \
    for (entry = (void *) 1; sizeof(struct { int i : -1; }); ++(entry))
#endif

做法很簡單，就是把 (head)->next 的 next 改成 prev ，讓串列往反方向遍歷。
有趣的是，這個函式並沒有在這邊被使用到，有點可惜。

list_quicksort：
- 先定義與初始化變數，並確認串列長度是否大於1，符合排序資格。
- 透過 INIT_LIST_HEAD 初始化兩個串列，greater 用來裝入比 pivot 大的節點， lesser 用來裝入比 pivot 小的節點。
- 使用 list_first_entry 將找到串列的第一個節點，並將他定義為 pivot ，然後使用 list_del 函式先將 pivot 移去。
- 通過 list_for_each_entry_safe 函式遍歷整個串列，並使用 cmpint 比較節點與 pivot 的大小。
  - 因為我們是傳入 const void 這個資料型別，所以我們要透過轉換成 uint16_t 來作比較。
  - 最後回傳直接透過兩者相減，如果 i1 > i2 回傳一個大於零的值，判斷式為真，表示此節點大於 pivot ，否則回傳小於等於零的值，判斷式為假，此節點小於等於 pivot 。
- 接著使用 list_move_tail 將節點依序接在尾端，使排序方法穩定。
- 接著透過遞迴呼叫，將 lesser 與 greater 兩個串列排序完成。
- 使用 list_add 先將 pivot 接在 head 的後面。
  - 這邊如果使用 list_add_tail 的話，會讓 pivot 最後被接在串列的最尾端。
- 接著使用 list_splice 跟 list_splice_tail 分別將 lesser 與 greater 這兩個串列，接在 pivot 之前與之後，完成整個排序
main 是如何測試的：
- 使用 random_shuffle_array 定義一個亂數陣列。
- 並將這個亂數陣列透過 for 迴圈實踐在 temp_list 上
- 分別呼叫 C 函數庫中的 qsort 函式與撰寫好的 list_sort 函式，進行排序。
- 使用 list_for_each_entry_safe 來確認 list_sort 的排序結果是否符合 qsort 排序出的結果。
- 整個過程皆使用 assert 確認是否出現問題。

改進 random_shuffle_array：

使用 uint16_t j = get_unsigned16() % (i + 1); 帶來的風險：
當 i + 1 不是 2 的整數次方時，模運算會導致隨機數的分佈不均勻（偏誤）。這是因為 65536（get_unsigned16() 的範圍）無法均勻分割成 i + 1 個等份，較小的索引值會被選擇的機率略高。
Fisher-Yates 洗牌的實現問題：
理想的 Fisher-Yates 洗牌應該從陣列末端開始向前遍歷，並在範圍 [0, i] 中均勻隨機選擇一個索引進行交換。但這裡的實現從頭開始（i 從 0 到 len-1），並使用有偏誤的隨機數，這可能導致洗牌結果不完全隨機。

以下改進上方問題後的程式碼：

#include <stdlib.h>
#include <time.h>

static inline uint16_t rand_range(uint16_t max)
{
    uint16_t limit = RAND_MAX - (RAND_MAX % max);
    uint16_t r;
    do {
        r = rand();
    } while (r >= limit);
    return r % max;
}

static inline void random_shuffle_array(uint16_t *operations, 
                                        uint16_t len)
{
    if (len <= 1) return;
    for (uint16_t i = len - 1; i > 0; i--) {
        uint16_t j = rand_range(i + 1);
        uint16_t temp = operations[i];
        operations[i] = operations[j];
        operations[j] = temp;
    }
}

int main(void)
{
    srand(time(NULL)); // 初始化隨機數種子
    // 其餘 main 程式碼不變
    random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));
    // ...
}

方法上定義一個新的函式 rand_range ，使用減法與除法來定義一個 limit 變數，防止因為系統不同，導致最大值的不穩定。
使用 while 迴圈生成隨機變數 r 直到他小於變數 limit 。
最後再雙重保險，將 r 模 max 進行縮放。

為何使用 list_move 會導致排序變得不穩定：

根據 list.h 中對於 list_move_tail 跟 list_move 的定義，我們可以知道，list_move_tail 會將節點依序接在尾部， list_move 則會將節點接在頭部。
所以當在排序時，使用 list_move 就會出現相等元素在排序過程中發生翻轉的狀況，導致排序不穩定

以下圖片舉例使用 list_move_tail 與 list_move 在排序時的情況：
初始的串列

使用 list_move_tail 後，第一次分割的結果：

使用 list_move 後，第一次分割的結果：

可以發現，在使用 list_move 後的排序，相同元素的節點間的相對順序被打亂，從原先的 A2 到 A4 ，變成 A4 在頭， A2 在尾的情況了。
這也導致了以下的結果：

在使用 list_move 函式後，因為在過程中，節點間的相對順序已經被翻轉，這也導致最後排序完成後，表面上排序結果正確，實際上相同的節點的相對順序已經被打亂了。

將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋

todo

第二週測驗二

解釋上述程式碼，並探討擴充為
$⌈ \sqrt{x} ⌉$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作
1. 探討 clz2()：
  clz2() 是用於實作開平方根的重要函式，他的作用是透過遞迴呼叫計算數字中前導零的數量。這個函式傳入的變數 x 與 c 分別的資料型別分別是 uint32_t 跟 int 。 x 會被轉成個32 bits 的數字，所以我們知道接下來計算前導零都是會以32位元為基準。
```
if (!x && !c)
    return 32;
```
  這個判斷式是為了節省運算成本。如果我們確認 x 全零，且 c 也為零，表示並未經過任何的遞迴，可以確認 x 的前導零數量就是32。
  接著我們做分割的動作，將 x 分割兩半，命名為 upper 與 lower 。
```
uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));
```
  在分割的過程，我們會使用到 mask 這個陣列。
```
static const int mask[] = {0, 8, 12, 14};
```
  mask 陣列顧名思義，就是用來處理位元遮罩的。那為什麼分別是0、8、12以及14，這四個數字呢？
  以下表格說明：
  
  i mask[i] 作用
  
  0 0 取完整的16位數
  
  1 8 16/2=8，接著取八位數
  
  2 12 8/2=4，接著取四位數
  
  3 14 4/2=2，接著取最低的兩位數
  
  所以隨著 c 的不同，我們要遮罩的數量也會隨之改變，這個過程是依照32位元被逐漸切半、切半直到我們最後的2位元為止。
  最後則是遞迴的判斷：
```
if (c == 3)
    return upper ? magic[upper] : 2 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
```
  這邊設計上有許多有趣的點：
  1. c == 3：為什麼 c 最多設計3就停止遞回呢？
    這邊假定 clz2 是從 c = 0 開始做運算，當 c = 3 的時候剛好32被除至2，也就是要判定的最小位元數，此時會回傳我們最終數到的結果。
  2. magic 陣列：
```
static const int magic[] = {2, 1, 0, 0};
```
    說實話，這個變數名稱取得不好。根據遞迴最後的回傳，會回傳的即是2位元時有多少零。那兩位元總共就是以下四種可能：
    
    i magic[i] 2位元表示
    
    0 2 00
    
    1 1 01
    
    2 0 10
    
    3 0 11
    
    這樣子 magic 陣列就是一個查詢用的表才對，所以是我的話，會把變數命名為 clz2_table ，這樣會來的直觀一些。
  3. 回傳值：
    - 這邊有趣的點是，程式碼皆是以 upper 為判斷的基準，爲什麼會這樣呢？這就要回到我們一開始說我們將 x 分割成一半的意義了。如果我們的 x 在第一次切割成16與16位元時， upper 剛好是一個非零的數，因為這個函式要找的是有多少前導零，此時 lower 就可以直接忽略不計，減少許多的運算成本。
    - 當 c == 3 時，如果 upper 不全為零，我們直接根據 magic 陣列去查表，找到前導0的數量回傳。若是 upper 為零，我們則查找 lower 的前導零數量，並加上2。因為 upper 此時是最小位數，也就是2位元，所以最多2個零。
    - 當 c != 3 時，持續遞迴。如果 upper 非零，如前述，可以直接忽略 lower ，繼續回傳 upper 即可。否則根據位元運算子 >> 判斷當前 upper 的位數，將其前導零的數量加上，繼續遞迴 lower 做運算。
2. 定義與延伸：
  首先明確將 clz2(x, 0) 定義為 clz32(x) ，如我們前面所述，用來數32位元數字有多少個前導零。
  接著定義函式 clz64() ，這邊傳入的 x 資料型別使用 uint64_t ，讓傳入變數變成64位元。
  並使用跟在 clz2() 相同的邏輯，如果上32位元不為0，就實作上32位元即可，否則就實作後32位元，並在最後計數上加上32，加上32位元的32個0。
3. sqrti() 函式的實作：
  - 因為我已經忘記當時測驗時作答的結果，所以我都會再次作答，並作答到表單滿分為止。但是我在作答 sqrti() 這個函式的 NNNN 與 PPPP 時，卻出現了提示：
    
    於是我決定查查規格書：
    
    6.5.7 Bitwise shift operators
    4. Each of the operands shall have integer type.
    5. The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
    
    所以得證只能為0，但是這樣是無意義的，因為 >>= 0 表示沒有任何動作，那這段程式碼正常來說就沒有書寫的必要了。
    但我覺得是自己的問題，所以我不信邪的送出表單：
    
    很好，果然是錯誤的。
    目前又找到你所不知道的 C 語言: bitwise 操作裡面說，是可以負數操作的，但是要看編譯器如何實作的，通常會是算術位移。
    
    ~~以下會先用， NNNN=1 與 PPPP=2 做解釋。~~
    ＊更新＊老師表單錯了，以下開始解釋 sqrti 函式。
  - 透過閱讀從 √2 的存在談開平方根的快速運算與 2025-02-25 課程問答簡記中可以得知 sqrti 函式是基於 digit-by-digit 方法去實作的。^[2]
    1. 逐位計算的數學基礎
      
      假設
      $N$ 是平方根，則
      $N^{2}$ 可以用二進位表示逼近：
      
      $\begin{aligned} N^{2} & \approx (b_{n} \times 2^{0} + b_{n - 1} \times 2^{1} + \dots b_{1} \times 2^{n - 1} + b_{0} \times 2^{n})^{2} \\ = (a_{n} + a_{n - 1} + \dots a_{1} + a_{0})^{2} \end{aligned}$
      - $b_{i} \in {0, 1}$ ，表示二進位中每個位元的值。
      - $a_{m} = b_{m} \times 2^{m}$ ，表示該位元對應的權重（例如
        $a_{m} = 2^{m}$ 或
        $0$ ）。
      為什麼這樣設計？
      - 逐位逼近：從最高位
        $m$ 開始（由 clz64(x) 計算），逐位測試
        $a_{m} = 2^{m}$ 或
        $0$ ，決定是否將該位加入結果。
      - 效率：這種方法只需要
        $\log_{2} (x)$ 次迭代（因為每次處理一位或一組位元），遠比線性搜索（例如從 0 加到
        $\sqrt{x}$ ）高效。
      在 sqrti 中：
      - m = 1ULL << shift 初始化為最高位的權重（例如
        $2^{4} = 16$ ）。
      - while (m) 從最高位到最低位迭代，每次測試一個位元。
    2. 使用
      $P_{m}$ 來逼近
      
      筆記中定義了
      $P_{m}$ 表示當前逼近的結果：
      
      $P_{m} = P_{m + 1} + a_{m}$
      - $a_{m} = 2^{m}$ （如果該位是 1）或
        $0$ （如果該位是 0）。
      - 判斷條件：
        
        $P_{m} = {\begin{cases} P_{m + 1} + 2^{m}, & if P_{m}^{2} \leq N^{2}, \\ P_{m + 1}, & otherwise. \end{cases}$
      為什麼這樣設計？
      - 避免直接計算平方：直接計算
        $P_{m}^{2}$ 需要乘法運算（例如
        $(y + m)^{2}$ ），對於 64 位元整數來說成本高且可能溢位。
      - 簡化為加減法：筆記中引入了
        $Y_{m} = (2 P_{m + 1} + a_{m}) a_{m}$ ，表示當前位元的貢獻，並用
        $X_{m} = N^{2} - Y_{m}$ 來計算誤差。
      在 sqrti 中：
      - y 對應筆記中的
        $P_{m + 1}$ ，表示當前已經計算的平方根部分。
      - m 對應
        $a_{m} = 2^{m}$ ，表示當前測試的位元權重。
      - b = y + m 對應
        $P_{m} = P_{m + 1} + a_{m}$ ，表示如果接受當前位元，新的逼近值是多少。
      - if (x >= b) 對應
        $P_{m}^{2} \leq N^{2}$ ，但為了避免計算平方，直接比較
        $x$ （剩餘值）與
        $b$ ，這是一個簡化的判斷。
    3. 位元移位的設計
      
      筆記中進一步優化了計算，引入了
      $c_{m}$ 和
      $d_{m}$ ：
      - $Y_{m} = c_{m} + d_{m}$ ，其中：
        
        $c_{m} = P_{m + 1} \times 2^{m + 1}$
        
        $d_{m} = (2^{m})^{2}$
      - 迭代關係：
        
        $c_{m - 1} = {\begin{cases} c_{m} / 2 + d_{m}, & if a_{m} \neq 0, \\ c_{m} / 2, & if a_{m} = 0. \end{cases}$ $d_{m - 1} = d_{m} / 4$
      為什麼這樣設計？
      - 位元移位的高效性：
        
        $c_{m} / 2$ 對應右移 1 位（>> 1）。
        
        $d_{m} / 4$ 對應右移 2 位（>> 2）。
        
        這與 sqrti 中的 y >>= 1 和 m >>= 2 直接對應。
      - 避免乘法：
        
        筆記中的
        $2^{m + 1}$ 、
        $(2^{m})^{2}$ 等運算都可以用位元移位實現。
        
        例如，m >>= 2 實現了
        $2^{m} \to 2^{m - 2}$ ，對應
        $d_{m - 1} = d_{m} / 4$ 。
      在 sqrti 中：
      - y >>= 1 對應
        $c_{m - 1} = c_{m} / 2$ ，調整當前結果的位元位置。
      - m >>= 2 對應
        $d_{m - 1} = d_{m} / 4$ ，移動到下一個位元權重。
    4. 誤差計算與更新
      
      筆記中提到：
      - $X_{m} = N^{2} - P_{m}^{2} = X_{m + 1} - Y_{m}$
      - $Y_{m} = (2 P_{m + 1} + a_{m}) a_{m}$
      為什麼這樣設計？
      - 誤差逐步減小：
        
        $X_{m}$ 是實際值
        $N^{2}$ 與當前逼近值
        $P_{m}^{2}$ 的誤差。
        
        每次迭代減去
        $Y_{m}$ ，逐步逼近
        $N^{2}$ 。
      - 簡化計算：
        
        直接計算
        $P_{m}^{2}$ 需要乘法，筆記通過
        $Y_{m}$ 將其轉換為加法和位移。
        
        在 sqrti 中，x 對應
        $X_{m}$ ，每次減去
        $b$ （即
        $y + m$ ），對應
        $X_{m} = X_{m + 1} - Y_{m}$ 。
      在 sqrti 中：
      - x -= b 對應
        $X_{m} = X_{m + 1} - Y_{m}$ ，減去當前位元的貢獻。
      - y += m 對應
        $P_{m} = P_{m + 1} + a_{m}$ ，將當前位元加入結果。
4. 擴充為
  $⌈ \sqrt{x} ⌉$ (向上取整數) 實作
  一開始的 sqrti 函式是向下取整數，也就是
  $⌊ \sqrt{x} ⌋$ 。根據上方說明我們可以知道 while 迴圈會結束在 m 為零的時候，可是此時的 x 若不是完全平方數，仍舊不為0，所以可以藉由判斷 x 是否大於0 ，來判斷 y 是不是需要進位。
  因此想要將 sqrti 變成取
  $⌈ \sqrt{x} ⌉$ 只需要在 while 迴圈結束後新增以下這個判斷式即可：
```
    if (x > 0)
        y += 1;  
```

i	mask[i]	作用
0	0	取完整的16位數
1	8	16/2=8，接著取八位數
2	12	8/2=4，接著取四位數
3	14	4/2=2，接著取最低的兩位數

i	magic[i]	2位元表示
0	2	00
1	1	01
2	0	10
3	0	11

[2]: 使用 GROK3 整理與潤飾

參照計算機結構測驗題 C 及其注釋，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格。對照 sqrtf, rsqrt, reciprocal implementations in Arm assembly

todo
參照從 √2 的存在談開平方根的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能

一旦發現效能改進的機會，可準備提交改進 int_sqrt 程式碼到 Linux 核心

第二週測驗三

解釋上述程式碼運作原理，應提供測試程式碼

針對 Linux 核心的 hash table 實作，提供更多圖例並揣摩 Linux 核心開發者

閱讀完 Linux 核心的 hash table 實作會對整個程式碼的實作上會有更深的體悟，像是使用指標的指標 **prev 來提升記憶體效率與統一操作，以及使用 GOLDEN_RATIO_32 的原因，以及實驗後的驗證。
首先，解釋程式碼運作原理：

初始結構定義與設計：
hlist_head 是一個簡單的結構，只包含指向第一個節點的指標 *first：
```
struct hlist_head {
    struct hlist_node *first;
};
```
hlist_node 是鏈結串列的節點，包含指向下一個節點的 *next 和一個雙重指標 **pprev：
```
struct hlist_node {
    struct hlist_node *next, **pprev;
};
```
這種設計不同於傳統雙向鏈結串列（prev 和 next 各一個指標）。**pprev 指向「指著當前節點的指標」（可能是 hlist_head->first 或前一節點的 next），而不是直接指向前一節點。

map_t 是雜湊表的整體結構，包含桶數的位元數 bits 和桶陣列 ht：
```
typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;
```
桶數由 MAP_HASH_SIZE(bits) 定義為 2^bits，例如 bits=3 表示 8 個桶。
```
#define MAP_HASH_SIZE(bits) (1<<bits)
```
hash_key 是儲存鍵值對的結構，內嵌一個 hlist_node 用於鏈結：
```
struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};
```
以下是雜湊表的結構示意圖：

假設 bits=2（4 個桶），插入了兩個鍵值對 (1, "one") 和 (5, "five")，其中 hash(1, 2)=1 和 hash(5, 2)=1 發生衝突：
圖中，桶 1（ht[1]）包含兩個節點，hk1 的 pprev (紅色）指向 ht[1].first，hk5 的 pprev （藍色）指向 hk1.node.next，形成鏈結。

為什麼用 hlist 而非傳統雙向鏈結串列？

Linux 核心開發者認為，在雜湊表這種場景下，桶數可能高達數千（如進程表或緩存結構），傳統雙向鏈結串列的頭結構（需要 prev 和 next 兩個指標）會浪費大量記憶體。hlist_head 只用一個 first 指標，節省了一半空間，這一點在核心註解中也有體現：

"Mostly useful for hash tables where the two pointer list head is too wasteful."
雜湊函數 (hash) 定義：
```
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
運作原理：
1. 輸入 val（鍵）和 bits（桶數的位元數，例如 bits=3 表示 8 個桶）。
2. 將 val 乘以常數 GOLDEN_RATIO_32（黃金分割相關值，約為
  $2^{32} * \frac{(3 - \sqrt{5})}{2}$ 。
3. 右移 (32 - bits) 位，保留高位元，結果範圍為 [0, 2^bits - 1]。
例如：val=1, bits=2：
- 1 * 0x61C88647 = 0x61C88647。
- 0x61C88647 >> (32 - 2) = 0x61C88647 >> 30 = 1（因為高 2 位是 01）。
- 映射到桶 1。
簡單展示鍵映射過程（bits=2，4 個桶）：
1. 為什麼用黃金分割常數？
  開發者可能受到 Donald Knuth 的啟發，Knuth 在《計算機程式設計藝術》中證明黃金分割相關值（如 phi^-2）能產生均勻分佈，減少碰撞和叢集。這對於核心中處理隨機或連續鍵（如記憶體位址）的場景尤為重要。
2. 為什麼用位元移位而非浮點運算？
  核心環境偏好整數運算，>> (32 - bits) 比傳統乘法方法（⌊m * (KA - ⌊KA⌋)⌋）更快，且在嵌入式系統中更高效。註解中提到：
  
  "High bits are more random, so use them."
  
  這顯示開發者刻意選擇高位元以提升隨機性。
相關輔助函式：
- 初始化 (map_init)：這是雜湊表的起點，負責分配並初始化結構。
  
  以初始化後的空雜湊表（bits=2，4 個桶）為例：
  圖中，ht 是一個陣列，每個 hlist_head 的 first 指向 NULL，表示空表。
- 查詢 (map_get 和 find_key)：從雜湊表中獲取值。
  - find_key：
    計算桶索引，獲取對應的 hlist_head。接著從 first 開始遍歷鏈結串列。並用 container_of（假設為標準宏）將 hlist_node 轉換為 hash_key。若找到匹配的鍵，返回該節點；否則返回 NULL。
  - map_get：調用 find_key，若找到則返回 data，否則返回 NULL。
- 插入 (map_add)：將鍵值對加入雜湊表。
  - 先用 find_key 檢查鍵是否已存在，若存在則退出（不覆蓋）。
  - 分配新的 hash_key 節點，設置 key 和 data。
  - 計算桶索引（hash(key, map*>bits)），獲取對應的 hlist_head。
  - 將新節點插入鏈結串列頭部：
  用 key=1, data="one" 到桶 1（bits=2）舉例：
  
  插入前：
  插入後：
  為什麼選擇頭部插入？
  可能是因為在插入操作應保持
  $O (1)$ 時間複雜度，頭部插入無需遍歷鏈結串列，這在核心的高頻操作（如緩存更新）中至關重要。尾部插入需要
  $O (n)$ 時間，與核心效率目標不符。
- 清理 (map_deinit)：釋放雜湊表資源。
  透過雙重 for 迴圈，使用 p 作為遍歷指標，但不直接在迴圈條件中更新，而是透過 p = p->next 手動前進，這是因為節點會在迴圈內被移除，必須先保存下一個節點的位置，然後將 hlist_node 轉換為包含它的 hash_key 結構，以便訪問 key 和 data。
  - if (!n->pprev) goto bail：
    檢查節點是否正確鏈結。pprev 若為 NULL，表示節點未被插入鏈結串列（可能是未初始化或已被移除），直接跳到釋放記憶體，避免後續操作引發錯誤。
  - 節點移除：
    先保存下一個節點（next）和前一指標的位址（pprev）。接著更新前一指標（可能是 head->first 或前一節點的 next）指向下一個節點，完成鏈結串列的斷開。
    若下一個節點存在，更新其 pprev 指向前一指標，保持雙向鏈結的完整性。否則，清空當前節點的指標，標記其已脫離鏈結串列。
  - 記憶體釋放：
    bail: 標籤後，free(kn->data) 釋放值記憶體，free(kn) 釋放節點本身。
  下圖以移除桶 1 的第一個節點（key=1）為例，假設初始有 1 和 5：
  - 移除前：
  - 移除中（*pprev = next 後）：
  - 移除後（更新 next->pprev 和清空節點）：
  為什麼檢查 n->pprev？
  可能是為了防範異常情況（如節點未正確鏈結），如果直接操作 NULL 的 pprev，可能導致記憶體錯誤。開發者注重穩定性，確保即使資料結構狀態異常也能安全清理。
使用 hash table 的 twoSum 應用
利用雜湊表的 O(1) 查找，將「找兩個數」的問題轉化為「找一個數」的查詢。

初始化一個雜湊表（bits=10，1024 個桶），並分配結果陣列 ret。
遍歷陣列 nums，對於每個元素 nums[i]：
1. 計算所需補數 target - nums[i]。
2. 用 map_get 查詢補數是否已在雜湊表中：
  - 若找到，p 指向補數的索引，設置 ret[0]=i, ret[1]=*p，並結束。
  - 若未找到，分配一個整數記憶體，儲存當前索引 i，並將 (nums[i], i) 加入雜湊表。

無論是否找到解，最後清理雜湊表並返回結果。

以 nums=[2,7,11,15], target=9 為例：

初始狀態：雜湊表為空。

i=0, nums[0]=2：
查詢 9-2=7，未找到。
插入 (2, 0) 到桶 hash(2, 2)=2

i=1, nums[1]=7：
查詢 9-7=2，找到 (2, 0)。
返回 [1, 0]，結束。

接著，以下驗證程式碼：
分為兩部分：首先驗證雜湊表的基本功能（map_init、map_add、map_get、map_deinit），然後測試 twoSum 的正確性。程式碼使用簡單的 printf 輸出結果，並包含邊界情況。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 假設 container_of 定義如下（簡化版）
#define container_of(ptr, type, member) ((type *)((char *)(ptr) - (char *)&((type *)0)->member))

// 前述程式碼（hlist_head, hlist_node, map_t, hash_key 等結構和函式）假設已包含

// 測試雜湊表基本功能
void test_hash_table() {
    printf("Testing hash table basic operations...\n");

    // 初始化雜湊表，bits=3 表示 8 個桶
    map_t *map = map_init(3);
    if (!map) {
        printf("map_init failed\n");
        return;
    }

    // 插入鍵值對
    char *data1 = "one";
    char *data2 = "nine"; // hash(1, 3) 和 hash(9, 3) 可能衝突
    map_add(map, 1, data1);
    map_add(map, 9, data2);

    // 查詢並驗證
    char *result1 = map_get(map, 1);
    char *result2 = map_get(map, 9);
    char *result3 = map_get(map, 5); // 未插入的鍵
    printf("map_get(1) = %s (expected: one)\n", result1 ? result1 : "NULL");
    printf("map_get(9) = %s (expected: nine)\n", result2 ? result2 : "NULL");
    printf("map_get(5) = %s (expected: NULL)\n", result3 ? result3 : "NULL");
    assert(result1 == data1);
    assert(result2 == data2);
    assert(result3 == NULL);

    // 清理
    map_deinit(map);
    printf("Hash table test passed.\n\n");
}

// 測試 twoSum
void test_two_sum() {
    printf("Testing twoSum...\n");

    // 測試案例 1：經典範例
    int nums1[] = {2, 7, 11, 15};
    int target1 = 9;
    int returnSize1;
    int *result1 = twoSum(nums1, 4, target1, &returnSize1);
    if (result1 && returnSize1 == 2) {
        printf("twoSum([2,7,11,15], 9) = [%d, %d] (expected: [1, 0])\n", 
               result1[0], result1[1]);
        assert(result1[0] == 1 && result1[1] == 0);
        free(result1);
    } else {
        printf("twoSum failed for target=9\n");
    }

    // 測試案例 2：有衝突的情況
    int nums2[] = {3, 3};
    int target2 = 6;
    int returnSize2;
    int *result2 = twoSum(nums2, 2, target2, &returnSize2);
    if (result2 && returnSize2 == 2) {
        printf("twoSum([3,3], 6) = [%d, %d] (expected: [1, 0])\n", 
               result2[0], result2[1]);
        assert(result2[0] == 1 && result2[1] == 0);
        free(result2);
    } else {
        printf("twoSum failed for target=6\n");
    }

    // 測試案例 3：無解的情況
    int nums3[] = {1, 2, 3, 4};
    int target3 = 10;
    int returnSize3;
    int *result3 = twoSum(nums3, 4, target3, &returnSize3);
    if (result3 && returnSize3 == 0) {
        printf("twoSum([1,2,3,4], 10) = no solution (expected: empty)\n");
        free(result retournSize3);
    } else {
        printf("twoSum failed for target=10\n");
    }

    printf("twoSum test passed.\n");
}

int main() {
    test_hash_table();
    test_two_sum();
    return 0;
}

運作原理：
- test_hash_table：
  - 初始化一個 bits=3（8 個桶）的雜湊表。
  - 插入鍵 1 和 9（可能映射到同一桶，測試衝突處理）。
  - 查詢存在的鍵（1 和 9）和不存在的鍵（5），驗證結果。
  - 清理雜湊表，確保無記憶體洩漏。
- test_two_sum：
  - 案例 1：經典輸入 [2,7,11,15], target=9，預期返回 [1,0]。
  - 案例 2：相同元素 [3,3], target=6，測試衝突下的正確性，預期 [1,0]。
  - 案例 3：無解情況 [1,2,3,4], target=10，預期返回空結果（returnSize=0）。
  - 使用 assert 驗證結果，並印出過程。

預期輸出：

Testing hash table basic operations...
map_get(1) = one (expected: one)
map_get(9) = nine (expected: nine)
map_get(5) = NULL (expected: NULL)
Hash table test passed.

Testing twoSum...
twoSum([2,7,11,15], 9) = [1, 0] (expected: [1, 0])
twoSum([3,3], 6) = [1, 0] (expected: [1, 0])
twoSum([1,2,3,4], 10) = no solution (expected: empty)
twoSum test passed.

進行《The Art of Computer Programming》(vol 3) 一書section 6.4 的 exercise 8，也就是證明 Theorem S

注意: Linux 核心內部大量使用 hash table，但並非每處的雜湊函數都滿足減少碰撞及避免 clustering 現象的原則，也就是存在若干改進空間
todo
探討 Linux 核心中使用 hash table 的應用案例，至少二項，應當列出原始程式碼並分析，斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素

2025q1 Homework2 (quiz1+2)

第一周測驗一

解釋上方程式碼運作原理

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

第一週測驗二

解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

第一週測驗三

解釋上述程式碼運作原理

研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

第二週測驗一

解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting

將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋

第二週測驗二

解釋上述程式碼，並探討擴充為 ⌈x⌉ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作

參照計算機結構測驗題 C 及其注釋，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格。對照 sqrtf, rsqrt, reciprocal implementations in Arm assembly

參照從 √2 的存在談開平方根的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能

第二週測驗三

解釋上述程式碼運作原理，應提供測試程式碼

進行《The Art of Computer Programming》(vol 3) 一書section 6.4 的 exercise 8，也就是證明 Theorem S

探討 Linux 核心中使用 hash table 的應用案例，至少二項，應當列出原始程式碼並分析，斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素

Read more

2025q1 Homework1 (lab0)

2025q1 Homework1 (ideas)

解釋上述程式碼，並探討擴充為
$⌈ \sqrt{x} ⌉$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作