2024q1 Homework2 (quiz1+2)

contributed by < ssheep773 >

第 1 週測驗題

2024q1 第 1 週測驗題

測驗 `1`

運作原理
使用鏈結串列實作 Quick sort ，其中的 node_t 結構如下

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

digraph node_t
{
    node [shape= "record"];
    rankdir= "LR";
    subgraph cluster_0
    {
        label= "node_t";
        node1 [label= "<head>value | next | {<left> left | <right> right}"];
    }
}

透過實際例子解釋程式流程:

digraph initial
{
    node [shape="box"];
    node4 [label= "4"]
    node3 [label= "3"]
    node5 [label= "5"]
    node1 [label= "1"]
    node [shape="plaintext"];
    L [fontcolor="blue"]
    R [fontcolor="blue"]
    pivot [fontcolor="red"]
    {
        rank="same";
        node4->node3
        node3->node5
        node5->node1
    }
    pivot->node4;
    L->node4;
    R->node1;
}

選擇 L 指向的節點 4 作為 pivot ，將 pivot 從串列移除，並比較剩餘節點和 pivot 的大小關係，使用 list_add 將小於 pivot 的節點加入 left ，大於 pivot 的節點加入 right 。

digraph initial
{
    node [shape="box"];
    node3 [label= "3"];
    node1 [label= "1"];
    node4 [label= "4"];
    node5 [label= "5"];
    node [shape="plaintext"];
    left [fontcolor="blue"];
    right [fontcolor="blue"];
    pivot [fontcolor="red"];
    
    
    left->node3;
    "begin[0]"->node3;
    node3->node1;
    node1->"end[0]" [dir=back];
    
    
    pivot->node4;
    "begin[1]"->node4;
    node4->"end[1]" [dir=back];
    
    right->node5;
    "begin[2]"->node5;
    node5->"end[2]" [dir=back];
    
}

i = 2 ， begin[2] == end[2] 將 begin[2] 加入到 result

digraph initial
{
    rankdir = "LR"
    node [shape="box"];
    node5 [label= "5"]
    result [shape="plaintext"];
    "result"->node5;
}

i = 1 ， begin[1] == end[1] 將 begin[1] 加入到 result

digraph initial
{
    rankdir = "LR"
    node [shape="box"];
    node4 [label= "4"]
    node5 [label= "5"]
    
    result [shape="plaintext"];
    "result"->node4;
    node4->node5;
    
}

然後再回到 i = 0 重複上述的步驟完成排序

digraph initial
{
    node [shape="box"];
    node4 [label= "4"]
    node3 [label= "3"]
    node5 [label= "5"]
    node1 [label= "1"]  
    result [shape="plaintext"];
    {
        rank="same";
        result->node1;
        node1->node3;
        node3->node4;
        node4->node5;
    }
    
}

此方法都是選擇最左邊的節點作為 pivot ，並且透過 begin[n] == end[n] 來確認是否完成排序，我們的結果是由小到大的排序，所以每次優先選擇 right 做排序

改進方法

pivot 的選擇
max_level 的大小

目前的選擇 pivot 的方法在處理一個排序好的遞增串列時，會使的時間複雜度 \(O(n^2)\)

暴力解 : 可以在排序前先檢查串列是否為排序好的遞增串列，若符合擇不執行 quick sort 直接將串列反轉

使用 median of three ，查看串列的前中後三個點的大小，取中間值作為 pivot
使用 median of median ，找尋串列的中位數作為 pivot

使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

使用 Linux 核心風格的 List API 改寫 Quick sort

commit a64bbcf

首先引入 list.h 以及將測試程式改成測驗一中 timsort 使用的 main.c 。

修改成 Linux 核心風格的 List API ，最需要修改的是排序節點的結構是定義在 main.c ，我們無法在 quick.c 中得知排序節點的架構，無法使用list_entry 等巨集，比較節點大小時則是透過呼叫比較函式 cmp

digraph {
    node [shape=plaintext];
    "Pointer to pointer:" -> "*begin[ ]:" -> "list_head:" [color=white];

    node [shape=record, fontcolor=black, ];
    pointers [label="<f0> **begin ", color=white];
    values [label="<f0> *begin[0] | <f1> begin[1] | <f2> *begin[2] | <f3> *begin[3] | <f4> ... | <f5> *begin[max_level]", ];
    indices [label="<head> head"];

    { rank=same; "Pointer to pointer:"; pointers }
    { rank=same; "*begin[ ]:"; values }
    { rank=same; "list_head:"; indices }

    edge [color=black];
    pointers:f0 -> values:f0;
    
    values:f0 -> indices:f0;    
}

