# 2024q1 Homework2 (quiz1+2)
contributed by < [ollieni](https://github.com/ollieni) >
## 第一周測驗題
### 測驗一
這題是想透過非遞迴的方式實作 quick sort。
根據參考資料: [ Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) ，作者提到想改進維基百科的做法，其中原因如下 :
1. 避免函式呼叫，因為進出函式是耗時的。
2. 不使用堆疊儲存資料，避免遞迴函數的性能慢且可能引起堆疊溢位。
3. 交換變數只在每輪中傳遞一個項目，降低效能成本。
4. 每輪中元素只移動到列表中的新位置一次，減少不必要的移動。
5. 當元素在 pivots 目的地正確一側，避免不必要的移動。
6. 避免在每輪中有50％的機會將列表中的元素與自身交換，降低性能成本。
這裡發現了一個問題，作者提到不使用堆疊儲存資料，但老師的測驗中提到"這份程式碼嘗試用堆疊模擬原本的遞迴呼叫"。
目前還沒想出這之間的關係。
本題的鏈結串列結構體如下:
```clike
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
```graphviz
digraph structs {
node[shape=record];
struct0 [label="{<node>*left|<node>*right}|<node>*next|<data>value",color=black]
rankdir=LR;
node[shape=box];
}
```
## 重新回答題目
要我們填空的程式碼如下:
首先是`list_tail()`，依據函式名稱可以推論出此函式的功能是找到鍊結串列的尾端。
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
```
可以看到 `while` 迴圈的停止條件是 `*left` 和 `(*left)->next`，其中之一為 `NULL` ，因此當 `*left` 指向尾端時，此迴圈就會停止，接著函式就會回傳 `*left` ，也就是尾端。
因此若是要找到尾端， `left = &(AAAA);` ，應為不斷往下一格移動。
所以 `AAAA` 的答案是 `(*left)->next`。
---
根據 `list_length()` 的函式名稱，我們可以得知此程式的目的是回傳鍊結串列的長度。
```c
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
依據現有的程式碼可以得知，此函式會在 `*left` 不為 `NULL` 時，持續將 `n` 加一，當 `*left` 為 `NULL` 時停止(也就達到尾端)。
因此可以推論出 `BBBB` 會讓 `*left` 持續往尾端移動。
答案為 `(*left)->next`。
---
以下程式碼為 quick sort 實作的一部份。
```c
.
.
.
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
left = right = NULL;
i += 2;
.
.
.
```
CCCC 在一個 `while` 迴圈中，這個迴圈會根據 n->value 是否大於 value，將節點 n 添加到名為 right 或 left 的鍊結串列中，此迴圈目的是在將鍊結串列依據大小分成 pivot 左右兩邊的串列。
因此需要走過每一個節點， CCCC 為 `p->next`。
begin 和 end 分別是在記錄左右兩邊串列的頭尾，因此 DDDD 應為 begin[i] 的尾端，我們可以用 `list_tail()` 來找尾端， DDDD 的答案就會是 `list_tail(left)`。
EEEE 會是 begin[i+2] 的尾端，答案會是 `list_tail(right)`。
### 測驗二
請補完 Timsort 程式碼，使其運作符合預期。
Timsort 為合併排序和插入排序的組合算法。
將數列分成數個 run (比較小的數列)以 insertion sort 將 run 裡的數字排序，再將所有 run 用 merge sort 的方式合併在一起。
分 run 時，有幾點需注意
1. run 的長度不宜超過 64，因為 insertion sort 的效果會變差
2. run 最好是二的次方， merge 合併效率才會比較好
## 第二周測驗題
### 測驗一
LeetCode [105 Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)
用前序 (preorder) 和中序 (inorder) 重構二元樹。
**Preorder Traversal 前序遍歷**:
用Depth-first Search走訪整棵樹，順序是：根、左子樹、右子樹。根排在最前面。
**Inorder Traversal 中序遍歷**:
也是採用Depth-first Search，走訪順序是：左子樹、根、右子樹。根排在中間。
#### **Key point** :
preorder 和 inorder ，可以用根的位置，用 Divide-and-Conquer 的概念，建立唯一二元樹。
在 preorder 之中，最左端一定是根節點。 inorder 中，根的兩側是左子樹和右子樹。因為子樹也是樹，可以用相同方式遞迴下去，求出整棵樹的架構。
**hlist_node**
```graphviz
digraph structs {
node[shape=record];
struct0 [label="{<node1>*next|<node2>*pprev}",color=black]
rankdir=LR;
node[shape=box];
}
```
**Tree_Node 結構**:
```graphviz
digraph structs {
node[shape=record];
struct0 [label="{<node>*left|<node>*right}|<data>val",color=black]
rankdir=LR;
node[shape=box];
}
```
**order_node 結構**:
```graphviz
digraph structs {
node[shape=record];
struct0 [label="<node>*node|<data>val|<data>idx",color=black]
rankdir=LR;
node[shape=box];
}
```
這是一個經典的問題，接下來我會以我的理解，解釋這題的程式。
函式解釋:
**find**
找出 value = num 的節點。
這個函數的目的是在 hash 串列中查找特定數值 num 的索引。
使用 hash 值計算，確保索引落在 hash 表範圍內。
透過 `hlist_for_each` 循環遍歷 hash 鏈表，並使用 `container_of` 將節點轉換為 order_node 結構。
若找到相應的數值，則返回對應的索引；否則返回 -1。
**dfs**
使用遞迴的方式做深度優先搜尋。
用於構建二元樹。
接收前序和中序走訪的區間，以及相應的 hash 串列等參數。
透過遞迴方式，根據前序遍歷的順序，建立二元樹的每個節點。
利用 `find` 函數找到中序走訪中該節點的索引，並分別遞迴建立左右子樹。
**buildTree**
使用 inorder 和 preorder 來建立一個唯一的樹。
這個函數是用於建立二元樹。
一開始配置 hash 串列的內存，並初始化每個 hash 串列。
使用前序遍歷的數組建立 hash 串列，同時調用 `dfs` 遞迴函式構建整個二元樹。
返回指向根節點的指標。
### 測驗二
程式目的 : 實作 Least Recently Used (LRU) Cache
在清除快取中的資料時，將上一次使用時間離現在最遠的資料清除。
**LRUNode 結構**：
```graphviz
digraph G {
rankdir = LR;
node [shape=record]
subgraph cluster_1 {
node [shape=record];
label="LRUNode";
hn [label="{ **pprev | *next }"];
lh [label="{ *prev | *next }"];
node1[label="{ key | value }"];
}
}
```
**LRUCache 結構**
```graphviz
digraph LRUCache {
rankdir = LR;
node [shape=record]
subgraph cluster_1 {
node [shape=record];
label="LRUCache";
node1[label="{ capacity | count }"];
lh [label="{ *prev | *next }"];
hn [label="{ hhead }"];
}
hln1 [label="{ **pprev | *next }"];
hln2 [label="{ **pprev | *next }"];
hn->hln1->hln2
}
```
函式解釋 :
**lRUCacheCreate**
創建一個空的 lRU cache ，並根據 `capacity` 配置記憶體。
**lRUCacheFree**
將 lRUCache 清空，並釋放記憶體。
使用 `list_for_each_safe` 走訪全部節點，並將結點記憶體釋放。
**lRUCacheGet**
根據 key ，從快取中取出相對應的值。
將 key 除餘 capacity ，得到 key 的 hash 值，再用 hlist_for_each走訪，若在LRUCache->hhead[hash] 的每個節點中，有找到 key 的值，將該節點放到 `obj->dhead`，也就是最前面。
**lRUCachePut**
將 key-value 放入快取中。
先查詢 key 是否存在，若存在就將其放到最前面的位置。若不存在，先檢查 cache 是否滿了，若沒滿則直接將 key-value 插入。若 cache 已滿，將最後的 key-value 刪除，並將要插入的 key-value 放到最前面。
### 測驗三
程式目的 : 找到第 n 個為1的 bit 。
**ffs** :
此函式功能為找出第一個是 1 的 bit。
其運作原理和 find_leading_zero 很相似。
```c
...
///如果最低的16位都为0，将 num 加上16，然后将 word 右移16位
if ((word & 0xffff) == 0) {
num += 16;
word >>= 16;
}
///如果最低的8位都为0，将 num 加上8，然后将 word 右移8位。
if ((word & 0xff) == 0) {
num += 8;
word >>= 8;
}
///如果最低的4位都为0，将 num 加上4，然后将 word 右移4位。
if ((word & 0xf) == 0) {
num += 4;
word >>= 4;
}
///如果最低的2位都为0，将 num 加上2，然后将 word 右移2位。
if ((word & 0x3) == 0) {
num += 2;
word >>= 2;
}
///如果最低的1位为0，将 num 加上1
if ((word & 0x1) == 0)
num += 1;
return num;
...
```
**clear_bit** :
將特定區塊的 bits 刪除。
用 `BIT_MASK(nr)` 產生一個在 nr 位置是1，其他位置皆為0的 mask ，可用於清除特定 bit。
找到包含要刪除 bit 的 word 記憶體位置的 pointer。
對pointer 用 `~mask` 做 bit-wise and 將 bit 刪除。
**fns** :
用 __ffs 去找第一個是1的 bit，用 __clear_bit 刪除，重複 n 次，即可找到第 n 個是 1 的 bit。
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet