# 2024q1 Homework2 (quiz1+2)
contributed by < [devarajabc](https://github.com/devarajabc) >

## 第一週測驗 `1`
參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)，實作非遞迴 (non-recursive; iterative) 的快速排序法

### 1.解釋上述程式碼的運作原理。

參考 [csotaku0926](csotaku0926), [chloe0919](https://hackmd.io/@Chloexyw/linux2024-homework2)
利用指標陣列 `begin` 和 `end` 來模擬堆疊
從堆疊中取出索引值對應的指標 `begin[i]` 和 `end[i]`並將值存在` L `和 `R` 之中
並將 `pivot` 設定為 `L`
> node_t *L = begin[i], *R = end[i];

示意圖如下

digraph graphname{
        node[shape=box]        
        rankdir = LR
        A[label=4]
        B[label=1]
        C[label=3]
        D[label=5]
        E[label=2]
        F[label=7]
        G[label=8]
        NULL[label=NULL,shape=plaintext]
        A->B->C->D->E->F->G->NULL
        {
            rank="same";
            L[label="L",shape=plaintext,fontcolor=red]
            pivot[label="pivot",shape=plaintext,fontcolor=blue]
            pivot->L[color=blue]
            L->A[color=red];
        }
        {
            rank="same";
            R[label="R",shape=plaintext,fontcolor=red]
            R->G[color=red];
        }
}

當 `L` 不等於 `R` 時，
將大於 pivot 的節點加入 `right` ，反之則加入 `left`

digraph{
    ## rankdir=TD 
    rankdir=LR
    node [shape=box,color=black]
    //tp [shape=none,label=pivot,fontcolor=red]
    A [shape=none,label=left]
    B [shape=none,label=right]
    C [shape=none,label=pivot,fontcolor=blue]
    C->4
    B->8->7->5
    A->2->3->1
}

接著分別用指標 `begin[i]` 和 `end[i]` 來記錄 `left` 的開頭與結尾、`begin[i+2]` 和 `end[i+2]` 來記錄 `right` 的開頭與結尾，而 `pivot` 則同時用 `begin[i+1]` 和 `end[i+1]` 來記錄
最後將堆疊的索引 `i` 更新為 `i+=2`
(取出一層又放回三層)
是意圖如下：

:::danger
改進你的漢語表達。
:::

digraph graphname{
        node[shape=box]        
        rankdir = LR
        p [shape=none,label=pivot,fontcolor=blue]
        p->4
        p1[shape=none,label="begin[i+1]",fontcolor=red]
        p1->4
        p2[shape=none,label="end[i+1]",fontcolor=red]
        p2->4
        A[label=8]
        B[label=7]
        C[label=5]
        D[label=2]
        E[label=3]
        F[label=1]
        R[label="R",shape=none,label=right]

        //NULL[label=NULL,shape=plaintext]
        right[shape=none,label="right",fontcolor=blue]
        right->A
        left[shape=none,label="left",fontcolor=blue]
        left ->D
        D->E->F
        A->B->C
        {
            rank="same";
            L[label="begin[i+2]",shape=plaintext,fontcolor=red]
            //pivot[label="pivot",shape=plaintext,fontcolor=blue]
            //pivot->L[color=blue]
            L->A[color=red];
        }
     
        {
            rank="same";
            R[label="end[i]",shape=plaintext,fontcolor=red]
            R->F[color=red];
        }
         {
            rank="same";
            L1[label="begin[i]",shape=plaintext,fontcolor=red]
            //pivot[label="pivot",shape=plaintext,fontcolor=blue]
            //pivot->L[color=blue]
            L1->D[color=red];
        }
        {
            rank="same";
            R1[label="end[i+2]",shape=plaintext,fontcolor=red]
            R1->C[color=red];
        }


}

digraph graphname{
        node[shape=box] 

subgraph cluster_0 {
          //rank="same";
          rankdir = LR;
    style=filled;
    color=lightgrey;
    node [style=filled,color=white];
    "begin[i+2]"  "begin[i+1]"  "begin[i]"  ;
    label = "begin";
  }
subgraph cluster_1 {
    //rank="same";
    rankdir = LR;
    style=filled;
    color=lightgrey;
    node [style=filled,color=white];
    "end[i+2]"  "end[i+1]"  "end[i]"  ;
    label = "end";
    
  }
}

可以想像成這樣：

digraph graphname{
        node[shape=box] 
        rankdir = LR
        node[shape=record];
    map [label="stack |begin[i+2] end[i+2]  |begin[i+1] end[i+1] |begin[i] end[i]  "];
}

反之當 `L` 等於 `R` 時，代表走訪到 pivot ，也就是「位置正確」的節點，所以使用 `list_add` 來將該節點加入 result 並將 `i--` 。

### 2.提出改進方案並予以實作
1. 選擇 povit 的方式
2. max_lengh 的大小

### 3.使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。
參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)

