# 2025q1 Homework2 (quiz1+2)
contributed by < `thwuedwin` >
## 第 1 週測驗一
### 程式碼運作原理分析
這個測驗主要考察對指標操作的熟練度。目標是實作 `list_insert_before` 函式，它的功能是在鏈結串列中找到指定的節點 `before`，並將 `item` 插入到它的前面。
該函式會接收以下參數：
- `l`：指向鏈結串列的指標
- `before`：目標節點
- `item`：要插入的節點
實作方式是從 `l->head` 開始遍歷鏈結串列，直到找到 `before`，然後將 `item` 插入至其前方。
**不使用間接指標的程式碼**
```c
list_item_t *p;
for (p = l->head; p->next != before; p = p->next)
;
p->next = item;
item->next = before;
```
這個版本直接使用 `p` 作為普通指標，在找到 `before` 之前，持續向後移動 `p`，最後修改 `p->next` 來完成插入。
**使用間接指標的程式碼**
```c
list_item_t **p;
for (p = &l->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
```
這個版本改用指向指標的指標 `p`，直接追蹤 `next` 指標的位置，這樣在插入 `item` 時，不需要額外處理 `p->next`，程式碼更加簡潔。
| 題目 | 答案 |
| -------- | -------- |
AAAA| `&l->head`
BBBB| `before`
CCCC| `&(*p)->next`
DDDD| `item->next`
**優雅之處**
不使用間接指標的版本雖然可行，但需要處理 `p->next`，而使用間接指標的版本則巧妙地利用 `p` 直接指向 `next` 指標的位置，使得：
1. 迴圈條件 `*p != before` 更直覺，不需要額外比較 `next`
2. `*p = item` 直接修改指標，不需要額外處理 `p->next`
這樣的設計讓程式碼更加簡潔，減少了變數存取的間接層級，提高了可讀性和可維護性。
### 實作：合併排序
```c=
void merge_sort(list_t *l) {
if (list_empty(l) || list_is_singular(l))
return;
list_t left, right;
list_item_t *slow, *fast, *before;
slow = fast = l->head;
while (fast && fast->next) {
before = slow;
slow = slow->next;
fast = fast->next->next;
}
left.head = l->head;
right.head = slow;
before->next = NULL;
merge_sort(&right);
merge_sort(&left);
// merge
list_item_t *head, *l1, *l2;
list_item_t **p = &head;
l1 = left.head;
l2 = right.head;
for (; l1 && l2; p = &(*p)->next) {
if (l1->value <= l2->value) {
*p = l1;
l1 = l1->next;
} else {
*p = l2;
l2 = l2->next;
}
}
*p = (list_item_t *)((uintptr_t)l1 | (uintptr_t)l2);
l->head = head;
}
```
1. **尋找中間節點（第 5～15 行）**
使用快慢指標來找到鏈結串列的中間節點。
由於此實作使用的是單向鏈結串列，無法直接回溯，因此我們額外使用變數 `before` 記錄 `slow` 前一個節點，以便切斷鏈結，將其拆分成左右兩個子串列。
示意圖如下：
2. **遞迴排序子串列（第 17～18 行）**
將拆分後的 `left` 和 `right` 子串列遞迴地進行合併排序。
3. **合併兩個排序好的子串列（第 21～35 行）**
- 利用**間接指標**來避免對特殊情況的額外處理，例如首節點的變更。
此次實作也善用了我在第 2 週測驗一學習到的想法，用堆疊的區域變數來管理暫存的節點。
## 第 1 週測驗二
### 程式碼運作原理分析
根據函式名稱 `remove_free_tree`，我推測它的目的是尋找可用空間並將其從 free tree 中移除。然而，我一開始無法理解 `find_free_tree` 的具體功能，尤其是它的回傳型態竟然是 `block_t **`，這點讓我感到困惑。
在仔細閱讀程式碼後，我發現 `remove_free_tree` 的主要操作是更新變數 `node_ptr`，並根據 `*node_ptr` 子節點的數量，選擇不同的方式來更新它。此外，並且該函式的初始化方式是` find_free_tree(root, target)`。基於以上觀察，我推測這個函式的作用如下：
1. `find_free_tree(root, target)` 在 free tree 中搜尋 `target`，並回傳**指向 `target` 之親代節點指標的指標**。例如，若 `node->l == target` 為真，則回傳 `&node->l`。該回傳值由 `block_t **node_ptr` 接收，這樣一來，只要更新 `node_ptr`，便能直接修改親帶節點的指向。這種設計相當聰明且優雅。如示意圖：
2. 根據 `target` 子樹的結構，決定用哪個節點來取代 `target`：
- 若 `target` 有兩個子節點，則選擇左子樹最右側的節點來取代 `target`。
- 若 `target` 僅有一個子節點，則讓該子節點直接取代 `target`。
- 若 `target` 沒有子節點，則僅需將其移除。
3. 在移除 `target` 之前，將其子節點指標設為 `NULL`，避免產生錯誤的參照。
**尋找左子樹最右節點的程式碼**
```c
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
```
| 題目 | 答案 |
| -------- | -------- |
EEEE| `(*pred_ptr)->r`
FFFF| `&(*pred_ptr)->r`
### 實作： Custom memory allocators
目標是實作一個以 free tree 管理可用空間的記憶體分配器，目前實作尚未完成，以下是 ftalloc.h 程式碼：
```c=
#define BRK_SIZE 135168
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
typedef struct memory {
void *addr;
block_t block;
} memory_t;
block_t *root = NULL;
void init_free_tree();
void brk_free_tree(size_t size);
void free_free_tree();
block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);
void remove_free_tree(block_t **root, block_t *target);
void insert_free_tree(block_t **root, block_t *target);
void *ftalloc(size_t size);
void ftfree(void *p);
```
- `ftalloc` 和 `ftfree` 函式是預計提供給使用者呼叫的，功能應該與 `malloc` 和 `free` 相同。
- 第 7 - 9 行的函式負責管理可動態配置出的記憶體：
- 在使用此記憶體空間配置器前，必需先呼叫 `init_free_tree`。`init_free_tree` 會使用 `malloc` 預先配置預設為 `BRK_SIZE` 大小的空間，作為初始可動態配置的記憶體空間。該區塊會由 free tree 管理。
- 若需要動態配置的空間超出 free tree 所管理的範圍，則呼叫 `brk_free_tree` 來增加可配置的空間並將新增的空間加入 free tree，預設擴展大小為`BRK_SIZE`。
- 程式結束後需呼叫 `free_free_tree` 來釋放由 `init_free_tree` 和 `brk_free_tree` 分配的記憶體區塊。
- 第 18 - 21 行的函式負責新增和移除 free tree 節點：
- 在使用者呼叫 `ftalloc` 時，`remove_free_tree` 會在 free tree 中尋找適當的空間，將該區塊從 free tree 移除，並維護 free tree 的結構與完整性。詳細見上方程式碼分析。
- 在使用者呼叫 `ftfree` 時，`insert_free_tree` 會將釋放的空間重新加入 free tree，恢復其可用狀態。
**困難點**
- 按照題目的指示，應該要預先分配好不同大小的區塊，以增加空間區域性（spatial locality）。但這會增加記憶體管理所需的開銷。在 64-bit 系統中，每個指標變數的大小為 8 位元組，`memory_t` 結構至少佔 28 位元組，若每個 4 位元組的空間都由一個 `memory_t` 來管理的成本太高了。
- **解決方案**：
- 我目前的思路是將 memory_t 管理的最小單位設定為一個 page。每個 page 內會包含多個小區塊，並且使用額外的標籤來標明每個 `page` 所儲存空間的特定大小及其內部的 free list。對於每個 page 內的 free list，我打算使用更高效且成本較低的資料結構，例如 bit map，來儲存每個區塊的使用狀態。
- 另一個需要考量的問題是記憶體對齊問題（memory alignment）。目前我還沒有確定具體的解決方案，但這部分應該需要參考現有的記憶體配置器，了解如何處理對齊需求。一般來說，記憶體分配器會確保分配的區塊大小能夠符合系統的對齊要求。
## 第 1 週測驗三
### 程式碼運作原理分析
此測驗快速排序法的方式雖然不是使用遞迴實作，仍然是採用了分治的想法。
1. 把串列的第一個節點當作樞紐（pivot），走訪串列所有節點，將大於樞紐值的節點加入 `right` 串列，反之加入 'left' 串列。最終形成三個子串列，分別由 `left`、`pivot` 和 `right` 所指向。
2. 依序檢查 `right`、`pivot` 和 `left` 指向的串列是否需要排序，此演算法會先優先處理最右邊的串列。
流程比較複雜不好簡單解釋，直接參考程式碼：
```c
while (i >= 0) {
struct list_head *L = begin[i],
*R = list_tail(begin[i]);
if (L != R) {
/* Distribute each node into the
* appropriate list: left, pivot,
* or right, based on its value.
*/
begin[i] = left;
begin[i + 1] = pivot;
begin[i + 2] = right;
left = right = NULL;
i += 2;
} else {
if (L) {
L->next = result;
result = L;
}
i--;
}
```
第 3 行的 `if(L != R)` 判斷該串列是否包含兩個以上的元素，若是，則需排序。分類後會產生三個子串列，因此做 `i += 2`，代表下一輪處理最後新增的串列。而`else` 對應到串列僅有一個元素，表示已經排序完成，直接合併到 `result` 內。
**為何 `max_level` 的設值為 $2n$？**
```c
int max_level = 2 * n;
struct list_head *begin[max_level];
```
我思考流程是，考慮當串列大小為 $n$，且原先已排序（升序）時，每次選擇樞紐值都會選到當前最小的元素。因此：
- `left` 為空
- `pivot` 僅包含該最小值
- `right` 包含剩餘的 $n-1$ 個元素
由於該實作不是穩定排序，下一次迭代會選擇 `right` 的最大值作為新樞紐，接著又選擇最小值，如此交替進行。結果是：
- `right` 為空
- 下一輪會將當前最大值合併至 `result`
這個方法不會產生 $2n$ 個串列，最只會產生 $n$ 個。於是我改變思路，我希望每次選樞紐都選到最小的樞紐。觀察到在將原始串列搬移到 `left` 或 `right` 時是有尾端插入，可以利用這個特性建構串列。舉實際例子，假設有一串列順序為 `[1 3 5 7 8 6 4 2]`，則排序過程為
1. `[] [1] [2 4 6 8 7 5 3]`
2. `[] [1] [] [2] [3 5 7 8 6 4]`
3. `[] [1] [] [2] [] [3] [4 6 8 7 5]`
...
依此類推，最終就會產生 $2n$ 個串列。
| 題目 | 答案 |
| -------- | -------- |
GGGG| `head->prev=prev`
HHHH| `list_entry(pivot,node_t,list)->value`
IIII| `list_entry(n,node_t,list)->value`
JJJJ| `pivot`
KKKK| `right`
### 研讀[〈A comparative study of linked list sorting algorithms〉](https://dl.acm.org/doi/pdf/10.1145/225890.225893)
本文探討六種常見排序演算法的效率，並分析其時間複雜度與實際執行效能。下方表格皆來自 [〈A comparative study of linked list sorting algorithms〉](https://dl.acm.org/doi/pdf/10.1145/225890.225893)
**大 O 表示法與實際效率**
雖然在理論上，排序演算法的效率通常以 $O(f(n))$ 表示，但由於常數因子的影響，只有在 $n$ 足夠大時，$O(n^2)$ 的演算法才會比 $O(n\log n)$ 的演算法顯著低效。本研究的實驗範圍為 $n \geq 100$，因此可從結果觀察不同演算法在實務上的表現。若在 $n，100$ 的區間可能會有不同的結果。
從下表可見，在時間複雜度為 $O(n\log n)$ 的排序演算法中，二元樹排序法（Tree Sort）的效率優於快速排序法（Qsort）及合併排序法（Msort）。
**常數因子分析**
根據表格 1 和表格 2 的數據，可透過理論時間複雜度擬合出各演算法的常數，結果整理於表格 3。
表格 3 中的 ratio 欄位 代表當 $n \leq 1000$ 與 $n > 1000$ 時，對應的時間常數比值：
- 比值大於 1：表示該演算法在較小的 $n$ 下效率較佳，此實驗中複雜度為 $O(n^2)$ 的演算法屬於這類。
- 比值小於 1：表示該演算法在較大的 $n$ 下效率較佳，此實驗中複雜度為 $O(n\log n)$ 的演算法屬於這類。
這些常數也可用來評估不同演算法之間的效率差異，提供量化的效能對照。
此外，值得注意的是，本研究的測試方法是對同一組輸入進行多次實驗後取平均值。換句話說，輸入串列的排列方式可能僅限於少數幾種固定模式，這可能導致比較結果的不公平性。例如，雖然合併排序、快速排序和二元樹排序在平均時間複雜度皆為 $O(n\log n)$，但快速排序與二元樹排序在最差情況下可能達到 $O(n^2)$，而合併排序的最差時間複雜度仍維持在 $O(n\log n)$。然而，本文並未深入探討這些最差情況下的差異。此外，該研究僅以執行效率作為評估標準，並未考量演算法是否為**穩定排序法**（Stable Sort）或**原地演算法**（In-place Algorithm），這些因素在實務應用上可能同樣重要。
### 實作：雙向鏈結串列排序演算法
根據前述的實驗結果，二元樹排序（Tree Sort）在效率上表現較佳，因此我選擇實作此演算法。
二元樹排序的核心概念是：
1. 建立一棵二元搜尋樹（BST, Binary Search Tree），將鏈結串列中的節點依序插入二元搜尋樹。
2. 使用**深度優先搜尋（DFS, Depth-First Search）** 走訪 BST，並依序將節點還原為排序後的鏈結串列。
插入二元搜尋樹的平均時間複雜度為 $O(\log n)$，最差情況下則為 $O(n)$。由於共需插入 $n$ 個節點，整體排序的平均時間複雜度為 $O(n\log n)$，而最差情況下可能達到 $O(n^2)$。
樹狀結構如示意圖：
**實作**
排序函式 `treesort` 是主流程，此外，我實作了 `bst_insert` 和 `bst_traverse` 兩個輔助函式來處理二元搜尋樹的建立與遍歷。
主排序函式：`treesort`
`treesort` 會遍歷鏈結串列，將節點依序從原串列刪除後插入二元搜尋樹，最後透過 `bst_traverse` 將二元搜尋樹轉回排序後的鏈結串列。
```c
static void treesort(struct list_head *head)
{
struct list_head *node, *safe, *root = NULL;
list_for_each_safe (node, safe, head) {
list_del(node);
node->prev = NULL;
node->next = NULL;
bst_insert(&root, node);
}
bst_traverse(root, head);
}
```
插入函式：`bst_insert`
`bst_insert` 會將給定的節點插入二元搜尋樹。透過遞迴尋找適當的插入位置，並使用間接指標來處理二元搜尋樹的根節點與子樹的連結關係。
`if (root_element->value > node_element->value) `這個條件確保二元搜尋樹遵循穩定排序的特性，。
```c
void bst_insert (struct list_head **root, struct list_head *node)
{
if (!*root) {
*root = node;
return;
}
element_t *root_element, *node_element;
root_element = list_entry(*root, element_t, list);
node_element = list_entry(node, element_t, list);
if (root_element->value > node_element->value)
bst_insert(&(*root)->prev, node);
else
bst_insert(&(*root)->next, node);
}
```
遍歷函式：`bst_traverse`
`bst_traverse` 會 **以中序遍歷（In-Order Traversal）** 的方式走訪二元搜尋樹，並將最小的節點依序插回鏈結串列，達到排序的效果。
```c
void bst_traverse (struct list_head *root, struct list_head *head)
{
struct list_head *work;
if (root) {
bst_traverse(root->prev, head);
work = root->next;
INIT_LIST_HEAD(root);
//printf("%d ", list_entry(root, element_t, list) ->value);
list_add_tail(root, head);
bst_traverse(work, head);
}
}
```
## 第 2 週測驗一
### 程式碼運作原理分析
此測驗實作的**是遞迴版本**的快速排序，採用鏈結串列的方式進行排序。
1. 選取一個節點作為樞紐（pivot），走訪每個節點，將小於樞紐值的節點加入 `list_less`，其餘則加入 `list_greater`。
2. 遞迴地對 `list_less` 和 `list_greater` 進行排序。
3. 最終合併 `list_less`、`pivot` 和 `list_greater`，得到完整的排序結果。
| 題目 | 答案 |
| -------- | -------- |
AAAA| `list_first_entry`
BBBB| `list_del`
CCCC| `list_move_tail`
DDDD| `list_add`
EEEE| `list_splice`
FFFF| `list_splice_tail`
**學習心得**
在實作時，我經常猶豫應該使用區域變數還是動態配置記憶體來宣告 struct 變數。例如，我原本可能會寫出以下動態配置的版本：
```c
{
struct list_head *list_less, *list_greater;
list_less = malloc(sizeof(stuct list_head));
list_greater = malloc(sizeof(stuct list_head));
// ...
}
```
這種做法需要額外處理記憶體釋放 (free)，並且因為變數的生命週期變長，必須在額外的地方確保值的正確性，這可能反而會**降低程式的可讀性和安全性**。
相比之下，若改為**區域變數**，則可以利用**遞迴的堆疊行為自動釋放記憶體**，提升一致性與安全性：
```c
{
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
// ...
list_quicksort(&list_less);
list_quicksort(&list_greater);
}
```
這樣的設計方式讓變數的生命週期受到更好的控制，避免了手動管理記憶體可能帶來的錯誤。
### 穩定排序（stable sorting）分析
快速排序的穩定性主要取決於節點加入 `list_less` 和 `list_greater` 的方式。
1. 由於樞紐選擇最左側節點，因此與樞紐值相等的節點應該放在 `list_greater`，確保相同數值的元素仍維持原本的相對順序。
2. 關鍵點：加入串列時必須從尾端插入，如果從前端插入，原本的順序會被反轉。因此，應使用 `list_move_tail` 來保持排序的穩定性：
```c
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);
}
```
這樣的做法確保了排序的穩定性，即原本相同數值的節點在排序後仍維持其相對順序。
### 實作：改善 `random_shuffle_array`
### 實作：整合 `qtest` 並使用 perf 進行效能分析
**整合 `qtest`**
- 修改 `qtest.c`
- 在 `console_init` 函式內新增
```c
ADD_COMMAND(qsort, "Sort queue in ascending/descening order implemented by quicksort", "");
```
- 實作 `do_qsort` 函式，並呼叫對應的快速排序函式 `q_qsort`
- 修改 `queue.c`
- 實作 `q_qsort` 函式
```c
void q_qsort(struct list_head *head, bool descend)
{
list_quicksort(head);
if (descend)
q_reverse(head);
}
```
**以 perf 進行效能分析**
我實作了一個函式來讀取輸入檔案，該檔案包含 1024 個長度為 8 的字串。測試函式會將這些字串依序插入鏈結串列，並根據命令列參數選擇相應的排序方法：
- sort：對應原本實作的合併排序（Merge Sort）。
- qsort：對應此次新增的快速排序（Quicksort）。
:::spoiler 實驗環境
```shell
$ cat /etc/os-release
PRETTY_NAME="Ubuntu 24.04.1 LTS"
NAME="Ubuntu"
VERSION_ID="24.04"
VERSION="24.04.1 LTS (Noble Numbat)"
VERSION_CODENAME=noble
ID=ubuntu
ID_LIKE=debian
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
UBUNTU_CODENAME=noble
LOGO=ubuntu-logo
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700
CPU family: 6
Model: 151
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
Stepping: 2
CPU(s) scaling MHz: 25%
CPU max MHz: 4900.0000
CPU min MHz: 800.0000
BogoMIPS: 4224.00
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx p
dpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclm
ulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes x
save avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid e
pt_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsavec xgetbv1 x
saves split_lock_detect user_shstk avx_vnni dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req hfi vnmi umip
pku ospke waitpkg gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_clear serialize pconfig arch_lbr ibt flush_l1d arch_capabilit
ies
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 512 KiB (12 instances)
L1i: 512 KiB (12 instances)
L2: 12 MiB (9 instances)
L3: 25 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-19
Vulnerabilities:
Gather data sampling: Not affected
Itlb multihit: Not affected
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Not affected
Reg file data sampling: Mitigation; Clear Register File
Retbleed: Not affected
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2: Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-eIBRS SW sequence; BHI BHI_DIS_S
Srbds: Not affected
Tsx async abort: Not affected
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
:::
執行結果如下：
```shell
$ sudo perf stat -e cycles,instructions ./test sort
Performance counter stats for './test sort':
<not counted> cpu_atom/cycles/ (0.00%)
1,918,165 cpu_core/cycles/
<not counted> cpu_atom/instructions/ (0.00%)
2,850,215 cpu_core/instructions/ # 1.49 insn per cycle
0.000717136 seconds time elapsed
0.000675000 seconds user
0.000000000 seconds sys
$ sudo perf stat -e cycles,instructions ./test qsort
Performance counter stats for './test qsort':
<not counted> cpu_atom/cycles/ (0.00%)
1,648,884 cpu_core/cycles/
<not counted> cpu_atom/instructions/ (0.00%)
2,862,565 cpu_core/instructions/ # 1.74 insn per cycle
0.000584501 seconds time elapsed
0.000000000 seconds user
0.000609000 seconds sys
```
目前尚未詳細分析兩者的效能差異，後續將進一步探討如何進行合理的比較，並補充更詳細的測試與分析結果。
## 第 2 週測驗二
### 程式碼運作原理分析
此測驗涉及 `clz`（counting leading zero）和整數開平方根 `sqrti` 的實作。
#### `clz` 分析
`clz` 的目標是計算數值的 leading zeros 的數量。實作方法是將數值拆分為上半部（upper）與下半部（lower），並根據以下邏輯進行遞迴計算：
• 若 `upper` 為零，則遞迴計算 `lower` 的 leading zero，並加上 `upper` 佔據的位數。
• 若 `upper` 不為零，則遞迴計算 `upper` 的 leading zero。
**思路**
由於遞迴的流程較難直觀理解，因此我先找出**初始條件與遞迴結束條件**。
- if (c == JJJJ) 條件下並未進行遞迴呼叫，推測這是遞迴終止的條件。
- c + 1 會在每次遞迴時遞增，當 c == 3 時應該要終止，否則可能導致超出陣列範圍存取錯誤。
```c
if (c == JJJJ)
return upper ? magic[upper] : KKKK + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
```
根據巨集定義 `#define clz32(x) clz2(x, 0)`，推測 `x` 為目標數值，而 `c` 則記錄目前處理的階段。
- `c == 0` 時，處理 32 位元數值
- `c == 1` 時，處理 16 位元數值
- `c == 2` 時，處理 8 位元數值
- `c == 3` 時，處理 4 位元數值
**逐行分析 `clz2`**
```c=
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);
}
```
- 第 9 行：`upper` 取得 `x` 的上半部位元。
- 第 10 行：`lower` 取得 `x` 的下半部位元，其中 `0xFFFF` 是 16 位的遮罩，前 16 位為 0，後 16 位為 1，透過 `mask[c]` 決定要保留的位數。當 `c` 為 3 時，應該要留下末兩位元，因此 `mask[3]` 為 14。
- 當 `c == 3`（處理 4 位元）時，`magic[]` 儲存 **2 位元對應的 leading zero 數量**，因此：
- `magic[] = {2, 1, 0, 0}`
- 當 `upper != 0`，回傳 `magic[upper]`
- 當 `upper == 0`，leading zero 為 `upper` 的 2 位元加上 `magic[lower]`
| 題目 | 答案 |
| -------- | -------- |
GGGG| 14
HHHH| 2
IIII| 0
JJJJ| 3
KKKK| 2
LLLL| 1
#### `sqrti` 分析
參考：[從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt#Digit-by-digit-Method)
**理論分析**
設 $N$ 為正整數，目標是求出 $N$ 的平方根值（以整數表示）。
$$
\begin{align}
N&=(b_n\times2^n+b_{n-1}\times2^{n-1}+...+b_0\times2^0)^2 \\
&=(a_n+a_{n-1}+...+a_0)^2
\end{align}
$$
其中，$b_i=0$ or $1,\ i=1,\ 2,...,\ n$、$a_i=b_i\times2^i$。
假設最高位為非零元素為第 k 位，亦即，$b_i=0,$ for $i>k$。我們有
$$a_k=2^k>\sum_{i=0}^{k-1}a_i=2^k-1$$
又對於任何 $x\geq2$，$x^2\geq2x$。於是對於第一個 $a_k^2\leq N$，必須把 $b_k$ 設成 $1$。否則就算把第 k 位以下都設成 $1$，對於估計 $\sqrt N$ 還是太小。我認為這是一個不嚴謹但相對直觀的解釋，搭配實作可以很好的幫助理解。
因此演算法可以以這個方法實作
1. 從最高位 $n$ 開始檢查，直到找到第一個 $a_k^2\leq N$，則把 $b_k$ 設成 $1$。
2. 接者，若 $\left(a_k+a_{k-1}\right)^2\leq N$，則把 $b_{k-1}$ 設為 $1$，反之設為 $0$。設 $P_m=\sum_{i=m+1}^na_i$，因為 $a_i$ 在第 $k$ 位以上都是 $0$，也可以簡化為 $P_m=\sum_{i=m+1}^{k}a_i$，以現階段為例就是 $P_{k-2}=\sum_{i=k-1}^{k}a_i=a_k+a_{k-1}$。
3. 計算 $P_{k-3}^2=\left(a_k+a_{k-1}+a_{k-2}\right)^2$，並和 $N$ 比較，若 $P_{k-3}^2\leq N$，則把 $b_{k-2}$ 設為 $1$，反之設為 $0$。
4. 以此類推直到計算到 $P_0$，最終結果 $\sqrt N$ 可以用 $(b_kb_{k-1}...b_0)_2$ 來估計。
定義 $X_m=N-P_m^2$ 為實際值和逼近值的誤差，其中 $Y_m=(2P_{m+1}+a_m)a_m$，可以縮減計算過程。
1. $X_m=N-P_m^2=X_{m+1}-Y_m$
2. $Y_m=P_m^2-P_{m+1}^2=(2P_{m+1}+a_m)a_m$
**實作**
```c
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
此程式碼可以直接對應到上述理論。`m = 1ULL << shift` 是將初始的 $P_n$ 設定為 $a_n$。若 `y` 記錄 $P_m$，`b = y + m`為 $P_{m-1}$。不斷重複計算直到 $P_0$。
| 題目 | 答案 |
| -------- | -------- |
MMMM| `~1`
NNNN| `1`
PPPP| `2`
### 實作：開平方根向上取整 $\left\lceil \sqrt N\right\rceil$
我一開始打算往數學的方式思考。正如前面提到的，此實作會比較 $P_m^2$ 和 $N$ 的大小，若小於 $N$ 則加入。但如果要做向上取整就比較困難，向上取整代表勢必需要 $P_m^2\geq N$，但很難知道到底需要大多少。於是我認為這個方向行不通。
我改成從實作著眼，若非完全平方數則需要加 $1$，完全平方數則不需要。我的思路轉為去思考**完全平方數和非完全平方數的差別**。從理論思考，我猜測在迴圈結束的時候，若為完全平方數 `x` 應該要為 $0$。於是我做了初步的實驗，我將 $1$ 到 $100$ 帶入，確認函式正確並且檢視函式結束時的 `x` 值。發現結果和我猜測的一樣：
```
x: 1, N: 2, sqrt(N): 1
x: 2, N: 3, sqrt(N): 1
x: 0, N: 4, sqrt(N): 2
x: 1, N: 5, sqrt(N): 2
x: 2, N: 6, sqrt(N): 2
x: 3, N: 7, sqrt(N): 2
x: 4, N: 8, sqrt(N): 2
x: 0, N: 9, sqrt(N): 3
x: 1, N: 10, sqrt(N): 3
x: 2, N: 11, sqrt(N): 3
x: 3, N: 12, sqrt(N): 3
x: 4, N: 13, sqrt(N): 3
x: 5, N: 14, sqrt(N): 3
x: 6, N: 15, sqrt(N): 3
x: 0, N: 16, sqrt(N): 4
x: 1, N: 17, sqrt(N): 4
x: 2, N: 18, sqrt(N): 4
```
但我認為在接近無號整數最大值附近會出問題於是我在 `sqrti` 的最後加了一行 `assert(x == 0)`，並只傳入完全平方數。測試函式如下：
```c
for (int i = 0; i < 65536; ++i) {
sqrti(i*i)
}
```
但是 assert 報錯了，我目前測試到 $2^{15}$ 都沒有問題，還沒找到最小會報錯的數字，原因要進一步分析。至少確定在 $N<2^{30}$ 要實作 $\left\lceil \sqrt N\right\rceil$ 僅需要在 `sqrti` 函式的最後加上：
```
if (x != 0)
++y;
```
### 實作：不依賴除法的浮點數開平方根 `sqrtf`
### 實作：藉由查表的平方根運算
## 第 2 週測驗三
此測驗涉及雜湊表（hash table）的實作，並在發生雜湊碰撞（hash collision）時，將碰撞的兩個值用鏈結串列的方式串接起來。以下是程式碼和示意圖：
```c
struct list_head {
struct list_head *next, *prev;
};
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
```
從程式碼中可以看出，雜湊表使用的鏈結串列與一般的雙向鏈結串列稍有不同，主要有以下兩點差異：
1. **節省空間**：雜湊表的鏈結串列**不應該**頻繁需要遍歷，也不需要快速存取尾節點。因此將首節點指向前一個元素的指標 `pprev` 省略，可以節省空間。因為雜湊表在建立時會創建大量的 `hlist_head`，其中有一部分可能完全不會使用到。
2. **簡化刪除操作**：`pprev` 是指向前一個節點 `next` 屬性的指標，這使得在刪除節點時更加方便。
**Two Sum 實作**
此測驗關於 LeetCode [Two Sum](https://leetcode.com/problems/two-sum/description/)。目標是高效率（O(N)）的尋找兩個數字，使它們的和為指定數字 `n`。為了達到這個目標，會構建一個雜湊表 `ht`。當現在搜尋的數字為 `k` 時，會檢查 `ht[k]` 是否存在。如果不存在，則建立 `ht[n-k]`；若存在，則表示找到所求的組合，並從儲存的資料中取出。
因此，資料結構如下：
```c
typedef struct {
int bits;
struct hlist_head *ht;
} map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
其中 `key` 是 $n-k$ 的雜湊值，`data` 儲存相關資料（本題為索引值）。
**各個函式的運作分析**
- `map_init`：這個函式會動態配置出 `map_t` 結構的變數 `map`，並根據指定的雜湊位元數動態配置出雜湊表的首節點，管理在 `map` 內。
- ``map_add``：這個函式將傳入的 `key` 和 `data` 加入雜湊表。會先檢查這個 `key` 是否已經在雜湊表中；若不存在，則會動態配置出一個新的 `hlist_node` 空間，並管理在 `map` 中。
- ``map_deinit``：這個函式會遍歷整個雜湊表並釋放 `map_init` 和 `map_add` 所配置的記憶體。
| 題目 | 答案 |
| -------- | -------- |
AAAA| `map->bits`
BBBB| `map->bits`
CCCC| `first->pprev`
DDDD| `n->pprev`
EEEE| `n->pprev`
Sign in with Wallet
Connect another wallet