HackMD
2024q1 Homework2 (quiz1+2)
contributed by < Dainel-0224 >
第一周測驗題
測驗一
不用列出參考題解，專注於程式碼和你的洞見。
避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。
主要想法是先利用 L 與 R 決定出串列的頭尾，再以串列中的第一個節點作為 pivot，然後 pivot->next 逐一走訪串列，判斷節點和 pivot 之間的大小關係，以 pivot 為中心分成 left 串列及 right 串列，而 begin 與 end 這兩個陣列會新增紀錄三個子串列的開頭與結尾。
接下來以此串列為例：
首先在 while 中將 L 及 R 指向最上層堆疊串列的頭和尾，並以串列起始當作 pivot。
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;
指標 n 會走訪每個節點判斷 n->value 及 pivot->value 之間的大小關係，將大於 pivot->value 的點放入 right 中，小於的放入 left。
while (p) {
node_t *n = p;
p = p->next;
list_add(n->value > value ? &right : &left, n);
}
再用 begin[] 與 end[] 作為堆疊，用來紀錄子串列的比較範圍，子串列節點的值越小就會越早被放入堆疊。i +＝ 2 是為了先從最上層堆疊開始處理，以舉例來看就是從 right 子串列繼續迭代。
begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);
left = right = NULL;
i += 2;
最終将形成如下所示的堆叠
由於 L=R，將節點新增入 Result 串列中。
else {
if (L)
list_add(&result, L);
i--;
}
可以改進的地方
我注意到可以改進的地方如下：
max_length的大小pivot的挑選
測驗二
不用列出參考題解，專注於程式碼和你的洞見。
Timsort 原理
在現實世界中，許多資料往往是由一些已經部分排序的串列組合而成，於是 Timsort 的策略是首先識別出資料中已排序的子序列 (這些子序列稱為 run），然後透過不斷合併這些 run 來達成全資料範圍的排序。
首先要透過以下程式碼將 doubly-linked list 轉變成 singly-linked list。
head->prev->next = NULL;
接下來這段程式碼將已排序的資料分成一個一個 run，而 tp 會指向最上層推疊的 run。
do {
struct pair result = find_run(priv, list, cmp);
result.head->prev = tp;
tp = result.head;
list = result.next;
stk_size++;
tp = merge_collapse(priv, cmp, tp);
} while (list);
每個 run 的元素個數在 find_run 程式碼所示，存放在 head->next->prev 中。
head->prev = NULL;
head->next->prev = (struct list_head *) len;
之後再呼叫 merge_collapse 檢查堆疊前三個 run 是否滿足:
- A 的長度要大於 B 和 C 的長度總和。
- B 的長度要大於 C 的長度。
並在以下情況進行合併
A <= B+C && A < C則AB合併A <= B+C && A >= C則BC合併B <= C則BC合併
直到所剩的堆疊小於三個，或是長度不滿足上述關係後，才進行統一合併。
最後透過 build_prev_link 恢復成雙向串列。
static struct list_head *merge_collapse(void *priv,
list_cmp_func_t cmp,
struct list_head *tp)
{
int n;
while ((n = stk_size) >= 2) {
if ((n >= 3 &&
run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
(n >= 4 && run_size(tp->prev->prev->prev) <=
run_size(tp->prev->prev) + run_size(tp->prev))) {
if (run_size(tp->prev->prev) < run_size(tp)) {
tp->prev = merge_at(priv, cmp, tp->prev);
} else {
tp = merge_at(priv, cmp, tp);
}
} else if (run_size(tp->prev) <= run_size(tp)) {
tp = merge_at(priv, cmp, tp);
} else {
break;
}
}
return tp;
}
可以改進的地方
我注意到可以改進的地方如下：
- 在
find_run中設計minrun使得串列分割成 2 的冪。 - Galloping mode 的實作，為了降低記憶體開銷及減少比較次數。
期待你的程式碼。
第二周測驗題
測驗一
一開始看到
struct hlist_node {
struct hlist_node *next, **pprev;
};
你是文明人，不該「蠻」
好奇為什麽這裡的 node 結構跟之前看到的雙向鏈結串列不同，在閱讀完〈Linux 核心的 hash table 實作〉後，了解這樣設計的好處是，當要刪除的節點是首個節點，即可藉由 *pprev = next 直接修改指標的指向，並且不用再將 list_head 傳遞給函式。
首先建立 inorder hash table ，然後呼叫 dfs 來建出 binary tree。
static struct TreeNode *buildTree(int *preorder,
int preorderSize,
int *inorder,
int inorderSize)
{
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);
}
DFS
首先以前序的第一個節點當作樹根，再呼叫 find 找出他在 hash table 中的索引，然後在遞迴尋找左子樹和右子樹。
將左子樹的範圍設置為 (pre_low + 1, pre_low + (idx - in_low))，這是因為左子樹的大小是由中序走訪串列中該節點的索引位置決定的。
將右子樹的範圍設置為 (pre_high - (in_high - idx - 1), pre_high)，這是因為右子樹的大小也是由中序走訪串列中該節點的索引位置決定的。
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;
}
