2025q1 Homework2 (quiz1+2)

contributed by < wurrrrrrrrrr >

第一週測驗題

測驗一
一開始先提到以下程式碼運用 "a pointer to a pointer" 技巧，於是我開始思考什麼叫做 "a pointer to a pointer"，於是我先閱讀了你所不知道的 C 語言: linked list 和非連續記憶體了解到間接指標的技巧，可以避免動態記憶體配置同時我也看了Linux 核心的 hash table 實作得知了間接指標也能用來消除特例使得程式碼更為優雅，比如說在上述文章中的例子：
探討針對典型雙向鏈結串列進行節點移去時，會產生的問題我們先使用典型的 doubly-linked list:

struct dll_node { 
    struct dll_node *next, *prev;
}

由此結構產生出的圖為下列：

如果以上面的結構在嘗試撰寫delete_node()的話會需要考慮特例的出現，也就是當要移除第一個節點時，必須做出額外的操作來更新list_head指向的節點，於是除了移除的目標之外還必須傳入list_head。

如果我們換一個寫法用指標的指標改寫上述程式碼，將原本的struct dll_node *prev 變更為 struct dll_node **pprev ：

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

則會形成以下的結構：

這件事就是之前 Linus Torvalds 的解說有時候你可以用不同的方式來看待一個問題，並重新改寫它，使得特殊情況消失，變成一般情況。

It does not have the if statement. And it doesn't really matter – I don't want you understand why it doesn't have the if statement, but I want you to understand that sometimes you can see a problem in a different way and rewrite it so that a special case goes away and becomes the normal case. And that's good code. But this is simple code. This is CS 101. This is not important – although, details are important.

程式運作原理

本次的測驗題首先題目先定義了以下兩個結構：

此為 list_t

此為 list_item_t

在解答這題之前，我們首先需要了解程式的運行流程。程式的執行從主程式開始，而第一步則是呼叫 test_suite() 這個函式。

    char *result = test_suite();

而 test_suite() 這個函式會進一步呼叫一個巨集 my_run_test() 來執行測試。最後，如果 test_suite() 執行成功，則會回傳 NULL 值。

    my_run_test(test_list);
    return NULL;

接下來，my_run_test() 這個巨集的輸入是一個函式，在此題中，輸入的函式為 test_list()。

在 my_run_test() 所生成的程式碼中，可以看到它使用了一個 do while 迴圈，這表示無論如何，do while 迴圈內的程式碼都至少會執行一次，即使條件最終不成立，迴圈內的程式仍然會被執行一次後才進行條件判斷，而 while 中輸入的值為 0 因此只會執行一次。

在 do while 迴圈內的開頭，會先呼叫輸入的函式，在本題中該函式為 test_list()。

test_list() 這個函式的主要作用是測試 list_insert_before() 是否正確運作，並透過 my_assert() 驗證結果是否符合預期。

test_list() 主要測試以下功能：

透過 list_insert_before(&l, l.head, &items[i]) 不斷將新元素插入到頭部，並檢查最終串列順序是否為逆序排列。
透過 list_insert_before(&l, NULL, &items[i]) 不斷將新元素插入在尾部，並檢查最終串列順序是否為正序排列。
最後重置串列，並按照順序插入元素。

首先，test_list() 會先呼叫 list_reset() 這個函式，而在解釋 list_reset() 的作用之前，我們需要先了解題目中所宣告的變數，因為這些變數會影響 list_reset() 的行為。

題目所宣告的變數：

static list_item_t items[N];
static list_t l;

而這當中的 N 在題目的巨集有定義：

#define N 1000

都了解後就能來看 list_reset() 這個函式的作用，這個函式的作用是重置鏈結串列 l 並初始化 items 陣列，確保每次測試都從頭開始，避免舊數據影響測試結果。

    for (size_t i = 0; i < N; i++) {
        items[i].value = i;
        items[i].next = NULL;
    }
    l.head = NULL;

再來程式會執行一個叫做 my_assert() 的巨集，此巨集的作用類似於 assert()，用來確保測試條件成立，否則會返回錯誤訊息。

7.2.1.1 The assert macro

if expression (which shall have a scalar type) is false (that is,compares equal to 0), the assert macro writes information about the particular call that failed (including the text of the argument, the name of the source file, the source line number, and the name of the enclosing function — the latter are respectively the values of the preprocessing macros _ FILE _ and _ LINE _ and of the identifier _ func _) on the standard error stream in an implementation-defined format.159) It then calls the abort function.

my_assert() 的第一個測試是檢查 list_size() 是否為 0。

如果 list_size(&l) != 0，則測試會立即報錯並終止執行。
如果測試通過，程式會繼續執行 list_insert_before(&l, l.head, &items[i])，將新元素不斷插入到串列的頭部。當插入 N 次後，程式會再度使用 my_assert() 驗證串列的大小是否為 N，確保所有元素都成功插入。最後，若所有測試皆通過，則進一步檢查 items.value，確認串列中的元素順序是否符合預期。

而第二個測試也是類似於第一個測試，程式會繼續執行 list_insert_before(&l, NULL, &items[i])，將新元素不斷插入到串列的尾部若，所有測試皆通過，則進一步檢查 items.value，確認串列中的元素順序是否符合預期。

最後一個測試與第二個測試執行的操作相同，此操作的目的為依照順序重置串列以確保串列能夠正確維護順序。

如果上述測試中的任何一個條件未通過，則會回傳對應的錯誤訊息給char *message並終止測試；反之，若所有測試皆通過，則回傳 NULL 值給 char *message，表示測試成功且未發現錯誤。

最後執行：

if (message)           
    return message;

如果有錯誤訊息就回傳錯誤訊息反之回傳 NULL 值。

當回傳後會回到主程式執行去檢查該回傳值假如為 NULL 會執行下列這行：

printf("ALL TESTS PASSED\n");

反之回報錯誤訊息:

printf("ERROR: %s\n", result);

最後執行:

printf("Tests run: %d\n", tests_run);

在知道上述流程後就可以開始填寫題目當中的 list_insert_before 函式。

題目中，list_insert_before 函式的輸入包含以下幾個部分：

list_t 的地址（即串列的目標位置）
插入位置（指定要插入的節點位置）
要插入的元素（即新節點）。

這些參數都與以下的結構有關：

