# 2024q1 Homework2 (quiz1+2)
contributed by < `Bonnnie-entre` >

## quiz1 測驗一：非遞迴的快速排序法

### stack 存在的意義是什麼？
如此藉由陣列的儲存，就能時做出非遞迴的快速排序程式碼。

實作邏輯為：將與 `pivot` 比較的結果依序放入 `index`，接著再拿出剛剛存取的 `right`(陣列中`index` 最大的內容)，繼續切分直到只存一個節點，就會開始由 `index` 高往下將節點插入至 `result` 最前端。

<br>

### 測驗分析
[測驗一](https://hackmd.io/@vax-r/linux2024-homework2)

#### 在解題時的分析步驟
* 可以先瀏覽有哪些函式
* 接著去看主要的程式碼邏輯，了解流程後，便能判斷出各個函式的功能
* 最後，再去針對函式內的用法去做分析與填空

#### 分析 `quicksort` 函式
* `max_level` 為兩倍的串列長度，原因：此變數的用途為初始化儲存與 `pivot` 比較的陣列，若為最糟情況一陣列會儲存整個串列除了 `pivot`，所以至少要大於串列長度的空間。
* `begin`、`end` 是初始化兩倍串列長度空間的陣列，用於記錄被切分的串列之第一個與最末節點的位址。
* 考慮什麼情況下 `L==R`，當第一趟的 `pivot` 切分做完時，會對大於 `pivot` 的區段接著做同樣切成 `left`, `pivot`, `right` ，直到 `right` 僅剩一個節點。之後便會進入 `else` 的邏輯裡，將該節點加入變數 `result` 中。

void quick_sort(node_t **list)
{
    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] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        
        // 這裡使用第一個與最末節點作為 L 與 R 的初始化
        // 為的是要作為切 pivot 的終節點
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            
            // 取串列的第一節點作為 pivot 
            node_t *pivot = L;
            value = pivot->value;
            
            // 由 pivot 的下一個節點依序往下與 pivot 比大小
            // 若大於 pivot 則將節點加至專門存結果 right；反之，則 left
            node_t *p = pivot->next;
            pivot->next = NULL;
            while (p) {
                node_t *n = p;
                p = CCCC;
                list_add(n->value > value ? &right : &left, n);
            }

            // 考慮順序的緣故，將 left 插入目前的 index
            // 將 pivot 插入下一個
            // 將 right 插入下下個
            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;
        } else {
            if (L)
                // 將 L 中的唯一節點插到 result 的最前端
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

#### 分析前綴為 `list_` 的函式
* `list_tail` 會返回串列最後一個節點
* `list_add` 會將節點插入串列最前

<br>

### 優化
#### 陣列 `end` 並非必要
原因：`end` 本身即為存在於 `begin[i]` 串列之尾節點，因此可以藉由呼叫 `*R = list_tail(begin[i])` 即可。

#### 若使用 Linux 核心風格 List API
* 不需要 `*L`, `*R` 參數，可以用 `list_is_singular()` 取代

<br>

## quiz1 測驗二：TimSort
[程式碼](https://github.com/Bonnie-entre/2024-linux-quiz/blob/main/quiz1_2_timsort.c)

### Timsort 的關鍵
* 透過 `find_run()` 找出排序好的連續串列 run
* 接著將從原串列中找到的已排序串列 run 合併至 `tp` 中，執行 `merge_collapse` 審查待排序的相臨三子序列的長度，以符合子序列平衡的規範，執行合併排序 `merge_at`。最後，倘若原串列中仍有未排序的元素，便會記錄在變數 `list` 裡持續處理
* 完成走訪原串列挑選排序好的 run ，邊進行排序的過程中，由於仍會有不符合平衡的子序列 `tp` 尚未完成排序，因此使用 `merge_force_collapse`

### 疑惑：
假如前面的 runs 都被合併好了，以下這段程式碼在做什麼？

struct list_head *stk0 = tp, *stk1 = stk0->prev;
    while (stk1 && stk1->prev)
        stk0 = stk0->prev, stk1 = stk1->prev;

### 優化
#### 限制 run 的數量在 2 的冪
> 在合併序列時，若 run 的數量等於或者略小於 2 的冪，效率會最高；若略大於 2 的冪，效率就會特別低。
#### 設定 minRun
> Timsort 為了使合併過程更加均衡，需要儘量控制每個 run 的長度，定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度，若長度太短，就用二分插入排序

測驗中的程式碼並未實作以上兩點，建議透過原串列的元素個數總和，求出略大於 run 數量的 2 的冪，接著再計算出 minRun 。並將邏輯實作至於函式 `find_run()` 中，使其回傳符合 minRun 數量的 run 。
<br>

## quiz2 測驗一：以 preorder/postorder 以及 inorder 建立樹
[完整程式碼](https://github.com/Bonnie-entre/2024-linux-quiz/blob/main/quiz2_1_hashtable.c)

### 解析程式碼運作
關鍵在於：可以利用 preorder 或是 postorder 得到 `root` 值，接著從 inorder 的串列中查找該 `root` 值，便能得知在 inorder 排列中 `root` 之左為樹的左分支、之右為樹的右分支。

此程式碼使租 dfs 遞迴的做法，先建立 `root` ，再去向下建立左右分支，而在建立分支時，需要注意的是要計算出正確的左右分支在 preorder/postorder 以及 inorder 排列中 index 的範圍。

### 優化
* `struct hlist_node` 中的 `pprev` 沒有必要使用 pointer of the pointer，徒增複雜與不一致容易導致錯誤。

<br>

## quiz2 測驗二：LRUCache
[完整程式碼]()

### 解析程式碼運作
本程式碼的關鍵有二：
* `hhead`：單向串列，透過計算的 `hash` 作為 index ，可以快速查找出 key 對應的 value
* `dhead`：雙向串列，為的是紀錄使用的頻率，不論是 put 或是 get 的動作都會將該節點更新至串列最初（若已存在串列中便會先移出再加至串列最初），如此當 Cache 容量達上限時，就能直接移除此串列的最末節點了

<br>

## quiz2 測驗三
[完整程式碼]

### 解析程式碼運作