2024q1 Homework2 (quiz1+2)

contributed by < st10740 >

第 1 週測驗題

測驗 1

此測驗題參考〈Optimized QuickSort — C Implementation (Non-Recursive)〉，實作非遞迴的快速排序法，然而上述提及的方法使用的資料結構為陣列，與本題使用的鏈結串列不同，故在進行分解時的處理方式不同，不過採取的非遞迴方法策略相同，都是使用堆疊 (stack) 來模擬原本的遞迴行為。

本題用來存取欲進行排序的鏈結串列節點的結構體如下：

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

一開始看到時會猜測此題使用雙向鏈結串列來實作，因為同時有指標 left 和 right，但是不清楚為什麼還有 next 指標，看了後面的實作才發現其實只有用到 next ，嘗試將 struct __node *left, *right; 註解掉發現還是能正常運行，因此這段程式碼的實作方式是採用單向的鏈結串列。

這就是留給學員改進的地方，真實世界的程式碼可能充斥無效或錯誤的程式碼。

快速排序方法函式 quick_sort 中有一個參數 list ，為指向欲進行排序的單向鏈結串列的指標的指標。

函式的一開始會先進行初始化，begin 和 end 用來模擬遞迴的堆疊, 分別存了第

$i$ 輪中要處理的子串列的頭尾節點位址，max_level 則為遞迴的最大深度，其值設定為

$2\times n$ 的原因與後續加入新資料到堆疊中的方式有關。

int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;

注意到程式碼關於堆疊深度的計算可能有誤。

因為一開始要排序的資料為整段串列，所以將整個串列的第一個和最後一個節點分別賦予給 begin[0] 和 end[0]。

begin[0] = *list;
end[0] = list_tail(list);

接著會進入 while 迴圈，進入迴圈的條件為 i >= 0 ，表示仍有資料在堆疊中。進入迴圈後會將 L 指標指向 begin[i] 指向的節點，將 R 指標指向 end[i] 指向的節點，當 L != R 時表示子串列中不只一個節點，即開始找子串列中的 pivot，並將串列分成兩個子串列 left 和 right，分別接比 pivot 小的節點和比 pivot 大的節點，再分別將兩個子串列資訊和 pivot 節點自成的串列資訊放入堆疊中，重複做上面步驟直到堆疊中沒有資料為止即完成排序。

每一層堆疊的實作細節如下：

首先，將串列中的第一個節點作為 pivot 並將它從串列中移出，再利用 p 指標指向原本的第二個節點，作為後續尋找要加入 left 或 right 串列的節點的指標。

node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;

將 pivot 指向 L 指向的節點：

pivot 從串列中被取出：

接著，利用 p 指標走遍串列中的節點，比較指向的節點大小與 pivot 大小，若比 pivot 小則將它取出加入到 left 串列中，若較大則加入到 right 串列中。

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

因為 1 小於 4，故將 1 加入到 left 串列中。

因為 3 小於 4，故將 3 加入到 left 串列中。

因為 5 大於 4，故將 5 加入到 right 串列中。

因為 2 小於 4，故將 2 加入到 left 串列中。

因為 7 大於 4，故將 7 加入到 right 串列中。

最後，決定好 pivot, left 和 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);

這邊可以發現到，每一輪會確定一個新的 `pivot` ，且每一輪皆會新增 2 組資料到堆疊上，串列中的每個節點都會當過一次 `pivot` ，因此 `max_level` 才會設定為 `2 * n` 。