{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

他先定義了一個指向 list_item_t 結構的指標的指標叫做 p，這個 p 指標會指向另一個指向 list_item_t 結構的指標

在定義完 list_item_t **p 之後，接著出現了一個迴圈，因此可以推測 p 是用來尋找要插入的位置的指標。

由於在前面的測試中已經確認 list_size(&l) != 0，如果串列為空（list_size(&l) == 0），則測試會直接回報錯誤並終止。因此，在這裡我們可以安全地將 p 設為 &l->head，即指向頭節點指標的位置。

那為什麼 p 設為 &l->head，而不是 &l.head？
l 是list_t型別的變數，而 l.head 是指向list_item_t的指標（list_item_t *）。
&l.head 表示取得 head 指標的地址，這樣 p 變數可以指向 head，並在迴圈中更新它的值。

關鍵點是在從函式的呼叫方式可以看到 list_insert_before() 接收的是 &l（即 list_t *），因此在函式內部應該用 list->head 來操作串列的頭部，而 &list->head 則是指向頭節點指標的位址，適合用來尋找插入位置。

決定好 p 的初始位置後，接下來需要設置迴圈的中斷條件，即找到 before 這個節點，因為 before 代表的是我們要插入的節點之後的元素。

在題目說明中，before 變數表示插入位置的後一個元素，因此我們在迴圈中遍歷串列也就是p = &(*p)->next，直到找到 *p == before，這樣 p 就會指向 before 前一個節點的 next 指標。

當找好 p 之後就要插入 item 因此可以看到下列這行：

*p = item;

也就是把指向 before 前一個節點的 next 指標指向 item ，看起來像這樣：
(假設 item 為 value 為 1 的話且 before 為 NULL )

再來執行下列這行：

item->next = before;

就是將item的 next 接在原來 *p->next 所指的也就是 before 上：

撰寫合併排序操作

merge sort 有三種實作方式：

top-down mergesort
bottom-up mergesort
queue-mergesort

Top-down mergesort

有最少的 average case、worst case 的 comparison 次數。
需要使用遞迴或是額外空間作為 user stack。
需要事先知道整個 list 的大小。

Bottom-up mergesort

此種需要最多的 comparison 次數。

Queue-mergesort

特別適合用於鏈結串列的排序。
queue-mergesort comparison 的次數少於 bottom-up mergesort，略高於 top-down mergesort。
可以以 top-down 或是 bottom-up 的方式實作。
透過 get front、put back 操作，因此排序完的結果會是 unstable。

我參考了 Linked List Sort 且採用第一種 Top-down mergesort ：

q_sort
ㄧ開始我先為排序提供一個包裝函式叫做 q_sort，並動態分配一個虛擬節點叫 dummy 節點，之後把 dummy->next 用來指向已經排好的單向鏈結串列：

list_item_t *dummy = malloc(sizeof(list_item_t));
dummy->next = mergeSortList(head);

函式 mergeSortList()
這段是用用快慢指標法：

slow 指標從 head 開始，fast 指標從 head->next 開始。
快指標每次前進兩個節點，慢指標每次前進一個節點。
當 fast 到達串列尾部時，slow 指向串列的中間位置。

透過 slow->next 將串列拆分成兩部分：
第一部分：從 head 到 slow。
第二部分：從 slow->next 到尾部（將 slow->next 設為 NULL 斷開鏈接），之後分別對拆分後的兩個子串列遞迴呼叫 mergeSortList() 進行排序，得到兩個已排序的串列 l1 與 l2 ，最後呼叫 merge(l1, l2) 函式，將兩個排序好的子串列合併成一個最終有序的串列並返回。

函式 merge()
在這個函式中先宣告一個局部變數 dummy ，並將 dummy.next 初始化為 NULL，之後定義一個指標 temp 指向 dummy，這個指標是用來創建合併後的新串列，方便後續操作，而且不需要特別處理新串列的首個節點。

    list_item_t dummy;
    dummy.next = NULL;
    list_item_t *temp = &dummy;

之後進到合併迴圈每次比較 l1 和 l2 當前節點 value 的值：
如果 l1->value 小於或等於 l2->value，就把 temp->next 指向 l1，並讓 l1 等於 l1->next；否則，將 temp->next 指向 l2，並讓 l2 等於 l2->next。

當 while 迴圈結束後，表示至少有一個串列已全部遍歷。我們將未遍歷完的串列（l1 或 l2）的剩餘部分直接連接到新串列的尾部，因為傳入 merge 函式的串列皆已排序，因此剩餘部分也必定保持排序。最後返回 dummy.next，即合併後新串列的第一個節點。

當 mergeSortList() 函式全部完成後，我們將結果儲存在 result 中（即 dummy->next），然後釋放 dummy，並返回 result，這樣可以避免浪費記憶體空間。

list_item_t *result = dummy->next;
free(dummy);
return result;

測驗二

程式運作原理

在本題中，我們嘗試撰寫程式碼來管理樹狀結構的記憶體區塊，將所有空閒內存塊（block_t）按照大小組織成一棵二叉搜尋樹，以便在進行內存分配時能夠迅速定位到合適的空閒塊。首先，我們定義了如下的結構：

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

之後定義了兩個輔助函式：
find_free_tree：用於在 free tree 中找到指向 target 節點的指標。
find_predecessor_free_tree：用於查找給定節點的中序前驅節點，這個函數主要是用於驗證找尋的 node_ptr 是否正確（通常是左子樹中最右邊的節點）。

void remove_free_tree(block_t **root, block_t *target)

在 remove_free_tree 函式中通過使用 find_free_tree()這個輔助函式，我們可以從 free tree 中找到指向 target 節點的指標（node_ptr）。
至於這裡為什麼事返回一個指向指標的指標呢？，是因為這樣我們可以直接獲得那個存放目標節點位置的變數的地址，從而直接修改它，也就是直接改變樹中父節點對目標節點的引用。

舉例子下列有一張圖：

如果我今天是使用指標的指標就等於是我能直接操作那個箭頭讓它指向別人：
(例子：把 block1_t 指向 block3_t 的箭頭改為指向 block4_t )

在解釋完上述程式碼後，我們接下來準備移除 *node_ptr 所指向的節點。然而，在真正刪除該節點之前，如果它仍有子節點，我們必須先找到一個合適的替代節點，即中序前驅節點。為此，我們首先需要檢查該節點的左右子樹是否為空，並根據檢查結果決定適當的替換策略。

下列這段程式碼的作用是尋找中序前驅節點。理解其運作方式後，填入相應的邏輯就會變得直觀且容易了。

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

中序前驅節點是左子樹中值最大的節點。為了找到它，我們首先從左子樹開始，然後持續向右搜尋，直至抵達最右側的節點。while 迴圈的作用正是遍歷左子樹的最右側，因為該位置的節點擁有左子樹中的最大值，即我們要找的中序前驅節點。

因此，EEEE 的條件應該是當 pred_ptr 的右子樹不為空時，迴圈便會持續執行。換句話說，程式會不斷向右移動，以找到左子樹中值最大的節點。因此，我們填入 (*pred_ptr)->r 作為判斷條件。

而 FFFF 的部分則表示我們需要不斷向右子樹移動，以找到左子樹中值最大的節點。因此，我們應填入 &(*pred_ptr)->r，讓 pred_ptr 指向其當前節點的右子節點，直到遍歷到最右側的節點為止。

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

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

參考 memory-allocators，可以得知 allocators 分為以下四種：

1. Linear Allocator:

這是最簡單的分配器類型。其概念是保持一個指針指向 memory 區塊的第一個 memory 地址，並在每次分配時移動該指針。
Free
由於其簡單，所以這種分配器不允許釋放特定位置的 memory。通常，所有 memory 會一起被釋放。

2. Stack Allocator:

這是 Linear Allocator 的一個進化。其概念是將 memory 管理像堆疊一樣運作（LIFO—後進先出）。
我們保持一個指針指向當前的 memory 地址，每次分配時將其向前移動，但是當執行釋放時也可以將指針向後移動。
需要一個指針（或偏移量）來跟踪最後一次分配。為了能夠釋放 memory，還需要為每個分配存儲一個頭部，告訴我們分配 block 的大小。

3. Pool Allocator:

與之前的 Allocator 非常不同。它將大的 memory 區塊拆分成相同大小的小區塊，並跟踪哪些區塊是空閒的。當請求分配時，它返回一個空閒區塊的大小；當釋放操作完成時，它只是將該區塊存儲起來，以便在下次分配時使用。
為了跟踪空閒的 memory 區塊，Pool Allocator 使用鏈表來鏈接每個空閒 memory 區塊的地址。
分配為從鏈表中取出第一個空閒區塊。

釋放操作為將釋放的元素添加為鏈表中的第一個元素。

4. Free list allocator:

這種實現使用鏈表以排序的方式存儲每個空閒連續 memory 塊的起始地址和大小。當請求分配時，它在鏈表中搜索一個可以容納數據的區塊。然後，它將該元素從鏈表中刪除，並在數據前面放置一個分配頭部（用於釋放操作）。當釋放 memory 時，我們通過分配頭部來獲取要釋放的區塊大小。釋放後，我們將該區塊插入到排序過的鏈表中，並嘗試合併相鄰的內存區塊，從而創建更大的區塊。
當請求分配時，我們會查找一個可以容納數據的 memory 區塊。這表示需要遍歷鏈表，直到找到一個大小等於或大於請求大小的區塊，然後將其從鏈表中移除。這種分配方式稱為first-fit allocation ，因為它會在找到第一個可以容納 memory 的區塊後停止。還有另一種叫做 best-fit 的搜索方式，它會尋找能夠容納我們數據的最小空閒區塊。
鏈表釋放:我們一開始會從頭部中獲取有關分配的資訊。接著，我們遍歷鏈表將空閒區塊插入到正確的位置。一旦插入，我們會合併相鄰的區塊。由於鏈表是排序的，我們可以在
$O (1)$ 的時間內合併區塊。我們只需要查看鏈表中的前一個和下一個元素，看看是否可以合併這些相鄰區塊。這種將相鄰 memory 區塊合併為更大區塊的操作稱為 Coalescence。

紅黑樹數據結構
使用紅黑樹的目的是加速分配和釋放操作。在鏈表（或順序）實現中，每次進行操作時都需要遍歷整個鏈表。這在所有情況下的時間複雜度都是

O (N)

。

使用紅黑樹，我們可以將其複雜度降低到

O (l o g N)

，同時保持較低的空間複雜度，因為樹結構的數據存儲在空閒的 memory 區塊中。此外，這種結構還允許使用 best-fit 算法來減少 fragmentation，同時保持良好的性能。然而，為了能夠執行合併操作，我們還需要一個額外的排序雙向鏈表來存儲已分配和空閒的元素，這樣可以將合併操作的時間複雜度維持在

O (1)

。這種實現是最常見且在實際系統中最常使用的，因為它在提供高靈活性的同時，能夠保持非常高的性能。

這是隨機刪除 10 個節點後的紅黑樹：

要進行這項測試，首先，我們需要先確保紅黑樹（Red-Black Tree, RBT）和二元搜尋樹（Binary Search Tree, BST）都實現了 insert 和 delete 操作，並且能夠測量這些操作的性能。之後，我們可以生成 10000 個節點並插入到樹中，然後刪除 5000 個節點，並測量時間和執行所需的 CPU 週期數。
以下是隨機插入和刪除的 cpu cycle (500 - 5000):

可以看到在小樣本和隨機插入和隨機刪除的條件下，二元搜尋樹和紅黑樹之間的效能差距不大。
隨機插入和隨機刪除的情況：儘管紅黑樹在理論上保證了較好的平衡性，但在此條件下，二元搜尋樹的效能可能會更好，甚至有時表現會超過紅黑樹。

我認為這個情況的原因在於刪除的數量太少，未能充分發揮紅黑樹的優勢。紅黑樹的強項在於插入和刪除操作的時間複雜度為

O (\log n)

，因此我增加了刪除操作的數量，同時也考慮了最壞情況的比較。這樣能更好地檢視紅黑樹在不同操作下的表現。

 Performance counter stats for './rbtree' (100 runs):

              2.67 msec task-clock                       #    0.154 CPUs utilized               ( +-  0.18% )
                 0      context-switches                 #    0.000 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
               181      page-faults                      #   67.692 K/sec                       ( +-  0.04% )
        12,244,659      cycles                           #    4.579 GHz                         ( +-  0.16% )
        10,946,123      instructions                     #    0.89  insn per cycle              ( +-  0.06% )
         2,004,065      branches                         #  749.493 M/sec                       ( +-  0.08% )
           134,348      branch-misses                    #    6.70% of all branches             ( +-  0.11% )

           0.01735 +- 0.00274 seconds time elapsed  ( +- 15.77% )

 Performance counter stats for './BST' (100 runs):

              2.76 msec task-clock                       #    0.921 CPUs utilized               ( +-  0.23% )
                 0      context-switches                 #    0.000 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
               152      page-faults                      #   55.019 K/sec                       ( +-  0.04% )
        12,664,378      cycles                           #    4.584 GHz                         ( +-  0.23% )
        12,978,877      instructions                     #    1.02  insn per cycle              ( +-  0.16% )
         2,216,202      branches                         #  802.187 M/sec                       ( +-  0.16% )
           137,921      branch-misses                    #    6.22% of all branches             ( +-  0.34% )

        0.00299926 +- 0.00000914 seconds time elapsed  ( +-  0.30% )

下列為 worse case 比較：

 Performance counter stats for './rbtreewc' (100 runs):

              1.61 msec task-clock                       #    0.870 CPUs utilized               ( +-  0.19% )
                 0      context-switches                 #    0.000 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
               181      page-faults                      #  112.735 K/sec                       ( +-  0.04% )
         7,353,841      cycles                           #    4.580 GHz                         ( +-  0.19% )
        11,081,451      instructions                     #    1.51  insn per cycle              ( +-  0.02% )
         1,867,257      branches                         #    1.163 G/sec                       ( +-  0.02% )
            18,199      branch-misses                    #    0.97% of all branches             ( +-  1.16% )

        0.00184489 +- 0.00000555 seconds time elapsed  ( +-  0.30% )

 Performance counter stats for './BSTwc' (100 runs):

            445.49 msec task-clock                       #    0.999 CPUs utilized               ( +-  0.40% )
                 1      context-switches                 #    2.245 /sec                        ( +- 15.18% )
                 0      cpu-migrations                   #    0.000 /sec                      
               229      page-faults                      #  514.039 /sec                        ( +-  0.03% )
     2,084,878,456      cycles                           #    4.680 GHz                         ( +-  0.40% )
     2,132,337,673      instructions                     #    1.02  insn per cycle              ( +-  0.00% )
       313,761,241      branches                         #  704.304 M/sec                       ( +-  0.00% )
        37,717,711      branch-misses                    #   12.02% of all branches             ( +-  0.00% )

           0.44583 +- 0.00180 seconds time elapsed  ( +-  0.40% )

可以看到在此條件下 rbtree 的效能為 BST 的約 284 倍

這 Commit ed4edff為此次的程式碼。
測驗三

程式運作原理

首先，我們將介紹一種非遞迴（即迭代式）的快速排序方法。假設我們有如下的單向鏈結串列：

在一開始可以看到該排序使用了輔助函式 list_length()來取得整個串列的長度，之後設定 max_level = 2 * n，準備一個大小足夠的陣列用於儲存待排序子串列的起始（begin）和結束（end）指標。
設定 result 和 left 還有 right 用來暫存排序結果與分割後的左、右子串列。
將 begin[0] 設為整個串列的第一個節點（即 *list），並將 end[0] 設為該鏈表的尾部（使用 list_tail(list) 取得）。

node_t *begin[max_level], *end[max_level];

隨後執行下方的程式碼：

    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;

在執行完後原本那個鏈結串列會變成下列這張圖：

下列這段程式碼會根據每個 node_t 的值與 pivot 的比較結果，將大於 pivot 的節點加入 right 串列，而小於或等於 pivot 的節點則加入 left 串列：

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

因此我們可以得知此處的 CCCC = p->next。

下方的 begin 和 end 陣列用於記錄每次切割後不同區域的邊界資訊：

它們分別保存了左側子串列的起始節點與尾端節點、右側子串列的起始節點與尾端節點，還有單獨的 pivot 節點的位置。
DDDD 為 list_tail(left)
EEEE 為 list_tail(right)

而題目是要求使用 Linux 核心風格 List API 的簡化標頭檔 list.h 來改寫快速排序程式碼

首先是結構體：

#include "list.h"

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

也就是下列這張圖：

而當中的 struct list_head 裡面存放兩個指向 struct list_head的指標：

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

因此實際上__node 會是以下的結構體：

首先，題目定義了四個函式，接下來我們逐一說明它們的作用：
函式一：

void list_construct(struct list_head *list, int n)

list_construct() 這個函式的作用為用來建立並初始化一個新節點，然後將它加入到串列中。
函式二：

void list_free(const struct list_head *head)

list_free() 這個函式會遍歷整個串列，並對每一個節點來去呼叫 free()，從而釋放所有動態分配的記憶體資源，防止記憶體洩漏。
函式三：

static bool list_is_ordered(const struct list_head *head)

list_is_ordered() 這個函式會依序檢查串列中每個節點的值，確認這個串列是否是嚴格遞增去排列的，如果都符合則認定串列排序正確。
函式四：

void shuffle(int *array, size_t n)

shuffle() 這段程式碼實作了一個洗牌函式，用來隨機打亂一個整數陣列的元素順序。它是使用了 Fisher-Yates 洗牌演算法，來將陣列中每個位置的元素與其後面某個隨機位置的元素交換。

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

在了解完上述函式之後，我們便可以進入主程式部分，看看整個應用程式是如何運作的。
在主程式一開始，我們首先創建了一個節點，這個節點作為鏈表的頭節點，用來標記整個鏈表的起始位置，隨後執行 INIT_LIST_HEAD（）這個函式來把它初始化，初始化後會看起來為下列這張圖：

首先，我們將節點數量設定為 100000。接著，透過 malloc() 動態分配一段記憶體，足以儲存 100000 個 int 型態的數值，並將返回的指標存入變數 test_arr 中。之後，我們使用迴圈依序將值從 0 填入陣列（即 0, 1, 2, …, count-1）。最後，調用洗牌函式 shuffle()，將陣列中的元素順序隨機打亂。

接下來，程式會在 while 迴圈中逐一將 test_arr 陣列中的元素轉換成節點並插入到串列中，然後執行快速排序，再用 assert 驗證排序結果是否正確，最後釋放所有動態分配的記憶體並返回 0 結束程式。

而在快速排序中會使用到三個輔助函式：

int list_length(struct list_head *left)

此函式用於計算鏈結串列中包含的節點數量。

struct list_head *list_tail(struct list_head *head)

此函式用於取得鏈結串列的尾端節點，也就是最後一個節點。

static void rebuild_list_link(struct list_head *head)

這個函式的目的是重新建立一個雙向鏈結串列的鏈接關係，使其變為一個循環雙向鏈結串列。

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

可以看出這段程式碼還未完成，因為還需要在最後加入一行程式碼來設定頭節點的 prev 指標指向最後一個節點，因此最後一行要填入 head->prev = prev;。

最後看到快速排序程式碼：

{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    struct list_head *begin[max_level];
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    begin[0] = list->next;
    list->prev->next = NULL;
    while (i >= 0) {
        struct list_head *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
            struct list_head *pivot = L;
            value = /* HHHH */
            struct list_head *p = pivot->next;
            pivot->next = NULL; /* break the list */

            while (p) {
                struct list_head *n = p;
                p = p->next;
                int n_value = /* IIII */;
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

            begin[i] = left;
            begin[i + 1] = /* JJJJ */;
            begin[i + 2] = /* KKKK */;
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }
    }
    list->next = result;
    rebuild_list_link(list);
}

根據前面介紹的快速排序，我們知道必須先選取一個 pivot。下列程式碼展示了如何找出 pivot 節點，並在找到後提取該節點的 value。由於我們需要從 pivot 節點中取得對應結構的資料，因此在填入該節點的 value 時，我們必須先了解 container_of 這個巨集的用法，藉以從節點指標中還原出整個結構。

#define list_entry(node, type, member) container_of(node, type, member)

了解後我們可以得知，應該填入的內容分別為：

list_entry(pivot, node_t, list)->value

list_entry(n, node_t, list)->value

而接下來的 begin 則是要紀錄左串列的第一個節點和右串列的第一個節點還有 pivot 節點，因此要填入 JJJJ = pivot 跟 KKKK = right 。

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

這篇論文〈A comparative study of linked list sorting algorithms〉主要探討了多種用於鏈表排序的演算法，並針對它們在不同資料規模下的表現進行了比較。

雙向鏈表排序

Sediment Sort：

這其實是一種泡沫排序（Bubble Sort）的變種。文中指出，雖然它在某些文獻中被宣稱是高效的，但實際上僅是對傳統泡沫排序的一個小變化，而且在效率上可能是最慢的，因為它需要進行大量不必要的節點交換，這個演算法的複雜度是
$O (n ²)$ 。

Tree Sort：

利用雙向鏈表中節點的兩個指標（前驅與後繼）來構造一棵二元搜尋樹，再通過中序遍歷將樹轉換成排序好的鏈表。這種方法在資料隨機時能夠保持較好的平衡性，理論上複雜度接近
$O (n l o g n)$ 。

單向鏈表排序
該論文也介紹了適用於單向鏈表的排序方法，包含：

Bubble Sort：

每次遍歷時比較相鄰節點並交換。

Selection Sort：

每次找到最小（或最大）元素，然後將其放到適當位置，只進行 n-1 次交換。

Quick Sort：

這裡討論的是一個穩定版本的快速排序，通過將鏈表劃分為小於、等於及大於樞紐值的三個部分，然後遞歸排序。

Merge Sort（合併排序）：

利用鏈表特性進行兩路分割，再合併排序好的子鏈表，特別適合順序存取的資料結構。

在看完上述論文後我先實做了具 Linux 核心風格的 List API 的insertion sort ：

void insertion_sort(struct list_head *head) {
    element_t *tp_node, *node;
    struct list_head ans;  
    struct list_head *temp, *pos, *ans_pos;

    INIT_LIST_HEAD(&ans);  


    list_for_each_safe(pos, temp, head) {
        tp_node = list_entry(pos, element_t, list); 
        list_del(pos); 


        ans_pos = ans.next;
        while (ans_pos != &ans && strcmp(tp_node->value, list_entry(ans_pos, element_t, list)->value) > 0) {
            ans_pos = ans_pos->next;
        }

        list_add(&tp_node->list, ans_pos->prev);
    }

    INIT_LIST_HEAD(head);
    list_for_each_safe(pos, temp, &ans) {
        node = list_entry(pos, element_t, list);
        list_add_tail(&node->list, head);
    }
}

接下來，我將根據本論文中提到的 Tree Sort 算法，實現以下流程圖來描述其工作原理。

一開始要先根據輸入的資料建構一個二元搜尋樹，假設建構完為下列這張圖:

建構完後我們首先建立頭節點:

建構完頭節點我們開始執行中序探訪，並將中序探訪的節點使用list_move_tail依序加入頭節點:

以上為 Tree Sort 的流程。

在本研究中，我們成功實作了 Sediment Sort，並以實際測試的方式比較了上述三種排序演算法的效能。我們採用 CPU cycles 作為效能度量指標，對不同資料規模下的運行效率進行了嚴謹測試。

 sudo perf stat --repeat 100 ./

從圖中可以看出三種排序演算法（insertion_sort、sediment_sort、tree_sort）在不同輸入規模下所花費的 CPU cycles隨著樣本數量成長的趨勢：

Sediment Sort（紅色方塊虛線）

隨著樣本數量增加，曲線迅速飆升，顯示其時間複雜度最高。
在 1 萬筆資料時，CPU cycles 高達約
$5 \times 10^{9}$ ，遠高於其他演算法。
證實它在大規模資料下效率偏低。

Insertion Sort（藍色圓點實線）

雖然也呈現明顯的成長，但相較於 Sediment Sort，增長速度較為平緩。
在 1 萬筆資料時約
$1 \times 10^{9}$ 出頭，比 Sediment Sort 小很多。
仍屬於
$O (n^{2})$ 演算法，但常數因子較小，使其在實測中優於 Sediment Sort。

Tree Sort（橘色三角形折線）

全程維持在相對較低的 CPU cycles 水平，顯示演算法效率最高。
在 1 萬筆資料時仍相對平緩，呈現近似
$O (n l o g n)$ 的特性。
適用於大部分情況下的排序需求，對大量樣本非常的有效。

tree_sort 的實做 Commit 91aeec6
insertion sort 的實做 Commit 6355a0b
Sediment Sort 的實做 Commit 7e959b6

第二週測驗題

測驗一

程式運作原理

首先題目定義了一個結構叫listitem他的結構會為下列這張圖( 已做完 INIT_LIST_HEAD )：

struct listitem {
    uint16_t i;
    struct list_head list;
};

再來它定義了一個比較用的函式和一些輔助函式：

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;

    return *i1 - *i2;
}

陣列大小計算：
使用 macro #define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0])) 來計算陣列中元素的個數。

隨機數生成：

getnum() 函數：
利用三個靜態變數（s1、s2、s3），各自根據不同的乘數與 modulus 更新，並將三者進行xor 去得到一個 8 位元的隨機數。

static inline uint8_t getnum(void)

get_unsigned16() 函數：
透過兩次呼叫 getnum()，並將兩個 8 位元的數值合併成一個 16 位元的數值。這樣做是為了得到更大範圍的隨機數。

陣列隨機洗牌：

random_shuffle_array() 函數：
該函數針對給定的 operations 陣列進行洗牌。對於每個索引 i，它產生一個介於 0 到 i（包含 i）的隨機索引 j，然後將 operations[i] 設為 operations[j]，並將 operations[j] 更新為 i

可以將此亂數函式替換為 Fisher–Yates shuffle

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

此為 Fisher–Yates shuffle 的亂度測試結果。

在測試程式部分，首先定義了一個struct list_head節點，命名為 testlist，作為鏈結串列的頭節點。接著，程式宣告了兩個指向 listitem 結構的指標，分別命名為item與 is，這兩個指標主要用於後續遍歷和操作鏈結串列中的節點。最後，定義了一個變數 i，通常用作迴圈的計數器，以便在插入或比對過程中追蹤當前的索引或元素數量。

    struct list_head testlist;
    struct listitem *item, *is = NULL;
    size_t i;

