# 2024q1 Homework2 (quiz1+2)
contributed by < `96121503` >
## 第一週測驗題
### 測驗1
[題目](https://hackmd.io/@sysprog/linux2024-quiz1)
**作業要求**
:::success
延伸問題：
解釋上述程式碼的運作原理，提出改進方案並予以實作。
使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
:::
最初在 wikipedia 中的 quicksort 方法是使用 L 和 R 各別與 pivot 比大小，若找到一組比 pivot 大和比 pivot 小的元素就會交換兩者指向的數字，直到 L 不小於等於 R
>使用 swap 與 sort 函式
在將序列分割為兩個部分後，將 pivot 與 L 所指向的元素交換，確定 pivot 在正確位置。
使用**遞迴**方式對 piovt 左右的兩個部分進行排序。整個排序過程通過不斷地選擇新的 pivot 並分割子序列，最終實現了整體排序。
**文章作者對此進行修改**
與上述提及的流程相同，將左右兩部分分別作為新的子序列後，繼續排序，遞迴過程中使用 i 變量來跟蹤當前遞迴的深度，並使用 MAX_LEVELS 來限制最大遞迴深度。
**題目使用的方法**
以下是程式碼的主要原理：
1. 獲取列表的長度（n）以及初始化變數。
2. 使用兩個陣列 `begin` 和 `end` 來追蹤每個階段的起始和結束節點。
```c
node_t *begin[max_level], *end[max_level];
```
4. 進入 while 迴圈，處理每個階段直到所有階段處理完畢。
5. 在每個階段中，從 `begin[i]` 到 `end[i]` 之間的範圍進行分割。
7. 選擇 `L`（左邊界）作為 pivot，將所有小於pivot的元素移至 `left` 序列，大於等於的元素移至 `right` 序列。
8. 更新 `begin[i]`、`end[i]`、`begin[i+1]`、`end[i+1]`、`begin[i+2]`、`end[i+2]`，準備用於處理下一階段的 pivot 和左右子序列。
10. 遞迴處理子序列，直到所有子序列都排序完畢。
12. 將排序後的列表重新連接起來。
```c
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;
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = tail->next;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = head->prev;
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
(待完成)
使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
### 測驗2
**題目要求**
:::success
延伸問題：
解釋上述程式碼的運作原理，提出改進方案並予以實作。
將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。
:::
Timsort 演算法：通過查找已經排好序的數據子序列，在此基礎上對剩餘部分更有效地排序。 該算法通過不斷地將特定子序列（稱為一個 run）與現有的 run 合併，直到滿足某些條件為止來達成的更有效的排序。
Timsort 改進的部分：
1. 加快合併（merge）過程
1. 減少進行合併的次數
1. 在某些特定情況下，尋找比合併排序更有效的排序方法
**效率因素**
合併序列時，若 run 的數量等於或者略小於 2 的冪，效率會最高；若略大於 2 的冪，效率就會特別低。需要儘量控制每個 run 的長度，定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度
Timsort 相較於合併排序，有以下改善。
降低 cache miss: 當在快取訪問不存在的數據時會產生 cache miss，導致程式執行時間變慢，通常會採取一些策略，如提前下載相鄰的數據至快取、提高快取命中率。
Timsort 結合了合併排序（Merge Sort）和插入排序（Insertion Sort），程式碼原理如下：
**run_size 用來計算遞增序列的長度**
```c
static inline size_t run_size(struct list_head *head)
{
if (!head)
return 0;
if (!head->next)
return 1;
return (size_t) (head->next->prev);
}
```
**合併 a 與 b 序列實作**
merge 函式：用來合併兩個已排序的兩個序列（即 a, b 序列）
```c
static struct list_head *merge(void *priv,
list_cmp_func_t cmp,
struct list_head *a,
struct list_head *b)
```
使用 cmp 函數來比較 a 和 b 之間的順序。如果 a 應該排在 b 之前或與其相等（<= 0 成立代表a應該排在b之前）。
```c
if (cmp(priv, a, b) <= 0)
```
將指向合併後序列的尾部的 tail 指標指向 a，讓 a 添加到合併後的序列中，然後更新 tail 指向下一個元素的指標，且移動 a 指標到下一個元素，為下一輪做準備。
```c
*tail = a;
tail = &a->next;
a = a->next;
```
如果 a 為 NULL，代表 a 序列已經造訪完，將 b 接到剛做完的序列並退出
```c
if (!a) {
*tail = b;
break;
```
如果 if-else 條件式不成立，則是b排在a之前，與上述程式碼是相對應的，把 b 放置在前，最後返回合併後序列的 head 指標位置。
**建立環狀雙向鏈結串列**
使用 build_prev_link 建立環狀雙向鏈結串列
```c
static void build_prev_link(struct list_head *head,
struct list_head *tail,
struct list_head *list)
{
tail->next = list;
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
/* The final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
```
**找下一個遞增序列**
用 find_run 找到下一個遞增序列，根據 cmp 函式比較相鄰節點的值(用以下條件式判斷)，找到遞增的子序列，同時計算遞增序列的長度。
```c
if (cmp(priv, list, next) > 0)
```
如果 list > next ，代表遞減排序，需要將其反轉，若是遞增排序則不須反轉，只需要訪問各節點即可，反轉的實作把原本指向下一個節點的指針改為指向上一個節點，即將 list 的 next 指標指派為 prev，並計算序列的長度。
```c
do {
len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;
} while (next && cmp(priv, list, next) > 0);
list->next = prev;
```
**merge 和 collapse**
調用 merge_collapse() 函數將找到的運行與前一運行合併，如果需要，將多個連續的運行折疊成一個大的運行。這樣做的目的是減少合併操作的次數，提高效率。
直到列表中的所有元素都被處理後，使用merge_force_collapse() 函數強制將剩餘的運行合併成一個run。
最後合併使用 merge_final 函式，類似於 merge 函式，但是在最後合併完之後會呼叫 build_prev_link 函式，將剩餘的序列 a 或 b 接到合併後序列的尾端。
## 第二週測驗題
[題目](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 1
**題目要求**
:::success
延伸問題:
解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討
:::
根據題目內文，給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹。由圖可以得知：
輸入：前序=[3,9,20,15,7]，中序=[9,3,15,20,7]
輸出：[3,9,20,NULL,NULL,15,7]
前序與後序的關係可以得知一些資訊，如下圖
將 left 和 right 分別當作新的 root node 下去做即可。遞迴的中止條件是在 inorder 中找不到對應元素。
**解釋程式碼原理**
目的為建立二元樹，使用了雜湊表來加速尋找某個值在中序遍歷中的位置。
首先，定義了雜湊表中的節點結構 struct order_node 和雜湊表的頭部結構 struct hlist_head。
```c
struct order_node {
struct hlist_node node;
int val;
int idx;
};
struct hlist_head {
struct hlist_node *first;
};
```
接著定義了幾個輔助函式來操作，例如 INIT_HLIST_HEAD 用於初始化雜湊表頭部，hlist_add_head 用於將節點添加到雜湊表中。
```c
static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
h->first = NULL;
}
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
if (h->first)
h->first->pprev = &n->next;
n->next = AAAA;
n->pprev = &h->first;
h->first = n;
}
```
接著使用遞迴函式 dfs，根據前序遍歷和中序遍歷的結果來建立二元樹。在這個過程中，使用雜湊表來快速找到中序遍歷中某個值的索引位置。
```c
static struct TreeNode *dfs(int *preorder,
int pre_low,
int pre_high,
int *inorder,
int in_low,
int in_high,
struct hlist_head *in_heads,
int size)
{
if (in_low > in_high || pre_low > pre_high)
return NULL;
struct TreeNode *tn = malloc(sizeof(*tn));
tn->val = preorder[pre_low];
int idx = find(preorder[pre_low], size, in_heads);
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
in_low, idx - 1, in_heads, size);
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
idx + 1, in_high, in_heads, size);
return tn;
}
```
最後主函式 buildTree 負責建立二元樹。先初始化中序遍歷雜湊表，然後呼叫 dfs 函式建立二元樹，最後返回建構好的二元樹的根節點。
```c
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
for (int i = 0; i < inorderSize; i++)
INIT_HLIST_HEAD(&in_heads[i]);
for (int i = 0; i < inorderSize; i++)
node_add(inorder[i], i, inorderSize, in_heads);
return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1,
in_heads, inorderSize);
}
```
### 測驗 2
### 測驗 3
Sign in with Wallet
Connect another wallet