2024q1 Homework2 (quiz1+2)

contributed by <[sssssssttttttt](https://github.com/stevendd543/lab0-c) > ### 第一周測驗 1 ```c 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) { 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] = 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) list_add(&result, L); i--; } } *list = result; } ``` 特別將這個函數`list_add`以圖表示過程 ```c void list_add(node_t **list, node_t *node_t) { node_t->next = *list; *list = node_t; } ``` 當 `node_t` 要插入 `list` 原本會長這樣 ```graphviz digraph { subgraph{ node_t[shape=box color=red] } "list"[shape=box] head[shape=box] n1[shape=box] n2[shape=box] {rank=same head "list"} {rank=same n1 n2} "list" -> head head -> n1 n1->n2 } ``` 加入後變這樣 ```graphviz digraph { subgraph{ node_t[shape=box color=red] } "list"[shape=box] head[shape=box] n1[shape=box] n2[shape=box] {rank=same head "list"} {rank=same node_t n1 n2} "list" -> head head -> node_t n1->n2 node_t->n1[color=red] } ``` 也就是加入在前端。 * stack 用途與特性 - 用途 : 先了解 stack 用意，在這個程式碼中使用了兩個變數`begin`和`end`來儲存任何==子串列==的頭跟尾的位置(下圖)，stack 每次都會將左中右的子串列儲存在 stack 中，其中最上端的串列位置所指的子串列，因為屬於右邊所以平均值會最大，用以日後 pop stack 時會先加入最大的數，可以回去看`list_add`的加入方法是從右到左放入數字。$(f > b > c,d,e$ ) - 特性 : stack 中每層位置指向的串列元素們都會**大於自己下方**和**小於自己上方**元素們 ```graphviz digraph { "begin[i]"[shape=box] "end[i]"[shape=box] pivot [shape=box] "begin[i+2]"[shape=box] "end[i+2]"[shape=box] b[shape=box] c[shape=box] d[shape=box] e[shape=box] f[shape=box] {rank=same b c d e f} "begin[i]" -> c b -> c[color=red] c-> d ->e->f "end[i]" ->e pivot->b "begin[i+2]"->f "end[i+2]"->f } ``` * 知道上述的變數用途後，可以把問題分成兩部分`L==R`與`L!=R`每次進入迭代時都會先取 stack 最上端分別給 `L`與`R` **L==R :** 代表這個子串列只剩一個元素可以直接加入`result` ```graphviz digraph { "L"[shape=box] "R"[shape=box] node1[shape=box] "L"->node1 "R"->node1 } ``` **L!=R :** 代表這個子串列還得繼續將它分成左右子串列再繼續處理 ```graphviz digraph { "L"[shape=box] "R"[shape=box] node1[shape=box] node2[shape=box] node3[shape=box] {rank=same node1 node2 node3} "L"->node1 "R"->node3 node1->node2 node2->node3 } ``` 綜合以上各個模組討論就可以把整個程式串起來了 ! #### 測驗一 : 空格填答 * AAAA = BBBB = `(*left)->next)` 走訪全串列 * CCCC : 將串列中元素根據 pivot 為標準將 $<pivot$ 之元素加入 `left` 串列 $>pivot$ 之元素加入 `right` 串列 ```diff= while (p) { node_t *n = p; - p = CCCC; + p = p->next; list_add(n->value > value ? &right : &left, n); } ``` * DDDD = `&list_tail(left)` * EEEE = `&list_tail(right)` #### 使用 Linux 核心風格的 List API ： * 完整程式碼在 [commit](https://github.com/stevendd543/sorting/commit/30a2009fbe9b2f5b0f426e725d9dcd95e9a51193) * 這是我使用的結構，`node_t`內包含`struct list_head`去做串接 ```graphviz digraph list { graph [fontsize=12 fontname="Verdana" compound=true]; node [shape="record"]; rankdir = "LR" subgraph cluster_a { label = "node_t"; node2 [label=value] node1 [label="list_head|{<left> *left |<right> *right}"]; } } ``` * 我保留原本的堆疊方法，將其改儲存`struct list_head`地址 #### 改進方案： * **配置大小的必要性 :** 可以發現在十萬筆資料下不管怎麼執行堆疊元素的量都遠小於資料量，因此可以探討` struct list_head *begin[2 * number_of_data]`**配置大小的必要性** ```c n = 100000 max stack element : 46 cpu clock time : 38384 max stack element : 50 cpu clock time : 29717 max stack element : 58 cpu clock time : 34506 ``` * **pivot 的選擇 :** 首先我先將區域極端值都抓到最前端與我提出的方法去做比較，可以發先區域極端值的排序相當耗時，可見選擇 pivot 相當重要 * :a:以下程式碼都是固定 stack 容量大小下實驗 ```c // 1 max stack element : 38 cpu clock time : 148056 // 2 max stack element : 10 cpu clock time : 261 ``` 這裡我採用不多花空間去紀錄所有值，然後再取中位數，我選擇從左到右比大小，但*要比大還比小*是交替選擇，來近似取中位數的方法，以下是我尋找 pivot 的程式碼 ```c void find_pivot(struct list_head *head, int n) { int k = 0; int stop = n / 2 + 1; bool lock = false; struct list_head *m = head->next; struct list_head *node; list_for_each(node, head){ k++; if(!lock){ m = list_entry(m, node_t, list)->value < list_entry(node, node_t, list)->value ? node : m; lock = !lock; }else{ m = list_entry(m, node_t, list)->value > list_entry(node, node_t, list)->value ? node : m; lock = !lock; } if(k == stop){ list_move(m,head); return; } }; } ``` 考慮到極端值會影響執行時間，因此我決定犧牲一點時間去選擇 pivot，雖然感覺多做一些操作，但實際排序結果卻快上很多 ```c // without find_pivot() // with find_pivot() n : 10000 max stack element : 10 cpu clock time : 1050 n : 10000 max stack element : 38 cpu clock time : 3430 n : 100000 max stack element : 26 cpu clock time : 10253 n : 100000 max stack element : 46 cpu clock time : 29003 n : 1000000 max stack element : 44 cpu clock time : 172131 n : 1000000 max stack element : 64 cpu clock time : 449864 ``` ### 第一周測驗 2 #### timsort 程式碼部分介紹引用[C語言規格書 6.3.2.3 ](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)，整數與指標間是可以合法轉換 >An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation. * `static struct pair find_run(...)` 中將 run size 轉型成指標後儲存在 `head->next->prev` ```c head->next->prev = (struct list_head *) len; ``` * `tp` 為儲存所有 run 的串列，注意`tp->prev...->prev`資料比`tp` 還早進來表示越舊 * `static struct list_head *merge_collapse(...)` 合併判斷標準為最新或者次新的 run 往後數三個來判斷 run size 大小，當最新的兩個$( A、B )$大小大於最舊的那個$( C )$且如果 $A>C$ 就將 $B、C$ 合併，否則 $A、B$ 合併 ```graphviz digraph { "A"[shape=box] "B"[shape=box] "C"[shape=box] "tp->prev->prev"[shape=box width=1] "tp->prev"[shape=box width=1.3] tp[shape=box width=1.3] {rank=same "tp->prev->prev" "tp->prev" tp} A->tp B->"tp->prev" C->"tp->prev->prev" tp->"tp->prev" "tp->prev"->"tp->prev->prev" } ``` #### timsort 主流程 * 建立串列並以 `NULL` 中斷串列連結成單向串列 * 迭代尋找串列中的 run ，每個 run 使用 `result` 這個結構進行包裝，並每次都檢查目前發現的 run 中是否需要進行合併，來保持所有 run size 的平衡 * 迭代尋找完所有 run 後合併所有 run 至 `stk_size < 3` 為止，合併條件當 $A>C$ 就先合併 $B、C$ 否則合併 $A、B$ ### 第二周測驗 1 ```graphviz digraph G { rankdir=LR; node[shape=record]; map [label="hlist_head.first |<ht0> |<ht1> |<ht2> |<ht3> |<ht4> |<ht5> |<ht7> |<ht8> "]; node[shape=none] null1 [label=NULL] null2 [label=NULL] subgraph cluster_1 { style=filled; color=lightgrey; node [shape=record]; hn1 [label="hlist_node | {<prev>pprev | <next>next}"]; label="hash_key 1" } subgraph cluster_2 { style=filled; color=lightgrey; node [shape=record]; hn2 [label="hlist_node | {<prev>pprev | <next>next}"]; label="hash_key 2" } subgraph cluster_3 { style=filled; color=lightgrey; node [shape=record]; hn3 [label="hlist_node | {<prev>pprev | <next>next}"]; label="hash_key 3" } map:ht1 -> hn1 hn1:next -> hn2 hn2:next -> null1 hn2:prev:s -> hn1:next:s map:ht5 -> hn3 hn3:next -> null2 hn1:prev:s -> map:ht1 hn3:prev:s -> map:ht5 } ``` * **其中 `pprev` 為何要宣告為==指標的指標==？** : 根據[教材](https://hackmd.io/rpIi8FeqQ9eBJ-UTFgb--A?view) : 雙向鏈結串列進行節點移去時，會產生的問題。而且 `pprev` 指向指著自身節點的指標。 * 變數用途 - `hlist_head` : 供 hash table 使用 - `hlist_node` : 填入 table 內，內部含有 next 做碰撞的串接 * `static inline void node_add(...)` : 將索引和值設定好在 `node` 的結構中透過，再利用 `inorder size` 計算出 hash value 加入在對應的 hash value 的串列 * `static struct TreeNode *dfs` : 透過`find`函數找從 hash table 中找到 inoder node 結構中的索引值，其中因為從 preoder 中找到任意子樹的 root 後就可以從 inoder 中找到左右子數節點的個數，在下列舉個**左子樹 dfs** 範例，pre_low 屬於目前 preoder 中左子數節點索引最低點，所以要繼續走訪的話，最低點索引要再加一，最高點索引就是從 inoder 推算出來的左子樹節點的個數`(idx - in_low)` 進行相加得到左子數節點在 preoder 中索引的範圍 ```c tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size); ```  ==preorder== ```graphviz graph { node [shape=record] rankdir=LR a [label="{3|<m>9|20|15|7}"] b [label="<n>idx" ] a:m -- b:n } ``` ==inorder== ```graphviz graph { node [shape=record] rankdir=LR a [label="{9|3|20|15|7}"] } ``` * `static struct TreeNode *buildTree(...)` : 將 inorder 所有的值都建立( by `INIT_HLIST_HEAD` )並計算雜湊值到對應的 `in_heads` 這個 hash table ( by `node_add` )，最後就透過`dfs`去建立整顆樹，即可完成 ### 第二周測驗 2 **原理** 這個 LRU 是使用 hash table 來實作，首先分析它的結構成員的用途 * `LRUCache` : - `capacity` : cache 總容量 - `count` : chche 目前的使用量 - `dhead` : 紀錄整個 hash node 的最近使用順序 - `hhead` : 整個 hash table ```c typedef struct { int capacity; int count; struct list_head dhead; struct hlist_head hhead[]; } LRUCache; ``` * `LRUNode` : - `node` : 用來儲存碰撞的串列元素 - `link` : 紀錄在 `dhead` 中的位置 ```c typedef struct { int key; int value; struct hlist_node node; struct list_head link; } LRUNode; ``` 有了以上的結構成員用途後，就可以知道整個程式碼的流程，特別的一點是每次使用`lRUCacheGet`、`lRUCachePut` 都必須更新 cache 結構中紀錄 hash node 的使用順序，因為不管是最近讀取或者最近放入，都算剛使用過，因此都會有以下這段程式碼，當找到對應的 key 時必須將 dhead 中自身往前挪移 ```c if (c->key == key) { list_move(&c->link, &obj->dhead); cache = c; } ``` 另外如果 cache 容量使用達到限制，必須移除 least recently used 的節點 ```c 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++; } ``` ### 第二周測驗 3