隨後，程式首先呼叫random_shuffle_array對全域陣列values進行亂序操作，這步驟確保後續插入到鏈結串列中的資料順序是隨機的，從而能夠更好地測試排序函式的效能與正確性。接著，程式透過INIT_LIST_HEAD(&testlist)初始化鏈結串列的頭節點 testlist，使其處於空鏈結串列的狀態，並在後續透過檢查確保該鏈結串列在初始化後確實為空。

    random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));

    INIT_LIST_HEAD(&testlist);

    assert(list_empty(&testlist));

接下來下列程式碼透過一個 for 迴圈遍歷陣列 values 中的每一個元素，並將每個元素包裝成一個動態分配的節點，然後依序加入到鏈結串列testlist的尾端。每次迴圈中，它先透過 malloc 為新的節點分配記憶體，接著使用 assert 確保記憶體分配成功，然後將當前陣列元素的值存入該節點的資料欄位（例如 i），最後利用list_add_tail函數將這個節點連接到鏈結串列的尾部:

    for (i = 0; i < ARRAY_SIZE(values); i++) {
        item = (struct listitem *) malloc(sizeof(*item));
        assert(item);
        item->i = values[i];
        list_add_tail(&item->list, &testlist);
    }

再來我們利用標準庫中的 qsort 函式對 values 陣列進行排序，目的是為了作為參考結果。之後，透過比較 qsort 排序後的陣列與我們自行實作的list_quicksort排序後的鏈結串列，可以驗證自訂排序演算法的正確性。

    qsort(values, ARRAY_SIZE(values), sizeof(values[0]), cmpint);
    list_quicksort(&testlist);

    i = 0;
    list_for_each_entry_safe (item, is, &testlist, list) {
        assert(item->i == values[i]);
        list_del(&item->list);
        free(item);
        i++;
    }