上面的步驟是當子串列中有不只一個節點的情況，但是當串列中只剩下一個節點時會執行下面的程式碼：
```c
if (L)
    list_add(&result, L);
    i--;

這段程式碼做的事情是將該節點加入到結果串列 result 中，並移除堆疊中最上層的資料，此步驟對應到遞迴方法中的中止條件。

可以改進的地方

觀察程式碼可以發現到，每次都要把準備處理的串列中的第一個節點位址和最後一個節點位址放到堆疊中，然而因為使用的是單向鏈結串列，所以需要從頭到尾走訪過串列中每一個節點才能取得最後一個節點的位址，時間複雜度為 O(n)，若使用雙向環狀鏈結串列則只需要

$O(1)$ 的時間複雜度即可取得最後一個節點的位址，因此我將嘗試把單向鏈結串列修改成雙向環狀鏈結串列來實作。

實作方式將使用 Linux 核心風格的鏈結串列所提供的巨集 The Linux Kernel - List Management Functions。

commit bfab147

我將原先的節點結構體中的指標變數改成使用 struct list_head 來實作雙向環狀鏈結串列。

typedef struct __node {
-    struct __node *left, *right;
-    struct __node *next;
+    struct list_head list;
    long value;
} node_t;

使用 Linux 核心風格的鏈結串列的好處是，我可以直接利用 list->next 找到串列中的第一個節點，再利用 list->prev 找到串列的最後一個節點，就不需要像原本的方法一樣利用兩個堆疊分別紀錄第一個節點和最後一個節點的位址，只需要紀錄 list 的位址，節省了記憶體空間。

- node_t *begin[max_level], *end[max_level];
+ struct list_head *heads[max_level];

- begin[0] = *list;
- end[0] = list_tail(list);
+ heads[0] = *list;

使用雙向鏈結串列相對原本的方法比較麻煩的是，需要建立額外一個 struct list_head 節點用以連接整個串列，且 pivot 也需要建立新節點，其中 list_new 方法用來動態配置新的記憶體空間給新節點，不再使用時要記得釋放。

- node_t *result = NULL, *left = NULL, *right = NULL;
+ struct list_head *result = list_new();
+ struct list_head *left = list_new();
+ struct list_head *right = list_new();
+ struct list_head *pivot = list_new();

最後，當把接下來要處理的各個子串列中的頭尾節點位址放到堆疊後，需要將 left、right 和 pivot 指標指向新配置的記憶體空間，再進行之後的步驟。

- 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);
+ heads[i] = left;
+ heads[i + 1] = pivot;
+ heads[i + 2] = right;

- left = right = NULL;
+ left = list_new();
+ right = list_new();
+ pivot = list_new();

提出可避免最差狀況的快速排序實作

測驗 2

Timsort 結合合併排序和插入排序，採用 bottom-up 的方法進行排序，使其平均與最差情況下的時間複雜度皆能達到

$O(nlogn)$，並且為穩定排序方法，該方法特別適用於部份已排序好的資料，該情境為 Tim Peter 觀察到在現實世界中常見的資料分佈情況。

其策略為不斷從資料中找尋已排序好的子序列作為一個 run，並將新建立的 run 放到堆疊中，過程中會針對堆疊頂端的幾個 run 進行比較並在適當時機將兩兩 run 進行合併，等到 run 都被建立放到堆疊後，會將所有的 run 都合併在一起，其結果即為排序好的資料。

因此以下將探討 Timsort 如何透過幾項操作來加快合併的過程與次數︰

1. 如何建立 run
2. 何時將堆疊中的兩兩 run 進行合併
3. 如何將所有的 run 合併在一起

本測驗題的資料儲存於 Linux 風格的鏈結串列中。stk_size 紀錄 run 的數目，tp 為存放 run 的堆疊。一開始會將輸入的 head 雙向環狀鏈結串列轉為單向且非環狀的串列，接著會掃過整個串列，利用 find_run 建立 run，並將新建立的 run 放入 tp 堆疊中，放入後再透過 merge_collapse 決定是否針對頂端的 run 進行合併，此過程會進行到掃過整個串列並建立完 run 為止。

stk_size = 0;

struct list_head *list = head->next, *tp = NULL;
if (head == head->prev)
    return;

/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;

do {
    /* Find next run */
    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);

find_run 用以建立 list 中的一個 run，假設最終目標是希望將資料從小排到大，則在建立 run 的過程中如果遇到從大排到小的子序列，會將其先進行翻轉再放到堆疊中。此函式回傳值的型別為 struct pair，該結構體的成員 head 和 next 分別接找到的 run 以及 list 中剩下的鏈結串列，最後會將 head 放入堆疊中。

藉由以下串列為例，說明 find_run 如何找到子串列 4, 3, 2，並將其翻轉成 2, 3, 4 做為一個 run。

一開始 head 會指到 list 指到的節點，而 next 則會指到 list->next 指到的節點。

最後，子串列 4, 3, 2 被翻轉為 2, 3, 4 作為一個 run，list 和 head 皆指到新建立的 run 中的第一個節點，此 run 中的節點透過 next 串接起來，而第一個節點的 prev 指向 NULL，第二個節點的 prev 則用來紀錄此 run 中的節點數目。

接著透過 find_run 找到的 run 會被放到 tp 堆疊中，堆疊中的 run 透過 prev 串接起來，再利用 merge_collapse 方法決定是否進行合併，以及合併的 run 為何。

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;
}

根據 Timsort 原文 的說法：

We would like to delay merging as long as possible in order to exploit patterns that may come up later, but we like even more to do merging as soon as possible to exploit that the run just found is still high in the memory hierarchy. We also can't delay merging "too long" because it consumes memory to remember the runs that are still unmerged, and the stack has a fixed size.

Tim Peters 希望合併能盡量越晚進行越好，因為可以利用其中的特定模式來降低合併成本，但同時也希望不要太晚進行，以確保 run 仍在較高的記憶體階層，因此他想到以下的妥協方案：

假設有三個以上的 run， A, B, C 分別是堆疊中最上面的三個由下到上的 run 的長度，必須確保不破壞以下條件：

1. A > B + C
2. B > C

當第一個條件被破壞時，會先比較 A 和 C 的大小，再將長度較短的 run 和 B 合併，不能將 A 和 C 合併的原因是 Timsort 是穩定排序法，所以只能合併相鄰的 run；當第二個條件被破壞時，會將 B 和 C 合併。若合併後的堆疊仍破壞以上條件，則會繼續進行合併直到符合條件為止。

第一個條件確保從堆疊上到下的 run 長度成長速度至少與費波那契數 (Fibonacci sequence) 一樣快，第二個條件確保從堆疊上到下的 run 長度為遞增，這樣可以使堆疊中的元素數量維持在一個範圍之內，不會過多。另外，透過每次放新的 run 到堆疊時便先檢查是否進行合併的方式也可以確保合併不會太晚進行。

本測驗題的 merge_collapse 方法除了確保不破壞上述條件外，也有針對四個以上的 run 進行處理，假設 A, B, C, D 分別是堆疊中最上面的四個由下到上的 run 的長度，則必須確保不破壞 A > B + C 和 B > C + D 的條件，若被破壞則比較 B 和 D 的大小，再將長度較短的 run 和 C 合併。參考了 Timsort 研究與對 Linux 核心貢獻嘗試 了解到加入該條件的原因是，在某些情況下，雖然堆疊中最上面的三個 run 不會破壞一開始的條件，使得合併行為結束，但是再往下看會發現接下來的三個 run 會破壞該條件，而透過加入處理四個 run 的條件能確保所有 run 都符合預期的結果。

當掃過全部資料並建立完 run 放入堆疊後，會利用 merge_force_collapse 將剩餘還沒有被合併的 run 合併在一起。

/* End of input; merge together all the runs. */
tp = merge_force_collapse(priv, cmp, tp);

merge_force_collapse 合併的方法一樣會看堆疊中最上面的三個 run 的長度，先比較 A 和 C 的大小，再將長度較小的 run 和 B 合併，此合併過程會一直持續到堆疊中的 run 數量小於 3 為止。

static struct list_head *merge_force_collapse(void *priv,
                                              list_cmp_func_t cmp,
                                              struct list_head *tp)
{
    while (stk_size >= 3) {
        if (run_size(tp->prev->prev) < run_size(tp)) {
            tp->prev = merge_at(priv, cmp, tp->prev);
        } else {
            tp = merge_at(priv, cmp, tp);
        }
    }
    return tp;
}

最後，因為 run 中的節點都只由 next 連接起來，所以需要再把 prev 連接回去，此步驟分成兩種情況，當只剩下一個 run 時，只需要利用 build_prev_link 把 prev 建立起來，但是當有兩個 run 時，需要利用 merge_final 將 run 進行最後的合併，再把 prev 建立起來。

/* The final merge; rebuild prev links */
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
    stk0 = stk0->prev, stk1 = stk1->prev;
if (stk_size <= 1) {
    build_prev_link(head, head, stk0);
    return;
}
merge_final(priv, cmp, head, stk1, stk0);

改進方案

以上實作的 Timsort 方法沒有針對 run 的長度設定最小值，即 minrun，當資料的值為隨機時，會造成每個 run 的長度都很小，需要較多的合併次數。因此我將參照原始 Timsort 的作法加入 minrun 的機制，這個做法的好處是當資料為隨機時，建立的 run 長度基本上都會等於 minrun，使得合併可以很平衡。

---

第 2 週測驗題

測驗 1

本測驗題的目標是給定一棵二元樹 (binary tree) 的前序 (preorder) 和 中序 (inorder) 遍歷結果，並重建這棵樹。

運用到的原理如題目描述：

由前序可知哪個節點在上面 (越前面的越上面)、而由中序可知哪個節點靠左(越前面的越左邊)，於是可得知前序的第一個元素一定是 root 的值，且該元素對應到中序後，左邊的值就在左邊，右邊的值就在右邊。
接著就將 left 和 right 分別當作新的 root node 下去做即可。遞迴的中止條件是在 inorder 中找不到對應元素。

因此步驟是先找到前序中的第一個元素作為當前子樹的樹根節點 (root)，並將它對應到中序中的位置，該位置左半邊的元素就構成該節點的左子樹，右半邊的元素構成該節點的右子樹，再分別把左右半邊元素下去做遞迴將更下方的子樹節點位置建立起來。

我們可以發現到，在把前序取得的元素對應到中序的位置時需要透過搜尋的方式，若採用線性搜尋法 (Linear Search) 來實作速度會太慢，因為每個元素都需要在中序中搜尋過一遍，假設元素個數為

$n$，則需要

$O(n^2)$ 的時間複雜度才能完成，因此此測驗題採用雜湊表 (hash table) 的方式存中序各元素的元素值和索引值，期望可以將搜尋的時間複雜度降低到

$O(1)$，將整體演算法的時間複雜度降低到

$O(n)$。

本題使用的雜湊表實作方法取自 Linux 核心，struct hlist_head 作為雜湊表的 bucket，hlist_node 作為雜湊表中發生碰撞 (collision) 時存的鏈結串列的節點。

根據 〈内核基础设施——hlist_head/hlist_node结构解析〉 的說法，選用 hlist_head 而不是使用 Linux 核心本身有的 list_head 作為鏈結串列 head 的原因是，list_head 需要多存一個指標指向串列的最後一個節點，當 bucket 數多的時候會需要較大的空間，且通常雜湊表若設計地好，鏈結串列通常不會太長，較不需要多存最後一個節點的位址。

struct hlist_node {
    struct hlist_node *next, **pprev;
};
struct hlist_head {
    struct hlist_node *first;
};

此外，就如同 list_head 的用法一樣，可以將 hlist_node 鑲嵌到其他結構體中，協助串連節點。order_node 為此題雜湊表中的鏈結串列節點，用來存中序的元素值和索引值。

struct order_node {
    struct hlist_node node;
    int val;
    int idx;
};

TreeNode 為最後建立的二元樹的節點結構體。

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};

主要用於建立二元樹的程式碼如下：

參數分別傳入前序和中序的陣列以及兩者陣列的長度。第 6 到第 8 行用於建立雜湊表，並初始化 bucket，bucket 的大小設定為中序元素數目。第 9 到第 10 行將中序中所有的元素值和索引值加入到雜湊表中，插入到的位置寫於 node_add 中 int hash = (val < 0 ? -val : val) % size; ，為元素值取絕對值除以中序元素數目的餘數。第 12, 13 行利用 dfs 遞迴函式一層層建立出二元樹。

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);
}

在函式 dfs 中，pre_low 和 pre_high 圍住的範圍為本輪 preorder 陣列包含的範圍（開區間），in_low 和 in_high 同理，故將 in_low > in_high || pre_low > pre_high 作為終止條件。第 14 行拿前序的第一個數值作為本輪的樹根節點，第十五行搜尋該節點對應到中序的索引值為何，有了索引值之後就可以分別將前序和中序切成左右子樹兩半部，繼續丟入遞迴執行，即第16行和第18行。

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;
}

完整測試程式