2024q1 Homework2 (quiz1+2)

contributed by < 96121503 >

第一週測驗題

測驗1

題目
作業要求

延伸問題：

解釋上述程式碼的運作原理，提出改進方案並予以實作。
使用 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 來追蹤每個階段的起始和結束節點。

node_t *begin[max_level], *end[max_level];

4. 進入 while 迴圈，處理每個階段直到所有階段處理完畢。
5. 在每個階段中，從 begin[i] 到 end[i] 之間的範圍進行分割。
6. 選擇 L（左邊界）作為 pivot，將所有小於pivot的元素移至 left 序列，大於等於的元素移至 right 序列。
7. 更新 begin[i]、end[i]、begin[i+1]、end[i+1]、begin[i+2]、end[i+2]，準備用於處理下一階段的 pivot 和左右子序列。
8. 遞迴處理子序列，直到所有子序列都排序完畢。
9. 將排序後的列表重新連接起來。

    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

題目要求

延伸問題：

解釋上述程式碼的運作原理，提出改進方案並予以實作。
將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。

Timsort 演算法：通過查找已經排好序的數據子序列，在此基礎上對剩餘部分更有效地排序。 該算法通過不斷地將特定子序列（稱為一個 run）與現有的 run 合併，直到滿足某些條件為止來達成的更有效的排序。

Timsort 改進的部分：

1. 加快合併（merge）過程
2. 減少進行合併的次數
3. 在某些特定情況下，尋找比合併排序更有效的排序方法

效率因素
合併序列時，若 run 的數量等於或者略小於 2 的冪，效率會最高；若略大於 2 的冪，效率就會特別低。需要儘量控制每個 run 的長度，定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度

Timsort 相較於合併排序，有以下改善。
降低 cache miss: 當在快取訪問不存在的數據時會產生 cache miss，導致程式執行時間變慢，通常會採取一些策略，如提前下載相鄰的數據至快取、提高快取命中率。

Timsort 結合了合併排序（Merge Sort）和插入排序（Insertion Sort），程式碼原理如下：

run_size 用來計算遞增序列的長度

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 序列）

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之前）。

if (cmp(priv, a, b) <= 0)

將指向合併後序列的尾部的 tail 指標指向 a，讓 a 添加到合併後的序列中，然後更新 tail 指向下一個元素的指標，且移動 a 指標到下一個元素，為下一輪做準備。

            *tail = a;
            tail = &a->next;
            a = a->next;

如果 a 為 NULL，代表 a 序列已經造訪完，將 b 接到剛做完的序列並退出

            if (!a) {
                *tail = b;
                break;

如果 if-else 條件式不成立，則是b排在a之前，與上述程式碼是相對應的，把 b 放置在前，最後返回合併後序列的 head 指標位置。

建立環狀雙向鏈結串列
使用 build_prev_link 建立環狀雙向鏈結串列

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 函式比較相鄰節點的值(用以下條件式判斷)，找到遞增的子序列，同時計算遞增序列的長度。

if (cmp(priv, list, next) > 0)

如果 list > next ，代表遞減排序，需要將其反轉，若是遞增排序則不須反轉，只需要訪問各節點即可，反轉的實作把原本指向下一個節點的指針改為指向上一個節點，即將 list 的 next 指標指派為 prev，並計算序列的長度。

        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 接到合併後序列的尾端。

第二週測驗題

題目

測驗 1

題目要求

延伸問題:

解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
在 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。

struct order_node {
    struct hlist_node node;
    int val;
    int idx;
};
struct hlist_head {
    struct hlist_node *first;
};

接著定義了幾個輔助函式來操作，例如 INIT_HLIST_HEAD 用於初始化雜湊表頭部，hlist_add_head 用於將節點添加到雜湊表中。

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，根據前序遍歷和中序遍歷的結果來建立二元樹。在這個過程中，使用雜湊表來快速找到中序遍歷中某個值的索引位置。

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 函式建立二元樹，最後返回建構好的二元樹的根節點。

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