而這個list_for_each_entry_safe實做方式如下圖：

再來看到 list_quicksort，相較於尋常的快速排序程式碼，我們希望排序結果是符合 stable sorting
由快速排序可以推敲出他的運作流程為以下示意圖 (此為要排序的鏈結串列):

首先可以看到，程式宣告了兩個struct list_head 變數，分別命名為list_less和list_greater這兩個變數用於儲存分割後的鏈結串列節點，分別代表小於 pivot 的節點群與大於該 pivot 的節點群，再來分別對這兩個變數作初始化讓他們的 next 和 prev 指標都指向自己：

再來程式從原始鏈結串列中選取第一個節點，並將其指定為排序過程中的 pivot。接著，程式會將這個 pivot 從鏈結串列中分離，這樣在後續的比較與分割操作中，就不會再次處理該節點。

    pivot = AAAA(head, struct listitem, list);
    BBBB(&pivot->list);

因此此處的 AAAA = list_first_entry 和 BBBB = list_del。

下列這段程式碼會對每個節點，其資料欄位 i 會與 pivot 節點的 i 進行比較。如果比較結果顯示該節點的數值小於 pivot 的數值，則會使用list_move_tail將此節點移到 list_less 鏈結串列的尾部；否則，則會透過 CCCC 的方式，將該節點放入 list_greater 鏈結串列中，因為本題是要stable所以 CCCC =list_move_tail而不是list_move。

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            CCCC(&item->list, &list_greater);
    }

下列為使用list_move的範例來說明為什麼不是stable( 8_1 為第一個 8 ，8_2 為第二個 8 )：

下列為執行完後的示意圖：

在原始串列中，8_1 位於第一個位置，但在執行一次分割迴圈後，它被移動到了第二個位置也就是 8_2 的後面，因此假如是list_move不保證stable。

如果是list_move_tail則會是下列這張圖可以看到為stable ：

在執行完迴圈後，程式將原始的鏈結串列分割為兩個子串列以及一個 pivot 。接著，透過遞迴地呼叫 list_quicksort，分別對這兩個子串列進行排序，從而達到整體排序的目的。

    list_quicksort(&list_less);
    list_quicksort(&list_greater);

最後，當兩個遞迴呼叫的排序操作都完成後，程式會依序將 pivot 節點以及兩個排序好的子串列整合回原始鏈結串列中。具體而言，透過呼叫

DDDD(&pivot->list, head) 將 pivot 節點加入主串列，
EEEE(&list_less, head) 將排序後的左側子串列合併到主串列，
FFFF(&list_greater, head) 將排序後的右側子串列併入主串列，從而完成整體的排序過程。

下列為流程圖：

首先把 pivot 放到 head 節點的後面( DDDD = list_add )，再把將排序後的左側子串列合併到主串列 ( EEEE = list_splice )：

最後將排序後的右側子串列併入主串列，從而完成整體的排序過程 ( FFFF = list_splice_tail )。

已將上述程式碼整合進 lab0 Commit 2733963

將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能

以下為測試不同的排序演算法結果：

測試資料為一半排序好的資料另一半為 rand() 隨機插入的測試資料，可以看到list_quicksort的速度為最慢的，我認為造成這個現象的主因在於 list_quicksort 內部不僅遞迴深度高，還頻繁呼叫多個鏈結串列操作函式（例如 list_move_tail 、list_splice 等），導致大量的函式呼叫開銷累積，進而拖慢整體執行速度。

在這組測試裡，我們把所有輸入資料都改成完全隨機（rand() 產生），結果所有排序演算法的執行時間都顯著上升。但值得注意的是，Timsort 的表現與其它演算法略有不同——在這種純隨機資料下，Timsort 反而比 Bottom‑Up Merge Sort 和 Top‑Down Merge Sort 慢；而基於鏈表的 Quick Sort（list_quicksort）依然是所有方案中最慢的。

TODO 嘗試改善 list_quicksort 的執行效率

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

測驗二
首先要看到 clz2 函式，其作用是藉由遞迴呼叫以計算 count leading zero (clz)。每次呼叫 clz2() 函式時，代表將目前關注的位元（bits）「切成一半」，以檢查 leading zero 的數量。
Step 1
將數值等分為兩部分：較高位（upper）與較低位（lower）。
Step 2
此時，依據 upper 的數值判斷下一次遞迴呼叫應該處理哪一部分，以累計 leading zero 的數量。

若 upper 等於 0，則下一次遞迴呼叫應檢查 lower 部分，並用計數器（counter）記錄目前已累計的 leading zero（等於 upper 位元數）。
若 upper 不等於 0，則下一次遞迴呼叫應繼續檢查 upper 部分。

Step 3
遞迴呼叫 clz2() 函式，直到僅剩 2 位元（bits）需要檢查 leading zero，然後回傳結果。

參考執行輸出:

輸入: 0x00000F00，其 clz32 為 20
輸入: 0x00000001，其 clz32 為 31

首先我們看到下列巨集：

#define clz32(x) clz2(x, 0)