上面是修改後的結構圖，會在排序開始時配置整個 **begin

struct list_head **begin = malloc(sizeof(struct list_head *) * max_level);

在排序過程中配置 *begin[] 指向 head 用來串接排序的串列，
其中因為最後是將結果接回輸入的 head 需要初始化避免出錯，所以使用list_splice_tail_init(head, begin[0])

begin[0] = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(begin[0]);
list_splice_tail_init(head, begin[0]);

我們可以透過檢查串列只有一個節點或是為空來決定要分割還是合併串列

-   if (L != R) 
+   if (!list_is_singular(begin[i]) && !list_empty(begin[i]))

使用 link-list 建立 `begin`

上面的方法中我們在一開始就考慮最差的情況，建立最大的可能使用的 begin[] ，這在一般隨機的情況下會產生資源浪費（這在後續的實驗會證明），而且要求配置龐大的連續空間，也存在失敗的風險，我希望 begin[] 可以改成以鏈結串列的方式建立

建立 begin_t 的架構，並且紀錄串列最長時的 begin_t 個數

typedef struct begin_t{
    struct list_head blist; // 串接其他的 begin_t
    struct list_head *head; // 串接排序的串列
} begin_t;

因為 begin_t 是定義在 quick.[ch] 所以我們可以使用 lis_entry 等巨集

來到實驗的部分，當樣本數是 10000 時的最壞情況， begin_t 個數來到 19999 ，符合前面用 begin[] 建立時的大小

Creating sample 
==== Testing quick_sort ====
max begin size = 19999
  Comparisons:    49995000
  check:      List is sorted

在相同樣本中一般情況下，串列最長時的 begin_t 個數約在 2100 個左右，可以發現個數大約是原始最大值的 10% ，減少了 90% 的空間，並且是非連續的記憶體建制。

Creating sample 
==== Testing quick_sort ====
max begin size = 2154
  Comparisons:    5043928
  check:      List is sorted

比較使用鏈結串列與陣列建立 begin 的記憶體開銷

首先是使用陣列建立的記憶體開銷
memory_array

在來是使用鏈結串列動態建立的記憶體開銷
可以看到記憶體的起伏，說明記憶體的配置與釋放
linklist

改進 `pivot` 的選擇使用 middle of three

commit f14fa6a

比較串列的第一個、最後一個與中間的節點數值，選擇他們的中間值作為 pivot ，中間的節點是透過快慢指標取得，其中的 snode->head->next->next->next 是為了要確認目前的串列至少有兩個節點，否則使用快慢指標會進入無窮迴圈，

struct list_head *pivot;
if (begin[i]->next->next->next != begin[i]) {
    struct list_head *first = begin[i]->next;
    struct list_head *last = begin[i]->prev;
    struct list_head *mid = begin[i]->next;
    for (struct list_head *fast = begin[i]->next;
         fast != begin[i] && fast->next != begin[i];
         fast = fast->next->next) {
        mid = mid->next;
    }
    pivot = findMiddle(first, mid, last, priv, cmp);
} else {
    pivot = begin[i]->next;
}

若排序一個排序好的串列時，原始的 quick sort 會是最壞的情況 (worse case) ，而改成使用 middle of three 後，在最壞的情況下可以減少約 99% 的比較次數。

Creating sample
==== Testing quick_sort ====
  Comparisons:    49995000
  check:      List is sorted
==== Testing quick_sort_mid ====
  Comparisons:    121821
  check:      List is sorted

但是在隨機串列的情況下，直接使用串列首個節點作 pivot 的比較次數會較少，並且 middle of three 會有嚴重 unstable 的情況，還需要改進。
(上面提到的最壞的情況不會有 unstable 的情況，是因為樣本中沒有重複的數字)

Creating sample
==== Testing quick_sort ====
  Comparisons:    5037252
  check:      List is sorted
==== Testing quick_sort_mid ====
  Comparisons:    5066375

ERROR: unstable 5001
  check:    
ERROR: unstable 5001
  List is not sorted

commit d0f0990 修改 findMiddle 找中間數值的函式，這次的修改主要是確保當 a == b == c 時，會優先選擇 a 減少 unstable 的發生，而 cmpBC 可以透過 cmpAB - cmpAC 得到，可以減少一次比較

struct list_head *findMiddle(struct list_head *a,
                             struct list_head *b,
                             struct list_head *c,
                             void *priv,
                             list_cmp_func_t cmp)
{
    int cmpAB = cmp(priv, a, b);
    int cmpAC = cmp(priv, a, c);   
    int cmpBC = cmpAB - cmpAC;
    if ( (cmpAB <= 0 && cmpAC >= 0) || (cmpAB >= 0 && cmpAC <= 0) ) {               
        return a;
    }
    if ( (cmpAB >= 0 && cmpBC >= 0) || (cmpAB <= 0 && cmpBC <= 0)) {                       
        return b;
    }
    return c;
}

修改後 unstable 的情況大幅減少，但是仍然會發生。

Creating sample
==== Testing quick_sort ====
  Comparisons:    5034315
  check:      List is sorted
==== Testing quick_sort_mid ====
  Comparisons:    5067210

ERROR: unstable 10
  check:    
ERROR: unstable 10
  List is not sorted

這主要是因為在前幾次分割時，選擇前中後三個數字時造成的，以例子說明：
在下面的例子中節點以 數值.次序 表示，可以看到因為 pivot = 9.10 ，而我們是用 < pivot <= 來劃分，這樣數值相同但是次序較前的 9.7 會被排到 9.10 後面產生 unstable 的情況，而若改成 <= pivot < 則換成 9.15 會產生 unstable 的情況，所以目前的方法還是 unstable 。

list = 3.0 5.1 5.2 6.3 2.4 5.5 8.6 9.7 4.8 4.9 9.10 5.11 8.12 6.13 3.14 9.15 0.16 5.17 7.18 7.19 

first= 3.0, mid= 9.10 ,last= 7.19 => pivot=9.10 

 begin[0] : 3.0 5.1 5.2 6.3 2.4 5.5 8.6 4.8 4.9 5.11 8.12 6.13 3.14 0.16 5.17 7.18 7.19 

 begin[1] : 9.10 

 begin[2] : 9.7 9.15

測驗 `2`

Timsort 程式碼理解

這裡使用的 merge 方法與 merge sort 使用的 one-pair-at-a-time mode 相同

static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head;
    struct list_head **tail = AAAA;
    for (;;) {
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

build_prev_link 將單向鏈結串列 list 加入雙向鏈結串列中，因為 Timsort 在排序過程中，會將原本的雙向鏈結斷掉

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

merge_final 與前面提到的 merge 差異是合併時是雙向鏈結串列，並且如果 a 走訪完畢則結束，但若是 b 走完則會將 a 放入 b ，再透過 build_prev_link(head, tail, b) 建立剩餘節點的雙向鏈結，並且這樣撰寫的優點是我們不必分別確認 a 跟 b 是否為走訪完

merge_at : 函式是將 tp 和 tp->prev 合併至 tp

find_run

static struct pair find_run(void *priv,
                            struct list_head *list,
                            list_cmp_func_t cmp)
{
    size_t len = 1;
    struct list_head *next = list->next, *head = list;
    struct pair result;

    if (!next) {
        result.head = head, result.next = next;
        return result;
    }

    if (cmp(priv, list, next) > 0) {
        /* decending run, also reverse the list */
        struct list_head *prev = NULL;
        do {
            len++;
            list->next = prev;
            prev = list;
            list = next;
            next = list->next;
            head = list;
        } while (next && cmp(priv, list, next) > 0);
        list->next = prev;
    } else {
        do {
            len++;
            list = next;
            next = list->next;
        } while (next && cmp(priv, list, next) <= 0);
        list->next = NULL;
    }
    head->prev = NULL;
    head->next->prev = (struct list_head *) len;
    result.head = head, result.next = next;
    return result;
}

使用圖解的方式說明 : 這裡參考 SH 同學的圖解

第一種情況 : 升序排列的節點

首先將 head 指向鏈結串列的開頭， next 指向 list 的下一個節點

digraph initial
{
    node [shape="box"];
    node1 [label= "1", color="red"]
    node4 [label= "4", color="red"]
    node5 [label= "5"]
    node2 [label= "2"]
    node3 [label= "3"]
    
    
    node [shape="plaintext"];
    head [fontcolor="blue"]
    list [fontcolor="blue"]
    next [fontcolor="red"]
    {
        rank="same";
        node1->node4
        node4->node5
        node5->node2
        node2->node3
        node3->"NULL"
    }
    head->node1;
    next->node4;
    list->node1;
}

next 指標中節點的值不小於 list 指標中節點的值，則繼續走訪，直到找到非升序的節點為止

digraph initial
{
    node [shape="box"];
    node1 [label= "1"]
    node4 [label= "4"]
    node5 [label= "5", color="red"]
    node2 [label= "2", color="red"]
    node3 [label= "3"]
    
    
    node [shape="plaintext"];
    head [fontcolor="blue"]
    list [fontcolor="blue"]
    next [fontcolor="red"]
    {
        rank="same";
        node1->node4
        node4->node5
        node5->node2
        node2->node3
        node3->"NULL"
        
    }
    head->node1;
    next->node2;
    list->node5;
    
}

離開迴圈後回傳串列的開頭以及 next 指標，使得下一輪能夠繼續走訪並找到下一組 run

digraph initial
{
    node [shape="box"];
    node1 [label= "1"]
    node4 [label= "4"]
    node5 [label= "5", color="red"]
    node2 [label= "2", color="red"]
    node3 [label= "3"]
    
    
    node [shape="plaintext"];
    head [fontcolor="blue"]
    list [fontcolor="blue"]
    next [fontcolor="red"]
    null [label = "NULL"]
    {
        rank="same";
        "result.head"->node1;
        node1->node4
        node4->node5
        node5->"NULL"
    }
    {   
        rank="same";
        "result.next"->node2;
        node2->node3
        node3->null
    }
    next->node2;
    list->node5;
    head->node1;
}

第二種情況 : 降序排列的節點

一樣首先將 head 指向鏈結串列的開頭， next 指向 list 的下一個節點，不過這種情況多一個 prev

digraph initial
{
    node [shape="box"];
    node1 [label= "1"]
    node4 [label= "4", color="red"]
    node5 [label= "5", color="red"]
    node2 [label= "2"]
    node3 [label= "3"]
    node [shape="plaintext"];
    head [fontcolor="blue"]
    list [fontcolor="blue"]
    next [fontcolor="red"]
    prev [fontcolor="red"]
    null [label="NULL"]
    {
        rank="same";
        node5->node4
        node4->node1
        node1->node2
        node2->node3
        node3->"NULL"
    }
    next->node4;
    list->node5;
    head->node5;
    prev->null;
}

第一次執行後結果

digraph initial
{
    node [shape="box"];
    node1 [label= "1"]
    node4 [label= "4", color="red"]
    node5 [label= "5", color="red"]
    node2 [label= "2"]
    node3 [label= "3"]
    node [shape="plaintext"];
    head [fontcolor="blue"]
    list [fontcolor="blue"]
    next [fontcolor="red"]
    prev [fontcolor="red"]
    null [label="NULL"]
    {
        rank="same";
        node4->node1
        node1->node2
        node2->node3
        node3->"NULL"
        node5->null;
    }
    next->node1;
    list->node4;
    head->node4;
    prev->node5;
    
}

持續走訪直到 next 節點的值大於(或等於) list 節點的值

digraph initial
{
    node [shape="box"];
    node1 [label= "1", color="red"]
    node4 [label= "4", color="red"]
    node5 [label= "5"]
    node2 [label= "2"]
    node3 [label= "3"]
    node [shape="plaintext"];
    head [fontcolor="blue"]
    list [fontcolor="blue"]
    next [fontcolor="red"]
    prev [fontcolor="red"]
    null [label="NULL"]
    {
        rank="same";
        node1->node2
        node2->node3
        node3->"NULL"
        node4->node5;
        node5->null;
    }
    next->node2;
    list->node1;
    head->node1;
    prev->node5;
    
}

最終離開迴圈後回傳串列的開頭以及 next 指標，使得下一輪能夠繼續走訪並找到下一組 run，可以發現走訪過的節點皆被反轉。

digraph initial
{
    node [shape="box"];
    node1 [label= "1", color="red"]
    node4 [label= "4", color="red"]
    node5 [label= "5"]
    node2 [label= "2"]
    node3 [label= "3"]
    node [shape="plaintext"];
    list [fontcolor="blue"]
    next [fontcolor="red"]
    null [label="NULL"]
    {
        rank="same";
        "result.head"->node1
        "result.next"->node2
        node2->node3
        node3->"NULL"
        node1->node4;
        node4->node5;
        node5->null;
    }
    next->node2;
    list->node5;
}

接著，timsort 會檢視目前的 runs 是否可以合併，這是 timsort 的一個特色，會在分割的過程中進行合併，達到對 cache 友善的效果。

merge_collapse 是 timsort 檢查 stack 中頂層 3 個 run 的大小是否滿足以下兩個條件 : ( X在最上層 )

Z > Y + X
Y > X

若沒有符合則比較 X 、 Z 的大小，較小的與 Y 合併，而如果只有 2 個 run 時則只需滿足第二個條件

X = run_size(tp)
Y = run_size(tp->prev)
Z = run_size(tp->prev->prev)
在下面的程式碼我們不只看頂層 3 個 run ，也看頂層 2 到 4 層是否滿足上述的條件

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

merge_force_collapse 這裡的合併就是不斷抓出頂部三個 run ，比較第一層與第三層的大小，較小的與第二層合併，直到剩下小於 3 run。合併時只跟上下層合併是為了保持排序的 stable

timsort 首先將鏈結串列斷成單向，接著執行 find_run 將串列拆分成多個 run 存在 tp 中並透過 merge_collapse 確保符合timsort 對 run 的兩個條件。
接著執行 merge_force_collapse 使 stk_size < 3 ，
而我們會有剩一個 run 以及剩兩個 run 的情況，若剩一個則執行
build_prev_link 將鏈結串列串成雙向則完成，否則呼叫merge_final 將最後兩個 run 合併

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
    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);

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

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

目前疑惑這段看起來是走訪到 stack 的底部，但不知道其中用意

/* The final merge; rebuild prev links */
    struct list_head *stk0 = tp, *stk1 = stk0->prev;
    while (stk1 && stk1->prev)
        stk0 = stk0->prev, stk1 = stk1->prev;

目前的 timsort 時做並未實作 minrun 與 galloping mode ，預計加入這兩個方法並分析效能
將 timsort 引入lab0 中 commit bcd1a78

第 2 週測驗題

2024q1 第 2 週測驗題

測驗 `1`

運用 Linux 核心的 hash table 實作構建二元樹

首先看主函式 buildTree，使用中序 (inorder) 的序列建立 hash table ，使用 INIT_HLIST_HEAD 初始化 hash table ，再透過 node_add 建立 hash table，最後用 dfs 搭配建立的 hash table 建構二元樹

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

先觀察 node_add 如何建立 hash table ，根據 hash 變數決定我們在 hash table 內的位置，透過 hlist_add_head 函式將其加至 hash table 中

static inline void node_add(int val,  
                            int idx,  //在中序的位置
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, ＆heads[hash]);
}

可以得到如下的 hash table，值得關注的是 order_node 還儲存 inorder 串列的索引值 idx

digraph so
{
    rankdir=LR;
    {rank=same inh4 inh3 inh2 inh1 inh0} 
    inh0 [label="in_heads[0]"; shape="none"];
    inh1 [label="in_heads[1]"; shape="none"];
    inh2 [label="in_heads[2]"; shape="none"];
    inh3 [label="in_heads[3]"; shape="none"];
    inh4 [label="in_heads[4]"; shape="none"];
    node [shape = "record"];
    15 [label="{val : 15 | idx : 2}"]; 
    20 [label="{val : 20 | idx : 3}"];
    7 [label="{val : 7 | idx : 4}"];
    9 [label="{val : 9 | idx : 0}"];
    3 [label="{val : 3 | idx : 1}"];
    inh0 -> 20 -> 15
    inh2 -> 7
    inh3 -> 3
    inh4 -> 9
 }

接者是 hlist_add_head ，需在加入前先檢查原先是否有節點存在，若存在則須將原先第一個節點的 pprev 指向 &n->next ，詳細內容的可以參見 Linux 核心的 hash table 實作

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first;
    n->pprev = &h->first;
    h->first = n;
}

在使用中序 (inorder) 建立 hash table 後，接著看到 dfs
輸入的變數 :
preorder pre_low pre_high ：前序序列與節點搜尋範圍
inorder in_low in_high ：中序序列與節點搜尋範圍
in_heads ：中序建立的 hash table
size ：是 inorderSize 同時也是 hash table 的大小

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

tn->val = preorder[pre_low] 因為是前序 tn 必為父點，透過 find 得知 tn 在中序的位置 idx ，我們可以透過 idx 得知節點是如何劃分的

digraph so
{
    rankdir=TB;
    left [color=red, label="9"]
    right [color=red, label="15    20    7"]
    
    root [color=blue;label="3"]
    root -> left
    root -> right
 }

如此遞迴下去即可建構二元樹

最後來看 find 尋找節點 val 在中序的位置 idx ，而使用 hash table 可以快速地找到目標節點資訊，其中 hlist_for_each (p, &heads[hash]) 為走訪特定索引中的所有節點，找到相同 val 並回傳 idx

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &heads[hash]) {
        struct order_node *on = list_entry(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

TODO

指出其中可改進之處並實作
在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

測驗 `2`

理解程式碼

LRUCache 結構

typedef struct {
    int capacity;    // 快取的最大容量
    int count;       // 目前已儲存的節點數量
    struct list_head dhead;     // 儲存快取中的節點
    struct hlist_head hhead[];  // 快速查找特定鍵值的節點
} LRUCache;

lRUCacheCreate 新增 LRU Cache 並初始化

疑問 : 在配置 hhead[] 的記憶體時，為何是使用 sizeof(struct list_head)) 而不是 hlist_head 是否因為空間相同？

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
                             capacity * sizeof(struct list_head));
    cache->capacity = capacity;
    cache->count = 0;
    INIT_LIST_HEAD(&cache->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_HLIST_HEAD(&cache->hhead[i]);
    return cache;
}

lRUCacheFree 釋放先前分配的記憶體並清除 LRU 快取
我們透過 list_for_each_safe 走訪快取中的所有節點，
而節點中 link 變數表示節點儲存的資料位置，我們在刪除節點 free(cache) 前需要先將 link 刪除

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, link);
        list_del(&cache->link);
        free(cache);
    }
    free(obj);
}

lRUCacheGet
使用 hash table 能夠更快速找到節點，透過 LRUNode *cache = list_entry(pos, LRUNode, node) 我們走訪特定索引值內中的節點，而且同一個索引值節點之間是用 node 連接。
並且若我們找到對應的 key 會將該節點移至 dhead 的開頭。

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

lRUCachePut
可以分為三種情況：

已有相同的節點存在
與 lRUCacheGet 作法相似，因為都在找尋相同 key 值，差異在於最後找到的節點 c 賦值給 cache。
沒有相同的節點存在，快取已滿，需要刪除節點
取得 dhead 尾部的節點，表示是最久未被使用的節點，將它移動至 dhead 開頭並刪除，最後在刪除的節點位置新增新的節點資訊
沒有相同的節點存在，快取未滿，可直接加入
為 cache 配置新的記憶體位置，將節點加入 head table 的索引及 dhead 開頭，最後更新目前的快取數量

在 lRUCachePut 的部分，情況 2 使用了原本刪除節點的記憶體位置，省去新配置記憶體的失敗風險，並且因為是額滿的情況也無需更新 obj->count

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *c = list_entry(pos, LRUNode, node);
        if (c->key == key) {
            list_move(c->link, &obj->dhead);
            cache = c;
        }
    }

    if (!cache) {
        if (obj->count == obj->capacity) {
            cache = list_last_entry(&obj->dhead, LRUNode, link);
            list_move(&cache->link, &obj->dhead);
            hlist_del(&cache->node);
            hlist_add_head(&cache->node, &obj->hhead[hash]);
        } else {
            cache = malloc(sizeof(LRUNode));
            hlist_add_head(&cache->node, &obj->hhead[hash]);
            list_add(&cache->link, &obj->dhead);
            obj->count++;
        }
        cache->key = key;
    }
    cache->value = value;
}

