2025q1 Homework2 (quiz1+2)

# 2025q1 Homework2 (quiz1+2) contributed by < `Huadesuwa` > ## 第 1 周測驗題 ### 測驗 `1` :::success 解釋上方程式碼運作原理 :::  ![B1csI9bqJe](https://hackmd.io/_uploads/HkihF0aj1l.png) 首先看到 `struct list_item` 為節點的結構，其中有一個整數型別 `value` 用於儲存資料，以及一個 a pointer named `next` to a `strcut list_item` ，因此可以得知這是一個單向的鏈結串列，而 `head` 則會指向整個鏈結串列 ```c typedef struct list_item { int value; struct list_item *next; } list_item_t; typedef struct { struct list_item *head; } list_t; ```  ```c static inline void list_insert_before(list_t *l, list_item_t *before, list_item_t *item); ``` 其關鍵操作 `list_insert_before` 函式的語意如下：函式會逐步走訪整個鏈結串列，定位到 `before` 之前指向的節點，並將 `item` 插入該位置 - 時間複雜度為 $O(n)$ ，n 是指需要幾步才能找到要插入的位置 - 若 `before` 指向鏈結串列的頭，意謂著會插入在鏈結串列最前面的位置 ```graphviz digraph foo { rankdir=LR; subgraph cluster_0 { label = "linked list" node [shape=record]; head [shape=ellipse]; a [label="{ <data> 12 | <ref> }", width=1.2] b [label="{ <data> 37 | <ref> }", width=1.2]; c [label="{ <data> 99 | <ref> }", width=1.2]; NULL [shape=plaintext]; } before [shape=plaintext]; subgraph cluster_1 { node [shape=record]; label = "item"; labelloc = "t"; item [label="{ <data> 1 | <ref> }", width=1.2]; } head -> a:data [arrowhead=vee, tailclip=true]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; before -> head [arrowhead=vee, tailclip=true, ]; } ``` ```graphviz digraph foo { rankdir=LR; subgraph cluster_0 { label = "linked list" node [shape=record]; head [shape=ellipse]; item [label="{ <data> 1 | <ref> }", width=1.2]; a [label="{ <data> 12 | <ref> }", width=1.2] b [label="{ <data> 37 | <ref> }", width=1.2]; c [label="{ <data> 99 | <ref> }", width=1.2]; NULL [shape=plaintext]; } head -> item:data [arrowhead=vee, tailclip=true]; item:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` - 反之，指向 `NULL` ，則會插入在尾巴 ```graphviz digraph foo { rankdir=LR; subgraph cluster_0 { label = "linked list" node [shape=record]; head [shape=ellipse]; a [label="{ <data> 12 | <ref> }", width=1.2] b [label="{ <data> 37 | <ref> }", width=1.2]; c [label="{ <data> 99 | <ref> }", width=1.2]; NULL [shape=plaintext]; } before [shape=plaintext]; subgraph cluster_1 { node [shape=record]; label = "item"; labelloc = "t"; item [label="{ <data> 1 | <ref> }", width=1.2]; } head -> a:data [arrowhead=vee, tailclip=true]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; before -> NULL [arrowhead=vee, tailclip=true, ]; } ``` ```graphviz digraph foo { rankdir=LR; node [shape=record]; head [shape=ellipse]; a [label="{ <data> 12 | <ref> }", width=1.2] b [label="{ <data> 37 | <ref> }", width=1.2]; c [label="{ <data> 99 | <ref> }", width=1.2]; NULL [shape=plaintext]; item [label="{ <data> 1 | <ref> }", width=1.2]; head -> a:data [arrowhead=vee, tailclip=true]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> item:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; item:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` - 除了之外的事件都被視為 `Undefined` <br>  其測試程式 `test_list` 將會對 `list_insert_before` 進行測試，驗證函式功能是否正確: - 將 `before` 設置為鏈結串列的頭( `l.head` )，測試插入 `item` 到前面的功能 - 將 `before` 設置為 `NULL` ，測試插入 `item` 到後面的功能 - 判斷是否有 `Unexpected Value` 的情況 - 測試完畢後，重置鏈結串列(將值由小到大重新插入) :::success 在現有的程式碼基礎上，撰寫合併排序操作 ::: 使用間接指標 `**ptr` 指向鏈結串列的頭，避免配置暫時指標的記憶體空間，而迴圈的中止條件為其中一串鏈結串列被走訪完畢 ( `NULL` ) ，剩餘的則透過 `bitops` 操作串上。 > 因為是單向鏈結串列(傳入的鏈結串列皆為排序過的)，所以當走訪過程中指向 `NULL` ，則代表其中一項串列被合併完了。 ```c list_item_t **ptr = &head->head, **node; for (node = NULL; L1 && L2; *node = (*node)->next) { node = (L1->head->value < L2->head->value) ? &L1->head : &L2->head; *ptr = *node; ptr = &(*ptr)->next; } *ptr = (list_item_t *) ((uintptr_t) L1->head | (uintptr_t) L2->head); ``` ### 測驗 `2` :::success 解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼 ::: #### 程式碼函式此程式碼實作了一個**二元搜尋樹 (Binary Search Tree, BST)** 來管理記憶體區塊，其中每個節點 (`block_t`) 代表一個記憶體區塊。以下是程式中的主要函式及其用途： **1. `block_t` (二元搜尋樹的節點結構)** - `size`：記錄該記憶體區塊的大小。 - `l, r`：指向左右子節點，形成二元搜尋樹 (BST) 結構。 **2. `find_free_tree` (搜尋記憶體區塊)** - 在 BST 中搜尋大小為 `target` 的節點，回傳該節點的位置 (`**node_ptr`)。 **3. `find_predecessor_free_tree`** - 在 BST 中，尋找某個節點的 **in-order predecessor**。 - **in-order predecessor** 是 BST 中**小於該節點的最大節點**，即左子樹中最右側的節點。 **4. `remove_free_tree` (刪除 BST 節點)** - 負責從 BST 中移除指定的節點，並確保樹的結構仍然維持 BST 的特性。 - **依據節點的子節點數量，分為三種刪除情況**： 1. **Case 1：刪除的節點沒有子節點** 2. **Case 2：刪除的節點只有一個子節點** 3. **Case 3：刪除的節點有兩個子節點** #### 刪除節點的處理邏輯 - [ ] **Case 1：刪除的節點沒有子節點** 此情況最簡單，直接刪除節點即可。 ##### **處理方式** - `*node_ptr = NULL;` - [ ] **Case 2：刪除的節點只有一個子節點** 需要讓子節點取代被刪除的節點。 ##### 處理方式 1. 判斷 `target` 是**只有左子節點**還是**只有右子節點**。 2. 讓 `target` 的**唯一子節點** 直接取代 `target`。 - [ ] **Case 3：刪除的節點有兩個子節點** 此情況最複雜，須透過 **in-order predecessor** 來找到取代節點。 ##### **處理方式 :** 1. 透過 `find_free_tree` 找到目標節點，`**node_ptr` 指向目標位置。 2. `**pred_ptr` 指向 `target` 左子樹的根節點。 3. 使用 `find_predecessor_free_tree` 找到 `target` 左子樹中的最大節點 (即 `target` 的 in-order predecessor)。 - [ ] **Still Case 3 (進階情境)** 當 `target` 有兩個子節點時，會進入 **Case 3** 的處理邏輯，在其中有以下細節需注意： 1. **`while` 迴圈持續向右走訪左子樹**，直到找到最右側的節點 (`in-order predecessor`)。 2. **`EEEE`** - `EEEE` 為 `(*pred_ptr)->r`，確保當 `pred_ptr` 已無右子節點時跳出迴圈。 3. **`FFFF`** - `FFFF` 為 `pred_ptr` 所指向節點的右子節點的地址 `&(*pred_ptr)->r`，如此才能使 `while` 迴圈不斷向右走訪。 4. **進一步確認 `in-order predecessor`** - 透過 `find_predecessor_free_tree` 再次搜尋，並使用 `assert` 檢查找到的 `in-order predecessor` 是否正確，若不相同則終止程式。 5. **替換 `target` 為 `pred_ptr`** - 若 `pred_ptr` 剛好是 `target` 的左子節點，則直接替換，並保留 `target` 的右子樹。 - 若 `pred_ptr` 位於 `target` 左子樹的更深處，則需要**先刪除 `pred_ptr`**，然後用它取代 `target`。 #### 測試程式碼 :::success 參閱 [memory-allocators](https://github.com/mtrebi/memory-allocators)，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現 ::: #### `allocator` 結構體定義首先，這是 `allocator` 的結構體定義： ```c typedef struct allocator { size_t size; block_t *root; char mem[0]; } allocator_t; ``` - `size` 是指分配給 `mem` 區塊的空間大小，不包括 header。 - `root` 是二元搜尋樹的根節點。 - `mem` 為長度為 0 的陣列，這樣可以讓它的空間取決於分配給它的大小，而不會佔用額外的空間。 #### `block` 結構體定義接著是 `block` 的結構體定義： ```cpp typedef struct block { size_t size; size_t prev_size; struct block *l, *r; char mem[0]; } block_t; ``` - `size` 用於記錄包含 header 的區塊大小，這樣可以減少運算。 1. 因為多數的使用場景是要拿來計算上一個和下一個區塊的地址 - `prev_size` 用於記錄前一個區塊的大小，有助於計算上一個區塊的位置，並且能夠用來判斷區塊是否已被使用。 - `l` 和 `r` 依然是代表二元搜尋樹的左、右子節點。 - `mem` 和上方一樣的概念 #### 以下是三個主要函式的說明： ```c /** * alloc_create - Create a new allocator with a * maximum memory size, which will be aligned up to 8 bytes. * @size: maximum memory size */ allocator_t *alloc_create(size_t size); /** * print_tree - Print the tree in preorder. * @root: the root node */ void print_tree(block_t *root); /** * alloc_alloc - Allocate memory with allocator and size. * If there is not any invalid block, it will return NULL. * @allocator: the allocator * @size: the size of memory needed */ void *alloc_alloc(allocator_t *allocator, size_t size); /** * alloc_free - Free an allocated memory. * @allocator: the allocator * @ptr: a pointer to the memory region */ void alloc_free(allocator_t *allocator, void *ptr); ``` - `alloc_create` 用於創建一個新的 `allocator` ，並指定最大可用的記憶體大小。 - `alloc_alloc` 用來從 `allocator` 中分配一塊指定大小的記憶體。 - `alloc_free` 用來釋放一塊已分配的記憶體區塊。 `alloc_create` 函式的實作如下： 1. 首先，`size` 會被對齊至 8 位元組，然後分配空間。 1. 並在末尾插入一個 `inuse` 的 `block_t`。 - 這樣可以確保每個區塊都能夠正確地存取下一個區塊（`NEXT_BLOCK`）。 1. 整個記憶體區塊被轉換為一個 `block_t`，並插入到二元搜尋樹中。 `alloc_alloc` 函式的實作如下： 1. 首先將 `size` 進行 `ALIGN_UP` 操作，確保對齊。 1. 之後確保記憶體可用空間能夠至少容納兩個 `header` 和所需的記憶體大小 `size` 。 - 這樣就可以將其分割為兩個區塊。 1. 移除原本的區塊，然後將剩餘空間重新插入二元搜尋樹。 `alloc_free` 函式的實作如下： 1. 釋放指定區塊時，首先檢查這個 `block` 前後區塊是否正在使用中。 1. 如果這些區塊未被使用，則將它們從樹中移除並合併，最後重新插入到樹中。 > commit:  #### 巨集定義以下是用於區塊管理和記憶體對齊的幾個重要巨集： ```c #define ALIGN_UP(size) (((size) + 7) & ~0x7) /* size filed is or'ed with PREV_INUSE when previous adjacent chunk in use */ #define prev_inuse 0x1 /* extract inuse bit of previous chunk */ #define PREV_INUSE(block) (((block_t *) (block))->prev_size & prev_inuse) /* extract block's inuse bit */ #define INUSE(block) (((block_t *) (block))->size & prev_inuse) #define CLEAR_USE_BIT(size) ((size) & ~(prev_inuse)) #define NEXT_BLOCK(block) \ ((block_t *) ((char *) (block) + \ CLEAR_USE_BIT(((block_t *) (block))->size))) #define PREV_BLOCK(block) \ ((block_t *) ((char *) (block) - \ CLEAR_USE_BIT(((block_t *) (block))->prev_size))) #define NEXT_INUSE(block) (INUSE(NEXT_BLOCK(block))) #ifndef container_of #define container_of(ptr, type, member) \ ((type *) ((char *) (ptr) - offsetof(type, member))) #endif ``` - `ALIGN_UP` 向上對齊到 8 位元組 - `PREV_INUSE` 上一個區塊是否被使用中 - `NEXT_INUSE` 下一個區塊是否被使用中 - `INUSE` 現在區塊是否被使用中 - `CLEAR_USE_BIT` 將大小去除 `USE_BIT` - `NEXT_BLOCK` 下一個區塊 - `PREV_BLOCK` 前一個區塊 - `container_of` 將 `list.h` 中使用的巨集引入，可以從成員得到結構體 ```shell $ ./test.elf malloc: 324210046 custom-alloc: 298007916 ``` 使用gnuplot繪製 ![statistic](https://hackmd.io/_uploads/HJ4UsP06yl.png) ### 測驗 `3` :::success 解釋上述程式碼運作原理 ::: 〈[Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)〉提出非遞迴 (non-recursive; iterative) 的快速排序法。此處提到的方法是以 swap 為主體，利用 `L` 與 `R` 去紀錄需交換的數量，再用 `begin[]` 與 `end[]` 作為堆疊，用來紀錄比較的範圍。在此使用了 Linux 風格的 List API 來建立鍊結串列，並使用 value 來紀錄數值。 ```c typedef struct __node { long value; struct list_head list; } node_t; ``` 以下為測試與輔助函式: `list_construct` : 在 `list` 中建立新的節點。 `list_free` : 釋放整個鏈結串列 `list` 已分配的記憶體空間。 `list_is_ordered` : 驗證鏈結串列 `list` 是否為有序排列。 `shuffle` : 打亂陣列的排列，運作條件為 `n < RAND_MAX` `list_tail` : 找到鏈結串列 `list` 的尾巴 `list_length` : 計算鏈結串列 `list` 大小(內含多少節點) `rebuild_list_link` : 將單向鏈結串列轉換為雙向環狀鏈結串列 - 迴圈內會將單向連接轉變為雙向連接，直到走訪至鏈結串列的尾巴 ( `NULL` ) - 因此， GGGG 為 `head->prev=prev` ，如此才能做到首尾相連 ```c while (node) { node->prev = prev; prev = node; node = node->next; } prev->next = head; head->prev=prev ``` 接著便開始進行排序的動作， ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; HEAD [label="HEAD", shape=record]; N1 [label="{ <value> 3 }", shape=record]; N2 [label="{ <value> 1 }", shape=record]; N3 [label="{ <value> 4 }", shape=record]; N4 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; HEAD -> N1; N1 -> N2; N2 -> N3; N3 -> N4; N4 -> N5; N5 -> NULL; N2 -> N1 ; N3 -> N2 ; N4 -> N3 ; N5 -> N4 ; } ``` 排序的過程中，先將 `L` 及 `R` 兩指標指向鏈結串列的頭及尾。 ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; HEAD [label="HEAD", shape=record]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; L -> N3; R -> N5; HEAD -> N3; N3 -> N1; N1 -> N4; N4 -> N2; N2 -> N5; N5 -> NULL; N5 -> N2 ; N2 -> N4 ; N4 -> N1 ; N1 -> N3 ; } ``` 若 `L` 及 `R` 兩者不同，則將 `piviot` 指向 `L` 所指的節點，並將 `piviot` 的數值存於 `value`。 ```c value = list_entry(pivot, node_t, list) -> value ``` ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; HEAD [label="HEAD", shape=record]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; piviot [label="*piviot",shape=plaintext]; value [label="value = 3",shape=plaintext]; L -> N3; R -> N5; piviot -> N3 HEAD -> N3; N3 -> N1; N1 -> N4; N4 -> N2; N2 -> N5; N5 -> NULL; N5 -> N2 ; N2 -> N4 ; N4 -> N1 ; N1 -> N3 ; } ``` 使用 `p` 指向 `piviot` 的下一個節點，並斷開 `piviot` (指向 `NULL` )。 ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; piviot [label="*piviot",shape=plaintext]; p [label="*p",shape=plaintext]; value [label="value = 3",shape=plaintext]; p -> N1; L -> N3; R -> N5; piviot -> N3 N1 -> N4; N4 -> N2; N2 -> N5; N5 -> NULL; N5 -> N2 ; N2 -> N4 ; N4 -> N1 ; } ``` 使用 `p` 逐步走訪整個節點，將小於 `value` 的置於 `left` 中，大於 `value` 則置於 `right` 中。 ```c int n_value = list_entry(n, node_t, list)->value; ``` ```c if (n_value > value) { n->next = right; right = n; } else { n->next = left; left = n; } ``` ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; piviot [label="*piviot",shape=plaintext]; value [label="value = 3",shape=plaintext]; left [label="*left",shape=plaintext]; right [label="*right",shape=plaintext]; piviot -> N3 L -> N3; R -> N5; left -> N2; right -> N5 ; N5 -> N4; N2 -> N1; } ``` 接著將 `begin[]` 指向對應的位置。 ```c begin[i]= begin[0] = left; begin[i + 1]= begin[1] = pivot; /* JJJJ */ begin[i + 2]= begin[2] = right; /* KKKK */ left = right = NULL; ``` ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 2",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; begin_i1 [label="begin[1]",shape=plaintext]; begin_i2 [label="begin[2]",shape=plaintext]; begin_i1 -> N3 L -> N3; R -> N5; begin_i -> N2; begin_i2 -> N5 ; N5 -> N4; N2 -> N1; } ``` 在下一輪，同樣將 `L` 指向 `begin[i]` 即 `begin[2]` (從較大子序列開始), 而 `R` 則指向 `begin[2]` 尾端。 ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 2",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; begin_i1 [label="begin[1]",shape=plaintext]; begin_i2 [label="begin[2]",shape=plaintext]; begin_i1 -> N3 R -> N4; begin_i -> N2; L -> N5 ; N5 -> N4; begin_i2 -> N5; N2 -> N1; } ``` 此時按照先前的步驟將 `piviot` 設置在 `L` 並將 `p` 指向 `piviot` 下一個節點 ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 2",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; value [label="value = 5",shape=plaintext]; piviot [label="*piviot",shape=plaintext]; p [label="*p",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; begin_i1 [label="begin[1]",shape=plaintext]; begin_i1 -> N3 begin_i -> N2; N2 -> N1; piviot -> N5; N5 -> N4; p -> N4; } ``` 同樣逐步走訪節點，將小於 `value` 的置於 `left` 中，大於 `value` 則置於 `right` 中，並將 `begin[]` 指向對應的位置。 ```c begin[i]= begin[2] = left; begin[i + 1]= begin[3] = pivot; begin[i + 2]= begin[4] = right; left = right = NULL; ``` ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 2",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; value [label="value = 5",shape=plaintext]; piviot [label="*piviot",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; left [label="*left",shape=plaintext]; right [label="*right",shape=plaintext]; begin_i1 [label="begin[1]",shape=plaintext]; begin_i1 -> N3 begin_i -> N2; N2 -> N1; left -> N4 piviot -> N5; right -> NULL; } ``` ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 4",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; begin_i [label="begin[0]",shape=plaintext]; begin_i1 [label="begin[1]",shape=plaintext]; begin_i2 [label="begin[2]",shape=plaintext]; begin_i3 [label="begin[3]",shape=plaintext]; begin_i1 -> N3 begin_i -> N2; N2 -> N1; begin_i2 -> N4 begin_i3 -> N5; } ``` 此時 `L` 將指向 `begin[4]` , `R` 指向 `begin[4]` 的尾端，兩者皆指向 `NULL` ，且 `L` 為 `NULL` 因此 `i= i-1 = 3` 。又 `3` 也同樣為單一一個節點，因此 `i` 會不斷扣一並在過程中逐步將元素加到 result 中。 ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 2",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; result [label="*result",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; begin_i1 [label="begin[1]",shape=plaintext]; begin_i2 [label="begin[2]",shape=plaintext]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; begin_i1 -> N3 L -> N2 R -> N1 begin_i -> N2; N2 -> N1; begin_i2 -> N4 result -> N5; } ``` ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 1",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; result [label="*result",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; begin_i1 [label="begin[1]",shape=plaintext]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; begin_i1 -> N3 L -> N2 R -> N1 begin_i -> N2; N2 -> N1; result -> N4; N4 -> N5 } ``` ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 0",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; result [label="*result",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; L [label="*L",shape=plaintext]; R [label="*R",shape=plaintext]; L -> N2 R -> N1 begin_i -> N2; N2 -> N1; result -> N3; N4 -> N5; N3 -> N4 } ``` 此時依照先前的方法同樣為 2 及 1 兩個節點設置 `begin[]` 。 ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 2",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; result [label="*result",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; begin_i1 [label="begin[1]",shape=plaintext]; begin_i -> N1; begin_i1 -> N2 result -> N3; N4 -> N5; N3 -> N4 } ``` 最後使用 result 收回 ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 1",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; result [label="*result",shape=plaintext]; begin_i [label="begin[0]",shape=plaintext]; begin_i -> N1; result -> N2; N4 -> N5; N3 -> N4 N2 -> N3 } ``` ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; i [label="i = 0",shape=plaintext]; N3 [label="{ <value> 3 }", shape=record]; N1 [label="{ <value> 1 }", shape=record]; N4 [label="{ <value> 4 }", shape=record]; N2 [label="{ <value> 2 }", shape=record]; N5 [label="{ <value> 5 }", shape=record]; result [label="*result",shape=plaintext]; result -> N1; N4 -> N5; N3 -> N4 N2 -> N3 N1 -> N2 } ``` 接著再使用 `rebuild_list_link` 設置回原本的雙向環狀鍊結串列。 ```graphviz digraph LinkedListSort { rankdir=LR; node [shape=record]; // 定義節點 N1 [label="1 ", shape=record]; N2 [label="2 ", shape=record]; N3 [label="3 ", shape=record]; N4 [label="4 ", shape=record]; N5 [label="5 ", shape=record]; // 指向排序結果 result [label="*result", shape=plaintext]; result1 [label="*result", shape=plaintext]; // 雙向連結：每個節點都指向前後節點 result -> N1; N1 -> N2; N2 -> N3; N3 -> N4; N4 -> N5; N2 -> N1; N3 -> N2; N4-> N3; N5 -> N4; N5 -> result1; } ``` ::: success 研讀〈[A comparative study of linked list sorting algorithms](https://dl.acm.org/doi/pdf/10.1145/225890.225893)〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作 ::: 論文起因於 **Sediment Sort** ——一個聲稱針對 *double linked-list* 最快且最有效率的排序演算法。為驗證其效能，作者整理並比較了六種針對不同鏈結串列結構的排序演算法進行比較，分類如下： - [ ] **針對 Double Linked-List：** - `Sediment Sort` - [ ] **針對 Single Linked-List：** - `Selection Sort` - `Merge Sort` - `Bubble Sort` - `Quick Sort` - 於排序過程中額外使用一個 `equal` 鏈結串列，來記錄排序時具有相同大小的元素，**以維持排序的穩定性 (stable)**。作者針對上述六種排序演算法進行實驗，比較它們在不同資料量下的效能。排序資料量 $n$ 從 $100$ 遞增至 $1000$，並記錄每種演算法在對應資料量下的執行時間。下表為各演算法在不同資料量下的執行時間比較： | $n$ | Sediment | Bubble | Selection | Merge | Quick | Tree | | :---: | :------: | :----: | :-------: | :---: | :---: | :--: | | 100 | 0.22 | 0.12 | 0.10 | 0.08 | 0.07 | 0.05 | | 200 | 0.98 | 0.54 | 0.44 | 0.15 | 0.13 | 0.09 | | 300 | 2.20 | 1.22 | 0.76 | 0.23 | 0.22 | 0.19 | | 400 | 4.18 | 2.42 | 1.44 | 0.32 | 0.30 | 0.21 | | 500 | 6.38 | 3.74 | 2.18 | 0.42 | 0.42 | 0.30 | | 600 | 10.2 | 6.48 | 4.06 | 0.53 | 0.51 | 0.34 | | 700 | 15.38 | 10.10 | 7.60 | 0.63 | 0.57 | 0.43 | | 800 | 21.10 | 14.82 | 9.68 | 0.76 | 0.69 | 0.54 | | 900 | 28.34 | 20.20 | 13.62 | 0.88 | 0.79 | 0.60 | | 1000 | 36.58 | 26.14 | 17.88 | 1.01 | 0.89 | 0.69 | 由結果可觀察到，**Sediment Sort 雖然設計上是針對 Double Linked-List 的排序演算法，但在所有測試資料量下，其執行時間皆為最長，效能遠遜於其他排序演算法**。 > 我將運用 Linux 核心風格的 List API 實作 Sediment Sort 與 Tree Sort，並進行分析與驗證。 ## 第 2 周測驗題 ### 測驗 `1` #### 延伸問題 `1` 在此使用 Linux 核心風格 List API 來開發快速排序程式碼。使用 `list_head` 來建立鍊結串列，並使用變數型別 `uint16_t` 來紀錄要被排序的數值。 ```c struct listitem { uint16_t i; struct list_head list; }; ``` **以下為測試與輔助函式:** `cmpint` : 實作 `quicksort` 的比較，因為傳入的參數是 `void *` 不能做 `bitops` ，因此要先做強制型別轉換 `(const uint16_t *)` `random_shuffle_array` : 打亂 `operations` 裡的排列順序，於迴圈中 `get_unsigned16` 將決定每階段互相交換的位置 `getnum` : * `s1、s2、s3` 以 `static` 宣告，因此只會初始化一次 * 使得每獲取一次亂數就更新一次，下次獲取的亂數就不會與現在一致，作到亂數的效果。 ``` s1=(s1*171)%30269 s2=(s2*172)%30307 s3=(s3*170)%30323 ``` `get_unsigned16` : 呼叫上述 `getnum` 函式兩次製造16位元的亂數 `main` : 對含有 256 個數字的陣列 `value` 進行隨機排序，並建立一個鏈結串列加入這些數字。接著對鏈結串列執行 `list_quicksort` 快速排序，最後比較陣列 `value` 和鏈結串列的值 `i` ，若不同會因為巨集 `assert` 而終止程式。 **主要函式:** **list_quicksort** 1. 首先，要選擇鏈結串列第一個元素作為 `pivot` ，由於 `head` 會指向整個鏈結串列，因此使用 `list_first_entry` ，找到指向的鏈結串列第一個元素。 2. 之後，要從鏈結串列裡移除 pivot ，好讓 quicksort 對鏈結串列剩餘的元素進行快速排列。 3. 以 `list_for_each_entry_safe` 逐步走訪整個鏈結串列，將值小於 `pivot` 的用 `list_move_tail` 移入 `list_less` ，反之，大於的值移入 `list_greater` ```c 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); } ``` 4. 透過遞迴對 `pivot` 左右兩邊的鏈結串列進行排序，當鏈結串列排到不能在排時就返回(只有單一元素)。 5. 最後，當整個鏈結串列都排序完畢時，就要將 `pivot` 、 `list_less` 、 `list_greater` 合併。 ```c list_add(&pivot->list, head); list_splice(&list_less, head); list_splice_tail(&list_greater, head); ``` #### 延伸問題 `2` ### 測驗 `2` #### 延伸問題 `1` 在此嘗試開發整數的開平方根運算。首先是 `clz2` 函式，其作用是藉由遞迴呼叫以計算 [count leading zero](https://en.wikipedia.org/wiki/Find_first_set) (clz)。每次呼叫 `clz2()` 函式時，代表將目前關注的位元（bits）「切成一半」，以檢查 leading zero 的數量。以下藉由一個數值（0x0001F000）來說明其步驟： ``` 0x0001F000 = 0000 0000 0000 0001 1111 0000 0000 0000 ~2~ ``` - [ ] Step1 將此數值分為兩部分: 較高位 ( upper ) 與較低位 ( lower ) 。 | **Upper** | **Lower** | |:-:|:-:| | 0000 0000 0000 0001 | 1111 0000 0000 0000 | - [ ] Step2 此時，依據 `upper` 的數值判斷下一次遞迴呼叫應該處理哪一部份，以累計 leading zero 的數量。 - **若 `upper` 等於`0`**，則下一次遞迴呼叫應檢查 lower 部分，並用計數器（counter）記錄目前已累計的 leading zero（等於 upper 位元數）。 - **若 `upper` 不等於`0`**，則下一次遞迴呼叫應繼續檢查 upper 部分。 ``` upper = 0000 0000 0000 0001 ``` 由於 `upper` 不為 0，下一次遞迴呼叫將繼續檢查 `upper` 部分的 leading zero。 - [ ] Step3 遞迴呼叫 `clz2()` 函式，直到僅剩 2 位元（bits）需要檢查 leading zero，然後回傳結果。 ```c static const int mask[] = {0, 8, 12, 14}; // GGGG static const int magic[] = {2, 1, 0, 0}; // HHHH, IIII ``` - `mask` : 決定遮罩的大小，若 `upper` 不等於 `0`，則下一次遞迴呼叫時被使用 - `magic` : 當遞迴呼叫 `clz2()` 函式至僅剩 2 位元需要檢查，也就是 `c = 3` 時，建表判斷有多少 leading zero ```c 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] : 2 + magic[lower]; return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1); } ``` 如果 `upper` 不等於 `0`，則遞迴呼叫 `clz2(upper, c+1)`。由於 **leading zero** 只會出現在 `upper`，因此這部分的計算與 `lower` 無關。若 `upper` 等於 `0`，則需要計算當前區間 `16 >> c` 中的 **leading zero** 數量，然後再遞迴呼叫 `clz2(lower, c+1)` 來計算 `lower` 的 **leading zero** 數量。延伸 `clz2` 函式 count leading zero 想法: clz64 (計算 64-bit 整數的前導零數量) #### **`clz64` (計算 64-bit 整數的前導零數量)** 對於 64-bit 無符號整數 `x`，我們可以根據其高 32 位與低 32 位來決定如何計算前導零數量： - **若高 32 位不為 0**，則直接計算 `clz32(high 32 bits)`。 - **若高 32 位為 0**，則計算 `clz32(low 32 bits) + 32`，因為這表示高 32 位的所有位元都是 0。 ```c int shift = (total_bits - 1 - clz64(x)) & ~1; // MMMM y >>= 1; // NNNN m >>= 2; // PPPP ``` #### **`sqrti` (計算 64-bit 無符號整數的整數平方根)** `sqrti(x)` 的目標是求得 `floor(sqrt(x))`，即 `x` 的整數平方根。其核心思想類似於二進位搜尋，從 `x` 的最高有效位開始逐步逼近平方根。 ##### **步驟解析** 1. **確定最高有效位 (MSB, Most Significant Bit)** 透過 `clz64(x)` 計算出 `x` 的 MSB 位置，並利用： \begin{align} \text{total_bits} - 1 - \text{clz64}(x) \end{align} 來確定 MSB 在二進位數字中的實際位置。 2. **確保起始的位移量是偶數** 由於平方根的位數變化與整數平方的位數變化相對應，因此對 `MSB` 進行位元操作： \begin{align} m = (\text{MSB} - 1) \& \sim 1 \end{align} 這確保 `m` 是偶數，使得 `m` 每次遞減 2 時能夠對應二進位平方的變化。 #### **`sqrti` 計算範例：** 以 $N^2 = 17$ 為例，求 $\lfloor \sqrt{17} \rfloor$。首先，將 $17$ 轉換為二進位表示： \begin{align} N^2 = (17)_{10} = (10001)_2 \end{align} 最高位在 $b_4$，因此從 $m=4$ 開始，逐步降低並嘗試構造平方根。 | m | 計算平方值 | 結果 | |----------|----------|------| | 4 | $P_4^2 = (2^4)^2 = 256$ | $256 > 17$，$P_4 = P_5$，$a_4 = 0$ | | 3 | $P_3^2 = (2^3)^2 = 64$ | $64 > 17$，$P_3 = P_4$，$a_3 = 0$ | | 2 | $P_2^2 = (2^2)^2 = 16$ | $16 < 17$，$P_2 = P_3 + 2^2$，$a_2 = 2^2$ | | 1 | $P_1^2 = (2^2 + 2^1)^2 = 36$ | $36 > 17$，$P_1 = P_2$，$a_1 = 0$ | | 0 | $P_0^2 = (2^2 + 2^0)^2 = 25$ | $25 > 17$，$P_0 = P_1$，$a_0 = 0$ | 最終，平方根為： \begin{align} N = P_0 = P_1 = P_2 = 2^2 = 4 \end{align} 因此，**$17$ 的整數平方根為 $4$**。 #### 延伸問題 `2` #### 延伸問題 `3` ### 測驗 `3` #### 延伸問題 `1`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.