由這個巨集的設定可以看出，在 clz2 函式的初始呼叫中，參數 c 被設置為 0。
接下來，我們來分析以下這段程式碼:

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

首先看到第一個判斷式，若 x == 0 且 c == 0，表示輸入的 x 是 0，在 32 位元表示中，全部都是零，因此返回 32。

再來拆分 x 成「高 16 位」和「低 16 位」

upper：代表 x 的高 16 位（或者高 8 位、高 4 位，依 c 變化）。
lower：代表 x 的低 16 位（或更小的區間）。

lower 的部分負責逐步縮小關注的位元範圍，透過將數值的前半部清零，逐步保留越來越小的區段。起初，它會保留 x 的後 16 位元，接著縮減範圍至 8 位元、再到 4 位元，最後僅剩 2 位元，確保遞迴過程能夠精確計算 leading zero 的數量，因此 GGGG ＝ 14。

再來看到這個判斷式：

if (c == JJJJ)

根據下列程式碼，可以推斷這個判斷式的作用是用來回傳 leading zero 的數量，因此它作為遞迴的中止條件。該程式的中止條件是在遞迴過程中，當剩下的位元數縮小到僅剩 2 位元時，則不再繼續遞迴，而是直接回傳計算結果，因此可以得知 JJJJ ＝ 3。( 16 位元時 c = 0 ，8 位元時 c = 1 ，4 位元時 c = 2，2 位元時 c = 3 )
再來看到下列這行：

return upper ? magic[upper] : KKKK + magic[lower];

當 upper == 0 時，程式會執行 KKKK + magic[lower] 分支；由於遞迴結束時 upper 一定為 0，可推得 KKKK = 2。
反之，若 upper != 0，則會直接執行 magic[upper] 分支——這說明 magic[] 陣列儲存的正是「（ leading zero ）的數量」。因此可進一步確定 magic 陣列中對應最高區段的值 HHHH = 2，以及最低區段的值 IIII = 0。

看到最後一行：

return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);

當 upper != 0（高位部分不全為 0）時
直接遞迴呼叫 clz2(upper, c + 1)，表示 leading zero 尚未結束，要繼續在更高一半的位元區段中尋找。

當 upper == 0（高位部分全為 0）時
首先累加 (16 >> c)，代表這一輪高半區段全部都是 leading zero 的位數；
然後遞迴呼叫 clz2(lower, c + LLLL)，將焦點轉到剩下的低半區段繼續計算 leading zero。

這樣的設計能夠「跳過」整個已確定為零的區塊，直接累計對應的零位數，再往更小範圍遞迴，直到最終只剩 2 位元為止。

LLLL ＝ 1

當時做好上述函式後可運用該函式建構 64 位元的版本：

static inline int clz64(uint64_t x)
{
    /* If the high 32 bits are nonzero, count within them.
     * Otherwise, count in the low 32 bits and add 32.
     */
    return (x >> 32) ? clz32((uint32_t) (x >> 32)) : clz32((uint32_t) x) + 32;
}

看了2025-02-25 問答簡記得知了他的實做手段，在解釋之前必須了解幾個特定的符號:
首先看到三元平方和為下列公式:

\begin{aligned} (a + b + c)^{2} & = ((a + b) + c)^{2} \\ = (a + b)^{2} + (a + b) c + c (a + b) + c^{2} \\ = (a + b)^{2} + (2 (a + b) + c) c \\ = a^{2} + (2 a + b) b + (2 (a + b) + c) c \end{aligned}

四元平方和為下列公式:

\begin{aligned} (a + b + c + d)^{2} & = ((a + b + c) + d)^{2} \\ = (a + b + c)^{2} + (a + b + c) d + d (a + b + c) + d^{2} \\ = (a + b + c)^{2} + (2 (a + b + c) + d) d \\ = a^{2} + (2 a + b) b + (2 (a + b) + c) c + (2 (a + b + c) + d) d \end{aligned}

觀察規律可以發現

m

元平方和可以藉由

1

到

m - 1

元平方和總和，同時加上一項

Y_{m} = [(2 \sum_{i = m + 1}^{n} a_{i}) + a_{m}] a_{m} = (2 P_{m + 1} + a_{m}) a_{m}

其中

P_{m + 1} = a_{n} + a_{n - 1} + \dots + a_{m + 2} + a_{m + 1}

而

P_{0} = N

且

P_{m} = P_{m + 1} + a_{m}, for 1 \leq m < 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}

由上面的二進制表示我們可以將

Y_{m}

表示為:

Y_{m} = P_{m + 1} 2^{m + 1} + (2^{m})^{2}

令

c_{m} = 2 a_{m} P_{m + 1} = P_{m + 1} 2^{m + 1}

與

d_{m} = a_{m}^{2} = (2^{m})^{2}

。重新將

Y_{m}

表示為

Y_{m} = {\begin{cases} c_{m} + d_{m}, & if a_{m} = 2^{m}, \\ 0, & if a_{m} = 0. \end{cases}

同時藉由

P_{m} = P_{m + 1} + a_{m}

則

\begin{aligned} c_{m} & = P_{m + 1} 2^{m + 1} \\ = (P_{m} - a_{m}) 2^{m} 2 \\ = 2 P_{m} 2^{m} - 2 a_{m} 2^{m} \\ = 2 c_{m - 1} - 2 a_{m} 2^{m} . \end{aligned}

如果

a_{m} \neq 0

則

c_{m - 1} = c_{m} / 2 + d_{m} .

同時

d_{m} = (2^{m})^{2} = (2 \times 2^{m - 1})^{2} = 4 (2^{m - 1})^{2}

則

d_{m - 1} = d_{m} / 4

總結迭代關係為

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_{- 1}

得知平方根為

c_{- 1} = P_{0} 2^{0} = P_{0} = N .

在了解完上述公式後下列這段程式碼簡略來說，就是我有一個輸入叫做

X

這個

X

假設他為

N^{2}

這時假設該數字

N

為 (

a_{n}

a_{n - 1}

+ … +

a 0

)，因此我們要不斷的去減去

Y_{m}

來去把我的

X

值裡的

a_{n}

到

a_{0}

所有不為

0

的減掉

Y_{m}

減掉後

Y_{m}

，之後

Y_{m}

變成

Y_{m - 1}

最後直到最後

c_{m}

等於

c_{- 1}

時即為所求因為

c_{- 1}

為

P_{0}

2^{0}

/**
 * int_sqrt - computes the integer square root
 * @x: integer of which to calculate the sqrt
 *
 * Computes: floor(sqrt(x))
 */
unsigned long int_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (__fls(x) & ~1UL);
    while (m != 0) {
        b = y + m;
        y >>= 1;

        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= 2;
    }

    return y;
}

MMMM 定義為 ~1，即將最低位清零，使得結果向下取整為偶數。
NNNN 定義為 1（即每次 y 右移 1 位）。
PPPP 定義為 2（即每次 m 右移 2 位）。
以下是
$x$ 的平方根
$\sqrt{x}$ 逐位元運算的數學推導。

下列為向上取整的版本，當最後不等於 0 時往上取一位:

    }
    if (m != 0)
        y = y + 1;

    return y;
}

以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格

在看完實作整數開平方根後我再去了解了二進位系統的平方根
令

q_{i} = \sqrt{x}, q_{i}

代表到小數點後面

i

位精確值

i \geq 0

假設

1 \leq x < 4

，於是

\sqrt{x}

的整數位必定是 1，所以

q_{0} = 1

。
考慮

q_{i + 1}

，亦即逐位元逼近:

若
$(q_{i} + 2^{- (i + 1)})^{2} \leq x$ 則
$q_{i + 1} = q_{i} + 2^{- (i + 1)}$
- 即
  $q_{i}$ 下一位補 1
若
$(q_{i} + 2^{- (i + 1)})^{2} > x$ 則
$q_{i + 1} = q_{i}$
- 即
  $q_{i}$ 下一位補 0

整理上面第一種情況

(q_{i} + 2^{- (i + 1)})^{2} \leq x