改進之處並實作
lRUCacheGet 中會將剛尋找到的節點移至 dhead 的開頭，我們也應該將節點移至 hlist_head 的開頭更快速的從 hash table 中找到。

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead);
+            hlist_del(&cache->node);
+            hlist_add_head(&cache->node, &obj->hhead[hash]);
            return cache->value;
        }
    }
    return -1;
}

延伸問題:
在 Linux 核心找出 LRU 相關程式碼並探討

測驗 `3`

在指定的記憶體空間找出第 N 個設定的位元

解釋程式碼的運作原理
首先看到 find_nth_bit 他有三個變數
addr : 指向要尋找的位元組的指標
size : 位元的搜尋範圍
n : 需要確認是否為 1 的位元位置

我們會先檢查 n 是否超出搜尋範圍，接著我們需要先了解 small_const_nbits GENMASK 這兩個巨集的作用

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

small_const_nbits 透過 builtin_constant_p 檢查 nbits 是否在編譯時就已經確立，並且檢查是否介於範圍 0 < nbit <= BITS_PER_LONG

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)

GENMASK 產生長度為 BITS_PER_LONG 並且在 h 位元到 l 位元之間為 1 的 bitmask

#define GENMASK(h, l) \
    (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

再知曉 small_const_nbits GENMASK 的作用後，看到下面程式碼，先確認變數是否在編譯時就確立後，並生成一個由 0 到 (size-1) 都為 1 的 mask ，與 addr 做交集，高於 size 的位元會被歸零，如此只保留搜尋範圍內的位元
這個判斷條件的主要是在 size 足夠小時，可以用更簡單快速的方法來找到第 n 個為 1 位元，而不需要調用到較複雜的 FIND_NTH_BIT

if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

之後再透過 fns 尋找第 nth 位元，fns 目的是找到第 n 個被設為 1 的位置，我們呼叫 __fs 尋找位元組中設為 1 的最低位元位置，並用 __clear_bit 將那個位置歸零避免重複找到，當 n = 1 時表示找到第 n 個被設為 1 的位置

static inline unsigned long fns(unsigned long word, unsigned int n)
{
    while (word) {
        unsigned int bit = __ffs(word);
        if (n-- == 0)
            return bit;
        __clear_bit(bit, &word);
    }

    return BITS_PER_LONG;
}

接者來看 FIND_NTH_BIT 使用 idx 以 BITS_PER_LONG 長度為一個區間走訪，透過 hweight_long 可以得知區間內的 1 個數，若個數大於 nr 則代表目標 nr 在這個區間內，再呼叫 fns 在該區間內尋找確切的位置，並且 fns 結果需加上目前所在區間位置 idx * BITS_PER_LONG ，才是最後的結果

反之若 hweight_long 區間內的 1 個數不超過 nr 代表，目標 nr 不再區間內，往下一個區間尋找，直到超過搜尋範圍 sz

#define FIND_NTH_BIT(FETCH, size, num)                          \
    ({                                                          \
        unsigned long sz = (size), nr = (num), idx, w, tmp;     \
                                                                \
        for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
            if (idx * BITS_PER_LONG + nr >= sz)                 \
                goto out;                                       \
                                                                \
            tmp = (FETCH);                                      \
            w = hweight_long(tmp);                              \
            if (w > nr)                                         \
                goto found;                                     \
                                                                \
            nr -= w;                                            \
        }                                                       \
                                                                \
        if (sz % BITS_PER_LONG)                              \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })

延伸問題：
在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例，並予以解說和分析，需要涵蓋 CPU affinity 相關的原始程式碼。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

2024q1 Homework2 (quiz1+2)

第 1 週測驗題

測驗 1

使用 Linux 核心風格的 List API 改寫 Quick sort

使用 link-list 建立 begin

改進 pivot 的選擇使用 middle of three

測驗 2

第 2 週測驗題

測驗 1

運用 Linux 核心的 hash table 實作 構建二元樹

測驗 2

理解程式碼

測驗 3

在指定的記憶體空間找出第 N 個設定的位元

測驗 `1`

使用 link-list 建立 `begin`

改進 `pivot` 的選擇使用 middle of three

測驗 `2`

測驗 `1`

運用 Linux 核心的 hash table 實作構建二元樹

測驗 `2`

測驗 `3`