## 第一週測驗 `2`
Timsort 的實作，刻意不額外配置記憶體空間

### 1.解釋上述程式碼的運作原理，提出改進方案並予以實作。
參考 [jimmylu890303](https://hackmd.io/@jimmylu0303/linux2024-homework2#%E6%B8%AC%E9%A9%97%E4%BA%8C)
程式執行可以分成以下幾個階段
1. 將原本的串列的最後一個節點解除環狀佇列，並將它指向 NULL
2. 利用 find_run 將從 list 分割出一個 run ，並將該 run 的開頭的 prev 設為上一個 run 的開頭，示意圖如下 ：

digraph{
    ## rankdir=TD 
    rankdir=LR
    node [shape=box,color=black]
    tp [shape=none,label=tp,fontcolor=red]
    A [shape=none,label=Z,fontcolor=blue]
    B [shape=none,label=Y,fontcolor=blue]
    C [shape=none,label=X,fontcolor=blue]
    C->8-> 9
    B->5->6->7
    A->1->2->3->4
    8->5 [xlabel= "   tp->prev",fontcolor=red]
    {rank=same; 5;8}
    tp->8
    {rank=same; tp;8}
    5->1[xlabel= "   tp->prev->prev",fontcolor=red]
    {rank=same; 5;1}
}

> 上圖修改自 jimmylu0303

3. 當 `stk_size` >= 2 時，利用 `merge_collapse` 來保堆疊上的 run 長度保持平衡
4. 利用`merge_force_collapse` 使 ` stk_size` 長度小於 3
5. 將 linked-list 恢復成 circular doubly-linked list
6. 若` stk_size` 為 2 則需要利用 `merge_final` 合併最後兩個 run

以下是對 timsort 會用到的函式進行細部的解釋

##### `create_sample`
`space` 是指向「一大串可用且連續的記體空間」的指標，藉由 `element_t *elem = space + i` 來配置一段記體空間給 element_t 並用區域變數 `elem` 指向它，隨後使用 `rand()` 來將 `elem->val` 設成一個隨機數，最後利用`list_add_tail(&elem->list, head)`將 element_t 加入鏈接 head 。

##### `copy_list`
利用 `element_t *copy = space++` 來獲得「指向可使用的記憶體空間」的指標，並在隨後的 `list_for_each_entry` 中不斷將鏈接 `from` 中每個的 `entry` 的資訊如 val, seq 複製到該記憶體空間 ， 最後再將該記憶體空間加入鏈接 `to` 之中。

##### `compare`
比較鏈接 `a` 和鏈接 `b` 的 `val` 並輸出相減的結果，跟 `strcmp` 很像
而 `void *priv` 的功能是，窩不知道

##### `check_lis`
用來檢查是否有以下三種錯誤情況
1. Wrong order
2. unstable
3. inconsistance

#### `run_size`
一開始看不懂為何 `(size_t) (head->next->prev)` 就是 runsize ?，一直到參考了 [ HotMercury](https://hackmd.io/@NeedSleep/linux2024-homework2#-Timsort) 的解釋才知道 run 的被以指標的型態儲存在`head->next->prev` 之中，最後用 (size_t) 來轉換型態並輸出。

##### `merge`
使用逐對合併 (one-pair-at-a-time) 合併兩個單向的鏈接（ null-terminated singly-linked list ）。

`tail` 是「指向尾端的指標」的指標，並在 for loop 中不斷更新，最後回傳指向「合併好的鏈結串列 」的指標。
(TODO ： 補圖片)

##### `build_prev_link`
將單向鏈結串列恢復成雙向鏈結串列。
但我不懂最後兩行程式碼為何可以讓其回復成雙向鏈結串列

/* And the final links to make a circular doubly-linked list */
	tail->next = head;
	head->prev = tail;

##### `merge_final`
內容與 `merge` 相似
不同之處在於：
1. 使用 Parameter `head` 來當記錄「合併好的鏈結串列」
2. 在函式最後使用 `build_prev_link` 來將單向鏈結串列恢復成雙向鏈結串列
3. 輸出為 void

##### `find_run`
> 參考 [ HotMercury](https://hackmd.io/@NeedSleep/linux2024-homework2#-Timsort)

輸出為 pair ，裡面包含了兩個指標 `next` 和 `head`
`head` 為指向當前 run 的指標，而 `next` 為指向下一個 run 的指標。
在走訪鏈接的過程中會遇到以下兩種情況：
1. 遇到連續的遞減的節點 -> 計算長度 `len` 並將其反轉，直到遇到比當前節點還大的節點
2. 遇到連續的遞增的節點 -> 計算長度 `len` ，直到遇到比當前節點小的節點-> 將最後一個節點的 `next` 設為 NULL 。

最後透過 ` head->next->prev = (struct list_head *) len`巧妙地將長度 `len` 藏在 `prev`

:::danger
程式碼註解以美式英語書寫，不該存在漢語。
用清晰的漢語解釋程式行為後，再搭配程式碼驗證，避免「舉燭」。
:::

##### `merge_at`
合併 `at` 和 `at->prev` 再用指標 `list` 指向合併的結果且利用 `list->prev = prev` 來維護鏈接的順序同時減少 `stk_size` 的值
（推測是在處理 stack 內的合併）
並利用 `list->next->prev = (struct list_head *) len` 更新合併後的 run 長度，最後再回傳 合併後的 run 。

##### `merge_collapse`
參考 [維基百科](https://en.wikipedia.org/wiki/Timsort)、 [jimmylu890303](https://hackmd.io/@jimmylu0303/linux2024-homework2#%E6%B8%AC%E9%A9%97%E4%BA%8C)
>The runs are inserted in a stack. If |Z| ≤ |Y| + |X|, then X and Y are merged and replaced on the stack. In this way, merging is continued until all runs satisfy :
> i. |Z| > |Y| + |X|
> ii. |Y| > |X|.

在本例子中，X 是 tp ， Y 是 tp->prev ， Z 是 tp->prev->prev
而要合併的形況分成以下 3 種
1. |Z| <= |Y|+|X| 且 |Z| < |X|

YZ 合併
tp->prev = merge_at(priv, cmp, tp->prev);

3. |Z| <= |Y|+|X| 且 |Z| >= |X|

XY 合併
tp = merge_at(priv, cmp, tp);

6. |Y| <= |X|

XY合併
tp = merge_at(priv, cmp, tp);

##### `merge_force_collapse`
與 `merge_collapse` 不同之處在於 `merge_force_collapse` 會不斷進行以下兩種合併直到`run_size` 小於 3
1. |Z|<|X|

YZ合併
tp->prev = merge_at(priv, cmp, tp->prev);

2. 其他

XY合併
tp = merge_at(priv, cmp, tp);

而 `merge_collapse` 只要遇到以下兩種情況就會離開 while loop

1. |Z| > |Y| + |X| 
2. |Y| > |X|

### 2.提出改進方案並予以實作
#### 1. `merge` 裡面重複的部分太多，且沒有使用 Galloping mode
> 考慮到 A 和 B 都是已排序好的數列，我們可持續改進：首先尋找 B 的首個元素（即）在 A 中的排序位置，從而確定 A 中有一段是小於者，可將這部分元素放回 A。接著，尋找剩餘 A 的首個元素在 B 中的位置，如此反覆進行，直到完成排序。

參考 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-timsort#Timsort-%E9%81%8B%E4%BD%9C%E6%96%B9%E5%BC%8F)

然而有關「重複部分太多」 的改進方案再參考 [第一次嘗試貢獻 Linux 核心](https://hackmd.io/@yanjiew/linux2023q1-1st_contrib) 所提供的結果後發現小丑竟是我自己。
#### 2. `find_run` 沒有遵守 2 的冪的原則也沒有確保每個run 的長度不小於 minrun
1. 選擇 minrun 的策略是 Timsort 的關鍵，我打算使用 [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2) 裡面提到的方法：
>取資料長度的前 6 位，若剩餘位中任何一位被設置，則加 1。
>這主要是為了在處理隨機數列時，使得能夠被 minrun 切分成 2 的冪的 run，以便在合併時達到最佳平衡。

原本看不懂敘述，直到翻閱了 [Wikipedia: Timsort](https://en.wikipedia.org/wiki/Timsort#:~:text=Timsort%20is%20a%20hybrid%2C%20stable,in%20the%20Python%20programming%20language.) 中的描述才知道是取陣列長度的「二進位表示法」的前六位為 minrun ，若剩餘位中任何一位被設置（剩餘位中有任何一位是1），則 minrun 要再加 1。

minrun 具體具體流程如下：
1. 找到前六位
在 while loop 中不斷將 `n` 除以 2 直到其值小於等於 63 (111111，六位皆為1)
2. 檢查剩餘位數是否有被設置（有 1 ）
使用 `n & 1` 來取得最後一位 (LSB) 的值 ，並用 `|` 來更新 `r` 的值

size_t calculate_minrun_naive(size_t n) {
    size_t r = 0; 
    while (n >= 64) {
        r |= n & 1;
        n >>= 1;
    }
    return n + r;
}

:::warning
考慮 [compute_minrun](https://github.com/swenson/sort/blob/24f5b8b13810ad130109c7b56daf8e99ab0fe1b8/sort.h#L123) 的實作，以 CLZ 加速與算，善用 GCC 的 `__builtin_clz`
> 了解
:::

參考 [compute_minrun](https://github.com/swenson/sort/blob/24f5b8b13810ad130109c7b56daf8e99ab0fe1b8/sort.h#L123)
步驟如下：
1. 利用 CLZ 來計算 `top_bit` ， size 轉換成二進位後的位數
2. 計算 `shift` ，要向右移的大小，若 size 不足六位則為零
3. 做出 `mask` ，來判斷剩餘位數是否有被設置(`1`)
4. `minrun` = size 的前六位，若有被設置則再加 1

2.改寫 `find_run`
>Timsort 為了使合併過程更加均衡，需要儘量控制每個 run 的長度，定義一個 minrun (最小運行長度)，用以表示每個 run 的最小長度，若長度太短，就用二分插入排序，將 run 後面的元素插入到前面的 run 裡面。

若對鏈結串列使用 `binary_insert` 的話時間複雜度會很糟糕（TODO:原因補充）
>今天一整天都卡在無法用鏈結串列實作出 `binary_insert` 而沒有思考為何要使用 `binary_insert` 以及是否非使用 `binary_insert` 不可，就埋頭亂寫一通，浪費一堆時間，下不為例。

naive:每個 run 的長度固定為 minrun

### 2.將改進過的 Timsort 實作整合進 sysprog21/lab0-c，作為另一個有效的排序命令，應設計效能評比的測試程式，確保測試案例符合 Timsort 設想的資料分布樣式。

---

## 第二週測驗 `1`
運用 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable) 來完成 LeetCode [105 Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)
>給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹。

### 解釋程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
參考 [jimmylu890303](https://hackmd.io/XE_4cW4XQiiWDnE4ILsQqg?view#%E7%AC%AC%E4%BA%8C%E5%91%A8%E6%B8%AC%E9%A9%97%E9%A1%8C)
>Hash table 中的元素為 hlist_head ，而 Hash table 中各個 bucket 的節點為 hlist_node

在結構 `hlist_node` 之中， `pprev` 為「指向自己的指標」的指標

digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    list_head[label = "<m>list_head | <n>first"]
    node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list];
    node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list];
    node_3[label = "<m>hlist_node_3 | {<p>pprev | <n>next}", group = list];
    
    NULL[shape = plaintext, label = "NULL", group = list]

    {rank = "min" list_head}
    
    list_head -> node_1 -> node_2 -> node_3[
        weight = 10, style = invis
    ]
    
    list_head:n -> node_1:m;
    node_1:p -> list_head:n;
    
    node_1:n -> node_2:m;
    node_2:p -> node_1:n;
    
    node_2:n -> node_3:m;
    node_3:p -> node_2:n;
    
    node_3:n -> NULL;
}

程式的執行可以分成以下幾個步驟
1. INIT_HLIST_HEAD
2. node_add
3. dfs

#### 可改進之處
1. 在原本的程式中，只使用了 `hash = (num < 0 ? -num : num) % size` 當作雜湊函數
故想改使用在 [hash.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/hash.h) 中提到的 $h(K) = K \times 2^w \times A >> (w - p)$

### 3.在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

---

## 第二週測驗 `2`
LeetCode 146. LRU Cache

### 2.解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
本題新增了兩個新的結構

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
        LRUCache[label="<m>LRUCache | <n>capacity | <o>count | <p>dhead | <q>hhead[]"]
    LRUNode[label="<m>LRUNode | <n>key | <o>value | <p>node | <q>link"]
    // hlist_head[label = "<m>hlist_head | first", group = list];
    // hlist_node[label = "<m>hlist_node | {<p>pprev | <n>next}", group = list];
    // hlist_head-> hlist_node [style=invis]
    LRUCache->LRUNode [style=invis]
}

> 參考 [jimmylu890303](https://hackmd.io/@jimmylu0303/linux2024-homework2#%E7%AC%AC%E4%BA%8C%E5%91%A8%E6%B8%AC%E9%A9%97%E9%A1%8C)

##### `lRUCacheCreate`
##### `lRUCacheFree`
##### `lRUCacheGet`
##### `lRUCachePut`

### 3.在 Linux 核心找出 LRU 相關程式碼並探討
## 測驗 第二週測驗 `3`
考慮 `find_nth_bit` 可在指定的記憶體空間找出第 N 個設定的位元 (即 `1` )

### 2.解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
### 3.在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討