\begin{aligned} {(q_{i} + 2^{- (i + 1)})}^{2} \leq x & \Rightarrow q_{i}^{2} + 2 \times q_{i} \times (2^{- (i + 1)}) + (2^{- (i + 1)})^{2} \leq x \\ \Rightarrow q_{i} \times (2^{- i}) + 2^{- 2 (i + 1)} \leq x - q_{i}^{2} \\ \Rightarrow q_{i} \times 2 + 2^{- (i + 1)} \leq (x - q_{i}^{2}) \times 2^{(i + 1)} \\ \Rightarrow s_{i} + r_{i} \leq x_{i}, \\ \begin{aligned} w h e r e & s_{i} = 2 \times q_{i}, \\ r_{i} = 2^{- (i + 1)}, \\ x_{i} = (x - q_{i}^{2}) \times 2^{(i + 1)} = (x - q_{i}^{2}) \times r_{i}^{- 1} \end{aligned} \end{aligned}

因此

若
$s_{i} + r_{i} \leq x_{i}$ ，則
- $q_{i + 1} = q_{i} + r_{i}$
- $s_{i + 1} = (s_{i} + r_{i}) + r_{i}$
- $x_{i + 1} = 2 x_{i} - 2 (s_{i} + r_{i}) = 2 [x_{i} - (s_{i} + r_{i})]$
  
  $\begin{aligned} s_{i + 1} & = 2 \times q_{i + 1} \\ = 2 \times [q_{i} + 2^{- (i + 1)}] \\ = (2 \times q_{i}) + 2^{- i} \\ = s_{i} + 2^{- i} \\ = s_{i} + 2^{- (i + 1)} + 2^{- (i + 1)} \\ = (s_{i} + r_{i}) + r_{i} \\ x_{i + 1} & = [x - q_{i + 1}^{2}] \times 2^{((i + 1) + 1)} \\ = [x - (q_{i} + r_{i})^{2}] \times 2^{(i + 2)} \\ = [x - (q_{i}^{2} + 2 q_{i} r_{i} + r_{i}^{2})] \times 2 r_{i}^{- 1} \\ = [x - q_{i}^{2}] \times 2 r_{i}^{- 1} - 2 q_{i} r_{i} \times 2 r_{i}^{- 1} - r_{i}^{2} \times 2 r_{i}^{- 1} \\ = 2 x_{i} - 2 s_{i} - 2 r_{i} \\ = 2 x_{i} - 2 (s_{i} + r_{i}) \end{aligned}$
若
$s_{i} + r_{i} > x_{i}$ ，則
- $q_{i + 1} = q_{i}$
- $s_{i + 1} = s_{i}$
- $x_{i + 1} = 2 x_{i}$
  
  $\begin{aligned} s_{i + 1} & = 2 \times q_{i + 1} \\ = 2 \times q_{i} \\ = s_{i} \\ x_{i + 1} & = [x - q_{i + 1}^{2}] \times 2^{((i + 1) + 1)} \\ = [x - q_{i}^{2}] \times 2^{(i + 2)} \\ = [x - q_{i}^{2}] \times 2 r_{i}^{- 1} \\ = 2 x_{i} \end{aligned}$

隨後看到 sqrtf, rsqrt, reciprocal implementations in Arm assembly 這篇文章主要是在說明該作者實作了一套用於計算 32 位浮點數尾數（mantissa）的平方根的演算法(預期輸入數值在區間

[1, 4)

範圍內)，並同時還提供了倒數平方根和尾數倒數的實現方法。

精度驗證：

作者通過暴力測試所有可能的尾數值，來去驗證此函數的輸出與正確結果的誤差在 1 ulp 以內。
通過計算殘差，並在必要時加 1，可獲得正確舍入的結果。

下列為計算殘差並在必要時加 1 的程式碼:

    uint32_t new_mantissa=sqrt_asm(mantissa32);
    int64_t msquared=(int64_t)new_mantissa*new_mantissa;
    int64_t x0=mantissa32;
    x0<<=23;
    int64_t residual=x0-msquared;
    if (residual>new_mantissa)
        {
            new_mantissa+=1;
        }

當一個數用 Q9.23 表示時，其整數值代表為「實際數值 ×

2^{23}

」。
例如，若我們希望表示

4.0

，則它在 Q9.23 中的表示為

4 << 23

；同理

2.0

就表示為

2 << 23

。

假設原數為 A（Q9.23 表示），那麼理想情況下它的平方根 R 應該滿足

\begin{matrix} R = \sqrt{A}, 但在固定點中有： A = 2^{23} \cdot mantissa 32, R = 2^{23} \cdot new_mantissa . \\ 所以理論上為： {(\frac{new_mantissa}{2^{23}})}^{2} = \frac{mantissa 32}{2^{23}} . \\ 兩邊同乘 2^{46} 可得： {new_mantissa}^{2} = mantissa 32 \times 2^{23} . \end{matrix}

了解完後就能知道上述的過程為：

首先 sqrt_asm 函數，得到根據原始尾數 mantissa32 計算出來的平方根結果。
將計算出來的平方根結果 new_mantissa 進行平方，得到的 msquared 實際上表示的是
$(m a n t i s s a 32)^{2}$ 。
原始輸入 mantissa32 是以 Q9.23 表示的，即實際數值 =
$m a n t i s s a 32 / 2^{23}$ 。1.
為了與 msquared（尺度為
$2^{46}$ ）進行比較，需要把原始數值放大 23 位：
計算殘差根據殘差進行四捨五入校正

此為用 c 去實做的結果 Commit a0dfec2。

「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能

TODO

程式運作原理

測驗三
在前文中，我們已經說明過為什麼pprev需要宣告為「指標的指標」，此處不再重複說明。接下來，我們將看到引入雜湊表（hash table）的實作，並藉此學習 Linux 核心的程式碼風格。

首先是結構體:

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

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

建立初始化一個 Hash Table（雜湊表）結構的函式，函式名稱是 map_init，它會根據給定的 bits 建立並初始化一個新的 map_t 結構，其初始化後結構為下列這張圖：

隨後定義了一個雜湊函式為下列程式碼:

#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
    /* High bits are more random, so use them. */
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}

至於為什麼選擇這個數值，主要是因為它是根據 Donald Knuth 的建議而來。根據《Hashing and Hash Tables》課程講義中的實驗結果（如下圖所示），當常數 A 採用黃金比例（golden ratio）時，這類雜湊函數被稱為 Fibonacci Hashing。

在 Fibonacci Hashing 中，key 經過乘以黃金比例後再進行位元操作，可產生分布相當均勻的索引值（index），也就是說碰撞的機率相對較低，因此特別適合用於實作雜湊表。

再來定義了一些輔助函式接下來會一一解釋其功用：

static struct hash_key *find_key(map_t *map, int key)

find_key(map_t *map, int key) 函數首先根據hash(key, AAAA)計算出 key 的哈希值，並以此從映射中選取對應的 hash bucket ，然後遍歷這個 bucket 中儲存的鏈節串列節點，對每個節點利用 container_of 轉換成包含該節點的 struct hash_key 結構，再比較這個結構中的 key 與傳入的 key 是否相等；如果相等，則返回該 struct hash_key 指標，否則遍歷結束後返回 NULL。

上述的說明和 hash 函式的定義我們可以得出 AAAA = map->bits，因為我們算出的 hash 值要在 0 ~ bucket-1。

void *map_get(map_t *map, int key)

map_get(map_t *map, int key) 函數則調用 find_key 尋找指定 key，如果找到了則從返回的 struct hash_key 結構中提取並返回對應的 data，如果找不到則返回 NULL。

void map_add(map_t *map, int key, void *data)

這個函式的作用是將一個新的鍵值對插入到哈希映射中。它的流程如下：

檢查重複：首先呼叫 find_key(map, key) 檢查是否已經存在該 key，如果存在的話就直接返回。
建立新節點：若不存在的話，則會分配一個新的 hash_key 節點，並將 key 與 data 儲存其中。
插入鏈節串列：利用hash(key, BBBB)計算 hash bucket，然後將新節點插入該桶的鏈節串列頭部，並更新相應的指標（這裡用 CCCC 與 DDDD 表示更新操作）。

