# 2025q1 Homework2 (quiz1+2)
contributed by < tsaiiuo >
## quiz1
### 測驗`1`
在這題所提出的資料結構如下，就是是一個標準的單向鏈結串列。
```clike
#include <stddef.h>
typedef struct list_item {
int value;
struct list_item *next;
} list_item_t;
typedef struct {
struct list_item *head;
} list_t;
```
透過 Graphviz 圖呈現大致如下。
這測驗一中主要是要實做`list_insert_before`這個函式，函式的敘述如下：
實做可以透過指標的指標與迴圈去找到放置 before 的指標，並且將此指標指向的指標改成要插入的元素，最後再將插入的元素的 next 指向 before 即可完成`list_insert_before`的功能。
```clike
static 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;
}
```
`AAAA` = &l->head (初始化第一個)
`BBBB` = before (透過迴圈尋找存放 before 的指標)
`CCCC` = &(*p)->next (指標的指標更新)
`DDDD` = item->next (將新的元素的 next 指向 before)
### 測驗`1` 延伸問題
#### 程式碼解釋
首先定義了兩個巨集
`my_assert`用來判斷回傳 error ，在程式碼中就用來盼對是否 list size 在不同操作過後是否正確， list value 是否在進行完`list_insert_before`後是否正確，若不正確的話則回傳參數 message 告訴我們哪裡出錯了。
`my_run_test`用來執行測試程式碼，如果有收到回傳的 message 則終止回傳。
函式的部分
`list_insert_before`上述介紹過。
`list_reset`用來初始化整個 list_item 分別為1~1000，並且將 next 指向 NULL。
`list_size`獲取 list 的長度。
`test_list`測試程式碼本身，透過判斷執行`list_insert_before`後 list value 和 list size 在操作後是否正確，來確認`list_insert_before`的功能是否正確。
程式運作脈絡：
呼叫巨集`test_suite`執行`test_list`，在`test_list`中執行一系列圍繞著`list_insert_before`的操作，並透過巨集`my_assert`判斷是否操作符合預期，若有問題則回傳錯誤消息; 沒有的話回傳 NULL 回傳的結果會給 result ，若 result 不等價於 NULL 代表有錯誤，則輸出錯誤資訊，反之則輸出測試通過。
#### 在現有的程式碼基礎上，撰寫合併排序操作
>[Commit 50e111c](https://github.com/tsaiiuo/lab1-c/commit/50e111c52dbfe9da9fe35098310cbe0dec6a00e0)
透過遞迴呼叫的方式撰寫合併排序，並且配合 `list_insert_before` 等先前定義好的函式，實做測試函式 `test_merge_sort` 去驗證正確性。
### 測驗`2`
這題所提出用來操作的資料結構為 block_t 如下：
```clike
typedef struct block {
size_t size;
struct block *l, *r;
} block_t;
```
就是一個實現二元搜尋樹的類資料結構。
要尋求的答案`EEEE`、`FFFF`其實也不用懂`remove_free_tree`的整個操作就可得出先觀察敘述
```clike
/* If the target node has two children, we need to find a replacement. */
if ((*node_ptr)->l && (*node_ptr)->r) {
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while (EEEE)
pred_ptr = FFFF;
....
```
可以知道這段程式碼的用意是要找到左子樹中最大的點(也就是左子樹中最右邊的點)，因此`EEEE` = (*pred_ptr) -> r 、 `FFFF` = &(*pred_ptr) -> r，這樣這個迴圈才可以不斷的向右遍歷找到答案。
### 測驗`2`延伸問題
#### 程式碼解釋
首先定義了兩個函式
`find_free_tree` 應該是個搜尋函式，會回傳指向 target 的指標，在`remove_free_tree`中有使用到回傳值被保存在 node_ptr。
`find_predecessor_free_tree`應該是個搜尋函式，用來尋找參數 node 的 in-order predecessor。
主函式
`remove_free_tree`負責移除二元搜尋樹的指定節點，並且要確保移除後樹還保持著二元搜尋樹的定義。
程式運作脈絡：
先透過`find_free_tree`取得要指向預計刪除節點的子樹主要分為三種狀況
狀況`1`：左右子樹皆有
這種情況會先透過`find_predecessor_free_tree`找到左子樹的 in-order predecessor 而`find_predecessor_free_tree`的結果也有可能為 node_ptr 的左子樹本身或 node_ptr 的左子樹有右子樹兩種情況：
若為 node_ptr 的左子樹本身，則先紀錄原先的 node_ptr 的右子樹 在這裡透過 old_right 儲存（因為接下來會透過指標的指標直接更新 node_ptr 指向的指標），接著更新 node_ptr 指向的指標的元素為 左子樹的 in-order predecessor(這裡在程式碼內是*pred_ptr)，最後再將更新完後的 node_ptr 指向的元素的右子樹指向 old_right。
若為不是 node_ptr 的左子樹本身，則原先 node_ptr 的左右子樹皆需先記錄起來，理由跟上面一樣，只是因為現在要拿來取代刪除節點不是 node_ptr 的左子樹本身，因此左子樹也須記載(會透過指標的指標直接更新 node_ptr 指向的指標的元素)為新節點做後續的左右子樹更新。
狀況`2`：左右子樹只擁有其中一個
直接將 node_ptr 指向存在的那一個的 root 的指標更新即可。
狀況`3`：左右子樹皆沒有
直接將 node_ptr 指向的指標更新為 NULL 。
#### 並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼
>[Commit cadf2b9](https://github.com/tsaiiuo/lab1-c/commit/cadf2b94c4a647fbb915d95f1763801b1af5a90f)
先將上述完整的 `remove_free_tree` 函式實做出來。
>[Commit b42eac7](https://github.com/tsaiiuo/lab1-c/commit/b42eac736c756548d68dba61da16f2192347d6df)
實做 `find_predecessor_free_tree` 和 `find_free_tree` ， `find_predecessor_free_tree` 利用二元搜尋樹的特性利用迴圈配合判斷大小即可找到目標元素， `find_free_tree` 沒有左子樹的情況回傳 NULL ; 反之，利用找到第一個左子樹並且配合迴圈找到最右邊的子樹就是答案。
>[Commit b805364](https://github.com/tsaiiuo/lab1-c/commit/b805364eacf9e01407350d2e7f0e1017e9f8741c)
撰寫相對應測試，主要利用二元搜尋樹的特性用 `inorder_traversal` 去拜訪的話會得到由小到大的元素，因為 `inorder_traversal` 的拜訪順序是 Left->Root->Right 。
### 測驗`3`
此題用來操作的資料結構 node_t 如下：
```clike
typedef struct __node {
long value;
struct list_head list;
} node_t;
```
也是具有 Linux 核心風格的 List API 的雙向鏈結串列
先看`GGGG`的答案為何，他在`rebuild_list_link`的函式中出現，就必須要了解這個函式的用途：
```clike
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 */;
}
```
可以看到這個函式的作用是在執行 quick_sort 完後要對 prev 重新鏈結，因 quick_sort 只利用 next 指標進行排序的操作。這邊迴圈的用意就是在根據節點的 next 跟節點進行 prev 的鏈結，並取在最後的時候需將最後一個節點的 next 鏈結到 head ，也須將 head 的 prev 鏈結到最後一個節點，因此`GGGG`答案是 head -> prev = prev。
接下來`HHHH` ->`KKKK`就需要了解 `quick_sort`函式的實作了，先看向程式碼，一開始先將雙向鏈結串列的結尾 head -> prev -> next = NULL 防止有循環無法中止遍歷鏈結串列， L 和 R 透過 begin[i] 儲存的起點配合`list_tal`取得結尾去宣告，並且將第一個元素宣告為 p 也就是 pivot 得簡寫，並且透過迴圈將大與 pivot value 的元素儲存在 right 這個鏈結串列上; 反之儲存在 left 這格鏈結串列上，因此可以先得知`HHHH`答案為 pivot -> value ; `IIII`答案為 n -> value 。之後根據 quick_sort 的描述可以看到將 begin[i] 更新為 left ， `JJJJ` 答案為pivot ， `KKKK` 答案為right，再執行 i +=2 進行後續的迴圈，透過這個操作可以優先對大於 pivot 的鏈結串列進行分割。在分割到 L = R 時代表分割出來只有一個元素，然後由於我們是優先對大於 pivot 的鏈結串列進行分割，因此這邊的第一個元素會是最大的元素將他與 result 鏈結串列進行連結並且更新 result 為該元素，同時執行 i- - 這樣可以讓迴圈下一次存取相較於本身的次高鏈結串列，若需分割則繼續分割，不需則執行 L = R 一樣的 result 更新，最後則可得到升序順利的鏈結串列，但此時這個鏈結串列只有維護 next 並沒有維護 prev 因此需執行 `rebuild_list_link` 去重新連結正確的 prev。
### 測驗`3`延伸問題
#### 程式碼解釋
函式：
`list_tail` 透過迴圈去尋找鏈結串列的尾巴。
`list_length` 透過 `list_for_each` 這個 API 去計算鏈結串列的長度。
`list_construct` 創建一個 value 為 n 的 node_t 並透過 `list_add` API 加進鏈結串列裡。
`list_free` 透過 `list_for_each_entry_safe` 這個 API 去釋放鏈結串列的記憶體。
`list_is_ordered` 透過 `list_for_each_entry` API 去檢測鏈結串列式經過排序的。
`shuffle` 實現 Fisher-Yates Shuffle 打亂陣列的元素。
`quick_sort` 上面已有詳細解釋。
`rebuild_list_link` 上面已有詳細解釋。
程式運作脈絡：
先使用 malloc 分配陣列的記憶體，再透過迴圈賦予值，之後執行 `shuffle` 打亂陣列的排序，接著配合迴圈去創建鏈結串列，創建完成之後執行 `quick_sort` 函式，並執行 `list_is_ordered` 去檢測是否排序正確，若正確的話則 `list_free` ; 反之 assert 會中斷程式碼。
## quiz2
### 測驗`1`
`AAAA` -> `FFFF` 是圍繞在函式 `list_quicksort` 裡面，因此須先了解該如何使用 quick_sort 並且使用 Linux 核心 API 來回答問題，程式碼本身先定義了 list_less 和 list_greater 分別保存小於 pivot 和大於 pivot 的元素， pivot 是鏈結串列的第一個點，因此 `AAAA` 答案是 `list_first_entry` ，接著需將 pivot 從原先的鏈結串列中移除，在這裡 `BBBB` 答案是 `list_del`，再來透過 `list_for_each_entry_safe` 遍歷鏈結串列並對每個元素對 pivot 的 value 比大小，將結果透過 `list_move_tail` 與 list_less 和 list_greater 分別鏈結起來，因此 `CCCC` 答案為 `list_move_tail` ，接著透過遞迴呼叫 `list_quicksort` 對 list_less 和 list_greater 做處理，最後分別透過 `list_add` `list_splice` 將 pivot 和 list_less 鏈結回 head ，最後再將 list_greater 透過 `list_splice_tail` 鏈結回尾巴，因此 `DDDD` 和 `EEEE` 答案分別為 `list_add` 、 `list_splice` ，`FFFF` 答案為 `list_splice_tail` ，這樣就有升序排序的結果。
### 測驗`1`延伸問題
#### 程式碼解釋
函式：
`cmpint` 用來比較兩個無號16位元的整數。
`getnum` 透過三個靜態變數(只會在第一次呼叫初始化一次)進行不同的乘法和算餘數，再將三個變數進行 XOR 運算，是用來生成隨機無號8位元數的。
`get_unsigned16` 16位元就是兩個 byte 因此透過兩次 `getnum` 函式配合 |= 運算可以生成一個隨機的無號16位元整數。
`random_shuffle_array` 是一個 shuffle 函數但不是用標準 Fisher–Yates 演算法實現。
`list_quicksort` 上述已有詳細描述。
程式運作脈絡：
宣告陣列，透過迴圈賦值，並執行 `random_shuffle_array` 擾亂順序，使用 `list_add_tail` 配合迴圈將陣列內的值分配給新的元素插入鏈結串列，在執行 `list_quicksort` 完後使用 `list_for_each_entry_safe` 檢查是否元素的值是正確的，主程式中間有錯誤都會透過 assert 中斷。
#### 改進 `random_shuffle_array`
1. 使用 get_unsigned16() % (i + 1) 的方式可能會引入 modulo bias，因為若隨機數生成器的值域不是 (i+1) 的整數倍，則某些值被抽到的機率會略高。
2. 從尾開始（標準 Fisher–Yates）： 每一次交換都只影響當前未固定的區間，交換過程是局部且獨立的，因此能夠證明最終的排列是均勻的。
從頭開始（forward variant）： 如果直接在原陣列上修改，交換或覆蓋的順序會使得前面產生的結果在後續迭代中再次被更改，而這就容易導致某些排列的出現機率與其他排列不同。
更改後的程式碼如下：
```clike
static inline uint16_t get_uniform_random(uint16_t n)
{
uint16_t x;
uint16_t max_usable = (UINT16_MAX / n) * n;
do {
x = get_unsigned16();
} while (x >= max_usable);
return x % n;
}
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = len - 1; i > 0; i--) {
uint16_t j = get_uniform_random(i + 1);
uint16_t tmp = operations[i];
operations[i] = operations[j];
operations[j] = tmp;
}
}
```
`get_uniform_random` 先計算 (i+1) 在最大為 UINT16_MAX 下的最大公倍數 max_usable 並且呼叫原本的 `get_unsigned16` 但多做一個檢查是是否在 0 ~ max_usable 的值域下，若是的話就 return 代表這次抽樣是公平的; 反之則重新抽取。
`random_shuffle_array` 就更改為標準的 Fisher-Yates Shuffle。
#### 為什麼 `list_for_each_entry_safe` 建構的迴圈中，若將 `list_move_tail` 換為 `list_move`，為何會無法滿足 stable sorting ?
因為 stable sorting 的定義是若兩個元素相同，那在經歷排序後他們的順序會符合原始順序。那假設我們採用 `list_move` 就會發生順序顛倒的情況。
範例：
初始狀況假設以 3 為 pivot
在執行原版`list_for_each_entry_safe` 建構的迴圈後
`list_move` 版本
雖然兩種都不影響最終數值排序的結果，但可以看到在 `list_move` 版本中排序的過程會照成順序顛倒，那在假設有元素相同的存在出現時就無法保證排序完的順序會是他們的初始順序。
### 測驗`2`
完整的程式碼：
```clike
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);
}
```
此函數要回傳前導零有多少個，並透過題目原本的敘述可以得知他要達到遞迴呼叫直到僅剩 2 位元（bits）需要檢查 leading zero ，因此這邊每一層的 upper 他是用 (x >> (16 >> c)); 來進行獲取，而這邊觀察遞迴呼叫的順序是當有 upper 時 c + 1 那可得知 c 的範圍就是0~3 ，分別用來分割 16、8、4、2 位元，並且 lower 也須透過與 mask[c] 進行 & 運算取得該取得，並且當 c = 3時應該要終止，因為分割到2位元了就可以直接查表獲取前導零。
最後透過觀察可得：
`GGGG` = 14
`HHHH` = 2 ( 00~2~ 的前導數為 2 )
`IIII` = 0 ( 11~2~ 的前導數為 0 )
`JJJJ` = 3
`KKKK` = 2 (若 upper 為零則前導數為 upper 所關注的位元數，像在這裡 c = 3 代表 upper 關注二位元)
之後 `MMMM` -> `PPPP` 在函式 `uint64_t sqrti` 裡，首先這個函式是想實做開平方根，而看向函式 (total_bits - 1 - clz64(x)) 這邊是想做取最高位 1 的位置，並且希望 shift 是 4 的冪次方因此還做了 & `MMMM` 的操作，為了達成 m 為 4 的冪次方，因此 `MMMM` 的值為 -1，因為 (-1)~2~ = 11111111 11111111 11111111 11111110~2~，這樣可以幫助他去除最低位元，這樣 m << 的操作的值只會是 2 的冪次方，而 m 又是 1ULL << 2 的冪次方的數，以數學表示為 $2^{2^k= shift}$ ，接下來就是逼近法的實作，在迴圈中 `NNNN` = 1 透過這樣在運算的結尾才會得到該 m 的平方根， `PPPP` = 2，這邊保持 m 四進位的看法下去看很直觀詳細解釋參考
> [allen chao](https://hackmd.io/@wMTPWBL3SY-hXZO6zn-QmQ/r15D-M3sJg)的解釋
在迴圈中，會將` m `加到` y `，因為最後的答案應為每次加到` y `的` m `的開根號，因此每次迴圈均會將` y `除以2，讓` y `透過位元右移對其中不同的` m `值開根號，以 x = 1000 為例
y = 0
y = 256
y = $\frac{256}{2}$ = 128
y = $\frac{256}{2}$ + 64 = 192
y = $\frac{256}{4}$ + $\frac{64}{2}$ = 96
y = $\frac{256}{4}$ + $\frac{64}{2}$ + 16 = 112
y = $\frac{256}{8}$ + $\frac{64}{4}$ + $\frac{16}{2}$ = 56
y = $\frac{256}{8}$ + $\frac{64}{4}$ + $\frac{16}{2}$ + 4 = 60
y = $\frac{256}{16}$ + $\frac{64}{8}$ + $\frac{16}{4}$ + $\frac{4}{2}$ = 30
y = $\frac{256}{16}$ + $\frac{64}{8}$ + $\frac{16}{4}$ + $\frac{4}{2}$ + 1 = 31
這也可以驗證為何一開始要找偶數位元且每次` m `要右移2位($m \div 4$)而不是1位，因為奇數位所表達的數值無法開根號為整數且$\sqrt{2}$不是整數
### 測驗`2`延伸問題
在迴圈之後加入以下判斷式即可對$\sqrt{x}$向上取整數，代表有剩下的數字，因此直接把 y ++ 即可涵蓋，達成向上取整數的效果。
```
if(x > 0){
y++;
}
```
### 測驗`3`
這題是要用 Two Sum 來帶出 hash table 的應用和實作，這邊題目所提出的資料結構如下：
```clike
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
typedef struct {
int bits;
struct hlist_head *ht;
} map_t;
struct hash_key {
int key;
void *data;
struct hlist_node node;
};
```
詳細結構設計解釋我覺得老師已經講得很清楚了，這邊直接看到題目本身，
首先先定義 `hash` 函式，這個函式是利用黃金比例 32 位元黃金比例常數 0x61C88647 與輸入的參數相乘，並保存當作哈希值。
再來看到 `find_key` 函式，這裡函式得目標是要取得輸入 key 所對應的 hashkey ，在一開始 `struct hlist_head *head = &(map->ht)[hash(key, AAAA)];` 這個操作是想獲取這個 key 所對應的哈希值的起頭，因此 `AAAA` = map->bits ，這樣才能正確獲取 map 的位元的哈希值，獲取哈希值後透過迴圈則可配合 `container_of` 獲取 hashkey 本身並回傳。
`map_get` 配合 `find_key` 回傳 key 所對應的 data。
`map_add` 用意是要新增一個 hashkey 進入相對應的 map 內， `BBBB` = maps->bits ，跟先前的 `find_key` 一樣是用來取得正確的哈希值，`CCCC` = first->pprev ，更新原先第一個元素的 pprev 為西增的元素的 next 指標， `DDDD` = n->pprev，直接指向 h->first 的記憶體位址。
`map_deinit` 這個函式是要用來釋放記憶體， `EEEE` = n->pprev ，這段程式碼是要將前一個節點的 next 指向現在要刪除節點的下一個元素，也就是把目前的元素從表上移除。
### 測驗`3`延伸問題
程式碼解析上述解釋的差不多了，剩下最後的 `two_sum` 函式：
透過一個迴圈 O(N) 的時間複雜度，透過 `map_get` 去檢查有沒有 target - 目前的陣列的值，若有則回傳這兩個數字; 沒有則透過 `map_add` 新增目前陣列的值，最後透過 `map_deinit` 釋放整個 hash map 的記憶體，回傳答案。
#### 測試程式碼
```clike
int main() {
int nums[] = {2, 6, 27, 18, 12};
int target = 24;
int returnSize;
int *result = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target, &returnSize);
if (returnSize == 2) {
printf("Answer: [%d, %d]\n", result[0], result[1]);
free(result);
} else {
printf("No answer found.\n");
}
return 0;
}
```
Sign in with Wallet
Connect another wallet