下列為流程圖：

上述的說明我們可以知道 BBBB = map->bits、 CCCC = first->pprev 、DDDD = n->pprev。

void map_deinit(map_t *map)

這個函式用來銷毀整個 hash table。其步驟是：

檢查 map 是否為 NULL，若是則返回。
遍歷每個 hash bucket，對 bucket 中所有鏈節串列節點進行處理。
將每個節點從鏈節串列中移除（更新指針，這裡用 EEEE 表示操作），
釋放節點內存（先釋放 kn->data，再釋放 kn 本身）。
最後釋放整個 map 結構。

因此可得知 EEEE = n->pprev。

此為測試程式碼 Commit 11afc62。

證明 Theorem S

首先在證明 Theorem S 之前我們必須先了解什麼是 Theorem S ？

至於為什麼要介紹這個公式，是因為

\frac{\sqrt{5} - 1}{2}

，也就是

ϕ^{- 1}

（黃金比例的倒數），是一個無理數。根據「三間隔定理」（Three-Gap Theorem），當

θ

為無理數時，其倍數的小數部分

k θ

（

k = 1, 2, 3, \dots

）在區間

[0, 1]

上會呈現均勻且無週期性的分佈。這個性質使得選用

ϕ^{- 1}

作為乘法哈希中的乘數時，哈希值能夠近似均勻地分散，大幅降低碰撞機率——這正是乘法哈希所追求的核心目標。

Theorem S. Let

θ

be any irrational number. When the points {

θ

}, {

2 θ

}, …, {

n θ

} are placed in the line segment [0 … 1], then

n + 1

line segments formed have at most three different lengths. Moreover, the next point {

(n + 1) θ

} will fall in one of the largest existing segments.

我參考了 2021 年提出的一個簡化版證明 Three Distance Theorem: Liang’s Proof 並提出下列這個例子:

假設今天有個無理數叫做

α

，而 {

α

} 表示為取

α

的小數部分，然後就能產生一列數 {

0 α

}, {

α

}, {

2 α

}, …, {

n α

} 今天把它們都放置在

[0 \dots 1]

線段上，也就是把所有值都取

m o d 1

，把這

n + 1

個點從小到大排列，就會把區間

[0 \dots 1]

切分為

n + 1

個區段，可以看到下圖展示了當

n = 10

各段之間的長度（以不同顏色區分）。

可以發現這些段長只有三種可能的數值：大約

0.090

跟

0.146

和

0.056

以此類推。

探討 Linux 核心中使用 hash table 的應用案例

PID Hash Table：加速 process 查找

在 Linux 中，每個 process 都會有一個唯一的識別碼，也就是 PID（Process ID）。當其他模組或系統呼叫要查找特定 PID 對應的 task_struct 時，如果每次都要從整個 process 列表線性搜尋，效率會非常差。
如何可以知道是用 Hash Table 呢 ? 可以看到/linux/pid.h找到了相關的敘述：

/*
 * What is struct pid?
 *
 * A struct pid is the kernel's internal notion of a process identifier.
 * It refers to individual tasks, process groups, and sessions.  While
 * there are processes attached to it the struct pid lives in a hash
 * table, so it and then the processes that it refers to can be found
 * quickly from the numeric pid value.  The attached processes may be
 * quickly accessed by following pointers from struct pid.
 *

解決方案：建立一張 PID 對應 task_struct 的 Hash Table
Linux 使用 pid_hash 陣列，加上雜湊函式（例如 hash_long(pid, bits)）對 PID 建立雜湊的索引。查找 process 時，可以直接根據 PID 對應到該 bucket 內的 linked list，再進行比對。

好處

平均查找效率為 O(1)，可避免 O(n) 的線性搜尋
提升系統呼叫（例如 kill(pid)、getpid）時的效率

dcache：加速檔名（路徑）查找

當使用者在 shell 下執行 cd /home/user/documents 或 cat file.txt 時，VFS（Virtual File System）需要一層層地從根目錄開始解析每個檔名，找到對應的 inode。如果每次都從磁碟讀取資訊，會非常耗時。

解決方案：使用 dcache（目錄快取）
Linux 將每個路徑段（例如 /home、/home/user）快取為一個 dentry 結構，並使用 hash table（例如 dentry_hashtable）來加速路徑名稱查找。
使用的 key 為父 dentry 加上檔名，value 則是對應的 dentry 結構（其中包含 inode 的指標）。

qstr（快速字串)
除了保存字串指標（name）之外，同時保存字串的長度（len）與經過計算的雜湊值（hash），並透過條件編譯確保在不同端序系統中能夠正確排列。

struct qstr {
	union {
		struct {
			HASH_LEN_DECLARE;
		};
		u64 hash_len;
	};
	const unsigned char *name;
};

這裡的 name 指向一個字串，比如一個檔案路徑（例如 ./test.txt）。而 HASH_LEN_DECLARE 則是一個巨集，用來宣告兩個 32 位元的成員，根據系統的位元組序（Endian）來決定其排列順序：

在 Little Endian 系統下，其排列為 u32 hash; u32 len，*
在 Big Endian 系統下，排列則是 u32 len; u32 hash。

這樣設計可以確保在 union 中以 64 位元整數（hash_len）來存取時，雜湊值總是位於低 32 位，而字串長度則位於高 32 位。

#ifdef __LITTLE_ENDIAN
 #define HASH_LEN_DECLARE u32 hash; u32 len
 #define bytemask_from_count(cnt)	(~(~0ul << (cnt)*8))
#else
 #define HASH_LEN_DECLARE u32 len; u32 hash
 #define bytemask_from_count(cnt)	(~(~0ul >> (cnt)*8))
#endif

dentry（目錄項目）
表示檔案系統中目錄結構的一個節點。每個 dentry 內部保存了名字（透過 struct qstr）、父目錄指標、指向 inode 的指標、快取鏈表、鎖與引用計數等。

下列這段程式碼主要定義了一個「快速字串」(qstr) 結構，用於在檔案系統中傳遞字串的同時，保存字串的附加資訊（長度與雜湊值）

下列為 dentry 的連接方式的例子，其中有一個 root_dentry 其 parent 指向自己：

#define IS_ROOT(x) ((x) == (x)->d_parent)

再來看到下列程式碼講述了struct dentry，它記錄了目錄項目的所有狀態信息。其欄位分為兩大部分：一部分經常被查找操作讀取 (RCU 同步機制)，必須快速而高效；另一部分則與引用計數、狀態更新及與檔案系統其它部分的交互有關：

	/* RCU lookup touched fields */
	unsigned int d_flags;		/* protected by d_lock */
	seqcount_spinlock_t d_seq;	/* per dentry seqlock */
	struct hlist_bl_node d_hash;	/* lookup hash list */
	struct dentry *d_parent;	/* parent directory */
	struct qstr d_name;
	struct inode *d_inode;		/* Where the name belongs to - NULL is
					 * negative */
	union shortname_store d_shortname;
	/* --- cacheline 1 boundary (64 bytes) was 32 bytes ago --- */

Read-copy update (RCU) is a synchronization mechanism that was added to the Linux kernel in October of 2002. RCU achieves scalability improvements by allowing reads to occur concurrently with updates.

引用計數與鎖
透過 dentry 的 d_lockref 結構來管理引用計數，確保在使用期間不會被釋放；而 d_lock 則保護部分字段的並發存取。

好處

可大幅減少磁碟 I/O 次數
常用目錄查找速度更快
降低 inode 資訊的重新載入頻率

2025q1 Homework2 (quiz1+2)

第一週測驗題

程式運作原理

撰寫合併排序操作

程式運作原理

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

程式運作原理

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

第二週測驗題

程式運作原理

將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能

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

以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格

「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能

程式運作原理

證明 Theorem S

探討 Linux 核心中使用 hash table 的應用案例

Read more

2025q1 Homework1 (lab0)

ideas

System-Level I/O

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