2021q1 Homework1 (quiz1)

# 2021q1 Homework1 (quiz1) contributed by < `RainbowEye0486` > ## 題目回顧 linked list 在 Quick sort 的作法: 1. 選定一個 pivot 2. 從整個 linked list 的左邊開始尋找比 pivot 大的值，找到則移動到 pivot 的右邊；並且從 linked list 的右邊尋找比 pivot 小的值，如果找到的話則移動到 pivot 的左邊，一樣的話任意放。用來分類比 pivot 大或小的數字 3. 接著以 pivot 做為切割點，左右兩個數列分辨進行 Quick sort :::success **Quick sort具有以下特點:** 1. Quick sort 並不是穩定的，因為如果像是 [1 4 2 3 6 2 5 2 ] 這樣的例子，選擇2作為 pivot ，1st 排序完可能會變成 [1 2 2 2 4 3 6 5] ，順序改變了 2. 不是 in-placed ，會浪費額外的空間 > 你需要解釋為何 quick sort「不是 in-placed ，會浪費額外的空間」 > :notes: jserv 我們[對 in-place 的定義](https://en.wikipedia.org/wiki/In-place_algorithm)是"僅僅需要常數空間的記憶體配置"，所以不需要額外多花資料結構來完成排序，但是正常版本的 quick sort 需要使用額外的 left 、 right (比 pivot 較大或小的資料結構，可能是 struct 、 array ...)，所以並不能算是 in-place 。當然，另外也有版本提供[改良過的 in-place quick sort](https://blog.kuoe0.tw/posts/2013/03/15/sort-about-quick-sort/) ，這些演算法重複利用原先的資料結構，不需要 $O(logn)$ 額外的指標來記錄分割後的子結構 ::: ![](https://i.imgur.com/orMwWjU.png) ## 程式碼解讀 ```cpp= static inline void list_add_node_t(node_t **list, node_t *node_t) { node_t->next = *list; *list = node_t; } static inline void list_concat(node_t **left, node_t *right) { while (*left) LLL;//left = &((*left)->next) *left = right; } void quicksort(node_t **list) { if (!*list) return; node_t *pivot = *list; int value = pivot->value; node_t *p = pivot->next; pivot->next = NULL; node_t *left = NULL, *right = NULL; while (p) { node_t *n = p; p = p->next; list_add_node_t(n->value > value ? AAA : BBB, n); } quicksort(&left); quicksort(&right); node_t *result = NULL; list_concat(&result, left); CCC; *list = result; } ``` ### 解析函式功能 - `list_add_node_t`:傳入一個想要新增的節點 node_t，並且將這個節點加到 `list` 的頭。 - `list_concat`: while 迴圈內將 `*left` 指標移動至 list 的末端，然後將其與 `*right` 相連接 - `quicksort`: - **line 14-1**:遞迴呼叫的中止條件，如果 list 無法再被分割 - `node_t *pivot = *list`:這邊選擇取 pivot 的方式是**從 list 的頭去抓** - 因為第一個當作 pivot ，所以從第二個開始檢查(`p`) - **line 23-27**:判斷當前的這個 node 值是不是比 pivot 還小/大，然後分別加入 `*left` 、 `*right` 兩個子 list - 對兩個子 list 遞迴排序 - 排序完畢後將 `*left` 、 `*right` 接起來，重新把開頭從 `result` 改成 `*list` ```graphviz digraph linked_list { rankdir=LR; node [shape=record]; a [label="{ <data> pivot | <ref> }"]; b [label="{ <data> n | <ref> }"]; c [label="{ <data> p | <ref> }"]; d [label="{ <data> -}"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; } ``` ### 重新回答測驗問題 **`LLL: left = &((*left)->next)`** 這邊主要是觀察等號右邊是否能夠將正確的值賦給左邊。觀察發現 - `*left` 是一個指向 node_t 結構的指標，所以用 `(*left)->next` 是正確的 - `left` 是 `*left` 的 dereference ，換句話說就是他的地址，知道 `left` 可以更改放在裡面的指標，決定裡面的地址會指向哪個節點要做的事情是把傳入的指標 `*left` 移動到 `(*left)->next`， ```graphviz digraph ptr { rankdir=LR; node[shape=box]; ptp[label= "0xff"]; ptr[label= "0x36"]; value[label= "node 1"]; ptp -> ptr[arrowhead=vee, tailclip=true, arrowsize=1] ptr -> value[arrowhead=vee, tailclip=true, arrowsize=1] } ``` 假設 `node 1` 的下一個節點是 `node 2` 且地址是 `0x40` ，先用 `&((*left)->next)` 抓到 `0x40` 的地址 `0xf8` 修改掉 ```graphviz digraph ptr { rankdir=LR; node[shape=box]; ptp[label= "0xf8"]; ptr[label= "0x40"]; value[label= "node 2"]; ptp -> ptr[arrowhead=vee, tailclip=true, arrowsize=1] ptr -> value[arrowhead=vee, tailclip=true, arrowsize=1] } ``` 告訴他現在`(*left)->next` 的地址是 `0xff` 了 ```graphviz digraph ptr { rankdir=LR; node[shape=box]; ptp[label= "0xff"]; ptr[label= "0x40"]; value[label= "node 2"]; ptp -> ptr[arrowhead=vee, tailclip=true, arrowsize=1] ptr -> value[arrowhead=vee, tailclip=true, arrowsize=1] } ``` 現在 `left` 裡面放的是原本節點指向的下一個了 :::success **指標的指標**:我們發現 `list_concat` 傳入的參數當中，有一個 `node_t **left` ，但是後面卻是傳入 `node_t *right` ，為什麼一個傳入指標的指標，但是另一個傳入的只是指標而已呢?因為我們要修改到實際 `*left` 的尾端，所以傳入指標的指標原因是要**傳址不傳值**，如果我們只是傳入 `node_t *left`的話，只是傳入 left 地址是甚麼(數值)，並不會真正的改動到他的地址，所以只有傳入指標的指標 ```graphviz digraph ptr { rankdir=LR; node[shape=box]; ptp[label= "0xff"]; ptr[label= "0x36"]; value[label= "20"]; ptp -> ptr[arrowhead=vee, tailclip=true, arrowsize=1] ptr -> value[arrowhead=vee, tailclip=true, arrowsize=1] } ``` 以這個例子來說，傳入 `node_t *left`的話，傳入的就只是 `0x36` 這個值而已，知道`0x36` 這個指標代表我們知道如何修改20這個 value ，但是我們想要做的操作是改變這個指標本身，所以必須知道 `0x35` 這個指標的地址，也就是 `0xff` ::: - **`AAA: &right` 、`BBB: &left`** 如果值比 pivot 大加入右 list ，小於或等於加入左 list ，需要特別注意傳入的是 `left` 跟 `right` 的地址，這樣才能真正修改到 `left` 跟 `right` 裡面的內容 - **`CCC: list_concat(&result, pivot); list_concat(&result, right)`** `result`代表的是開頭，一開始是空的，程式碼已經連接好開頭跟左 list 了，所以我們需要再接上 pivot 跟右 list 於其後面。 ### 測試程式使用到 [random](https://linux.die.net/man/3/random)，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator 測試程式的時候，發現幾件事情，首先是 ANSI C 並沒有支援 `random()` 這個函式，所以用 gcc 編譯的時候可以更改成 `rand()` 這樣編譯才會過。並且同樣的執行環境下，無論編譯多少次產生出來的隨機數列結果都是一樣的，原因來自[偽隨機性 (Pseudorandomness)](https://zh.wikipedia.org/wiki/%E4%BC%AA%E9%9A%8F%E6%9C%BA%E6%80%A7)的關係，當一開始 Pseudorandom number 的開始值，也就是種子沒有改變的時候，以這個種子產生的亂數序列是可以預測的(也就是說，其實 `random()` 也只是一個給定輸入產生輸出的函式而已，本身沒有甚麼隨機性，雖然在同一次編譯時同個 `random()` 產生出不同的數字，但是重新編譯會獲得相似出現的順序)。 #### 解決方案: srandom() 用 `srandom(unsigned int seed)` ，以 <time.h> 提供的時間做出"偽亂數"，可以讓初始的種子不一樣，產生的序列也不相同。 ```cpp=94 int main(int argc, char **argv) { size_t count = 20; srandom(time(NULL));//set a random seed based on time node_t *list = NULL; while (count--) list = list_make_node_t(list, random() % 1024); ``` 加上一行 `srandom(time(NULL))` 能夠使 `random()` 的初始種子是不一樣的，這樣產生出來的序列也會不相同。 :::warning :warning: 但是， `srandom()` 或是 `srand()` 均可能產生一些問題，參照 [Random Number Generation](https://inst.eecs.berkeley.edu/~cs161/fa05/Notes/random.pdf): 1. 因為 `srand()` 調用的是時間戳記，而這個時間戳記的單位是用微秒。也就是說，如果快速調用(同個微秒內發生)時，其時間戳記(也就是 seed )是不會改變的，而針對同個 seed 產生出來的 `rand()` 序列也會是相同的。 2. 每次設定隨機種子後，`rand()` 輸出會自動複位到第一個初始值，種子相同，則初值及後續的序列相同，結合 1. 跟 2. ，給出參考範例: ```cpp int foo() { int r; srand((unsigned) time(NULL)); r = rand() % 100; return r; } void main(void) { int i,r; srand((unsigned) time(NULL)); for (i = 0; i < 10; i++) { r = rand() % 100; printf(" %3d", r); } printf("\n"); for (i = 0; i < 10; i++) { printf(" %3d", foo()); } printf("\n"); } ``` 參考輸出為 ``` 23 14 38 28 42 72 70 64 94 0 23 23 23 23 23 23 23 23 23 23 ``` 3. 這讓我們想到另一個問題，萬一我們知道一開始的時間戳記的時候，是不是後面的 `rand()` 也會被隨之破解?答案是可能的，一年的秒數共有$3600×24×365=31,536,000≈2^{25}$秒，我們只要知道這個程式是在哪一年，更好的是哪一個月，哪一天被編譯的，產生出來的亂數種子是有機會被破譯的。 > 關於如果我們能夠成功知道 seed 便可以根據這個 seed 獲得函式產生的一系列輸出這點，應該是所有 4. 輸出並非隨機，如果我們參考[規格書[7.20.2.2]](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) `rand()` 可能的實作過程: ```cpp static unsigned int next = 0; void srand(unsigned int seed) { next = seed; } /* RAND_MAX assumed to be 32767 */ int rand(void) { next = next * 1103515245 + 12345; return (unsigned int)(next/65536) % 32768; } ``` 我們會發現如果知道了 `rand()` 內部亂數產生的方式以及 `RAND_MAX` ，便可以大幅降低破解可能性。舉例來說，低位的 bit 可能是以固定順序出現(因為每次都是×5+5，所以輸出的 LSB 順序為 0,1,0,1...)，這樣會讓輸出的可能性降低至只有$2^{113}$種可能性，並且因為下一個輸出結果取決於上一個，所以如果知道了第一個輸出，後面==接續的輸出將能夠被預測出==! ::: 上面提到，在 C 語言規格書中說明 rand() 的實作方式是透過[線性同餘法](https://en.wikipedia.org/wiki/Linear_congruential_generator)，這個方法是基於初始的一個 seed ，然後用上一次產生的亂數乘上 $a$ 後取 $m$ 餘數:$$X_{n+1}=(aX_n+c)modm$$其中，$m=modulus,a=multiplier,c=increment$對於較小的資料量這個方法實作還不錯，因為快速而且簡單易懂，但是如果多給幾筆資料，則可以輕鬆的攻擊取得參數 $m,a,c$，網友實做[其中一個方法](https://www.itread01.com/ypcfe.html)，只要解線性方程組或是 gcd 就可以取得參數。另外一方面，如果說今天的題目跟資訊安全無關啊為什麼需要討論安全性。線性同餘法仍然存在其他(如隨機性)缺點，像是 1. :warning: 中的第4點，在低位的 bit 出現並不是隨機的 2. 如果不仔細選擇常數a，m和c，則隨機數可能不會覆蓋可能數的整個範圍。 3. 偽隨機數的序列是固定的，所以存在**相關性**，在順序隨機數之間。如果人們使用隨機數在 k 維空間中創建點（與蒙特卡洛方法一樣），則可能這些點將不會填滿空間 ![](https://i.imgur.com/SZYeGVd.png) 左邊是線性同餘法產生的點，可以看到晶格化部隨機的分布情形 #### 解決方法: [Mersenne twister](https://en.wikipedia.org/wiki/Mersenne_Twister) *梅森旋轉隨機算法*是一種 Pseudorandom number generator ，目前被許多程式語言廣泛使用，能夠用於解決古典隨機算法的一些缺點，對於一個 k 位元長度，能夠在[$0,2^k-1$]的區間生成離散型均勻分布的隨機數。這個算法有著非常長的週期$2^{19937}-1$，叫做梅森素數。長周期的優點使得攻擊者不能像是短周期的演算法那樣能夠觀察，記錄和重用周期短的序列從而破解，但是他並不是不可預測的。MT19937算法以624個32位值追蹤狀態。如果攻擊者能夠收集624個序列值，則可以對整個序列（順向和逆向）進行反向工程。 **Mersenne twister的實現方式**: 首先理解 Linear Feedback Shifting Register (線性回授移位暫存器)如何旋轉: :::success TODO:程式碼理解與實現 ::: **實現結果** 我自己還沒寫出測試程式碼，先借用[stack overflow 上別人做的成果](https://stackoverflow.com/questions/45120396/why-does-switching-from-mersenne-twister-to-other-prngs-in-gradient-noise-genera) 展示可以發現視覺化之後，梅森旋轉算法的分布紋路 ![](https://i.imgur.com/bi45Qzn.png) 比 LCG 的均勻不少 ![](https://i.imgur.com/CtVkjIx.png) ==Linux kernel== 根據[維基百科說明](https://zh.wikipedia.org/wiki//dev/random)，Linux kernel 的做法是使用背景噪聲產生真正的亂數， generator 有一個容納噪聲資料的熵池，若熵池空了，對/dev/random的 read operation 將會被阻塞，直到收集到了足夠的環境噪聲為止，由於亂數的產生採取自真實世界中不可預估的噪音，因此在預測難度以及密碼強度都具有比較好的表現。 :::info **Question:** 1. 計算機中為了產生隨機種子，最常看到的方式就是利用`<time.h>`提供以"時間"作為偽亂數的來源，但是無法解決如果在同一微秒中產生多個隨機種子(也就是快速調用)時，產生一樣種子的問題，或許可以利用調動次數( counter )的方式增加一些隨機性，像是每次調用 `srand()` 時乘上 counter 再 mode 、或是用一些 delay 的方式不要在同個毫秒內重複產生種子。但是還有沒有更好的方法呢? 2. 雖然上述說如果知道編譯大概的時間點，可以用高速運算的電腦暴力解出種子，但是實際上這是可能的嗎?或許以毫秒等級產生的隨機性就已經足夠? ::: 但是隨機性本身依舊有些不確定性，我們只能盡量要求產生的隨機數符合數學模型(如卡方分布)的均勻分布狀態，請看笑話: ![](https://i.imgur.com/JiYnnC6.png) ### 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫文章提出的方法主要是用了兩個陣列，`beg[]` 、 `end[]` 去紀錄每一個分割的開頭跟結尾，如果一段排序完畢後會將這段替換成以 pivot 左邊的一段和以 pivot 的右邊，也就是一個 stack 的概念，如果以作者給出的事例舉例來說，第一次排序完會長這樣: |beg|0|1|2|3|4|...| |---|---|---|---|---|---|---| | |0|4| |end|0|1|2|3|4|...| |---|---|---|---|---|---|---| | |3|7| 代表接下來有兩段需要分別排序:**0~3** 以及 **4~7**。對於每一段來說，排序的方式有點像是**大風吹**的感覺。 1. 一開始我們把 pivot 的位子讓出來，這裡 pivot 必須選擇頭，因為後面我們要找比 pivot 小的數字跟他交換，所以**讓出來的位置必須一定在左邊** | piv | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | **4** | 4 | 5 | 3 | 6 | 2 | 8 | 1 | 7 | 2. 從右邊向左找出第一個遇見比 pivot 小的數字(這個數字應該要在 pivot 的左邊)，"坐"到原本 pivot 的位置 | piv | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | **4** | **1** | 5 | 3 | 6 | 2 | 8 | 1 | 7 | 3. 接著從左邊出發，找到第一個比 pivot 大的數字，"坐"到上個移動的數字原本的位置 | piv | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | **4** | 1 | 5 | 3 | 6 | 2 | 8 | **5** | 7 | 4. 重複 2. 3. 直到 L 和 R 重疊，最後把 pivot 塞回去 | piv | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | **4** | 1 | 2 | 3 | **4** | 6 | 8 | 5 | 7 | #### 程式碼實現 ==**程式碼實現**== 根據範例，我們發現單向的 linked list 不能像陣列一樣只是做 L++ 、 R-- 這樣的處理就好，我們要記錄不再是 index 而是 address ，並且**單向的 linked list**不能讓 L 、 R 順利的左右移動，因此引入**雙向的 linked list**實作，在原本的資料結構補上 ```cpp typedef struct __node { int value; int index; struct __node *next; struct __node *prev; } node_t; ``` 因為原本程式碼沒有寫到 `list_free` 、 `list_make_node` 這兩個函式，所以自行添加 ```cpp static void list_free(node_t **list){ while (*list){ node_t *current = *list; *list = (*list)->next; free(current); } } static node_t *list_make_node_t(node_t *list, int ranNum, int index){ node_t *new; if (!(new = malloc(sizeof(node_t)))) return NULL; if (list) list->prev = new; new->value = ranNum; new->prev = NULL; new->next = list; new->index = index; return new; } ``` 主要的程式碼的部分 ```cpp= void quicksort(node_t **list) { node_t *L, *R, *beg[MAX_LEVEL], *end[MAX_LEVEL], *swap; int i = 0, piv; beg[0] = *list; end[0] = list_tail(*list); while (i >= 0) { L = beg[i]; R = end[i]; if (L->index < R->index) { piv = L->value; while (L->index < R->index) { while (R->value >= piv && L->index < R->index) R = R->prev; if (L->index < R->index){ L->value = R->value; L = L->next; } while (L->value <= piv && L->index < R->index) L = L->next; if (L->index < R->index){ R->value = L->value; R = R->prev; } L->value = piv; if (L->next) beg[i+1] = L->next; else beg[i+1] = L; end[i+1] = end[i]; end[i++] = L; if (end[i]->index - beg[i]->index > end[i-1] - beg[i-1]){ swap=beg[i]; beg[i]=beg[i-1]; beg[i-1]=swap; swap=end[i]; end[i]=end[i-1]; end[i-1]=swap; } } } else { i--; } } } ``` 這邊 `beg[]` 跟 `end[]` 儲存的是 `node_t` 節點，內部新增了 index 去紀錄當前位置(因為原本作者使用 array 紀錄，改成用 `node_t` 的方式紀錄後只紀錄了指標，無法直接取得 index 之間前後的關係，所以才需要花費額外空間紀錄 index) ==**使用迴圈版本的好處**== 根據作者提到他實做的好處，有以下提到的幾個： 1. **省下 function call 所浪費的時間**。 2. **不使用 `stack` 來除存數據**，這邊的 `stack` 指的可能是程式執行的時候記憶體配置的 `stack` ，紀錄的區域變數可能是來自呼叫上一層 function 的變數狀態以及參數等等，雖然在 recursive 的實作方式中看起來程式碼比較簡潔，但是背後可能需要花費大量的記憶體空間去記錄這些區域變數，如果在 worse case 或是整個 list 太長的時候，是有可能發生 stack overflow 的，這時候會出現 segmentation fault 。但是像作者一樣使用有限制的 array (其實也就是把原本看不見的 stack 用我們可以掌控的方式實作)來判斷會不會 overflow 。作者在這邊還實作了一個改良版，也就是我程式碼 **36-40行**的地方能夠把比較短的分割先拿出來繼續排序，這樣可以大幅降低 overflow 的機率。 3. **不需要 SWAP** ，雖然 SWAP 可以用 macro 定義就好，但是每次 swap 都會使用一個多的儲存空間 temp ，作者這邊是使用 pivot 離開後留下的空位當作交換的 buffer ，不需要用多的 temp 暫存 4. **減少移動次數**，L 跟 R 分別向中間移動的時候，如果遇到不須交換的節點(以 L 來說是比較小的節點，以 R 來說是比較大的節點)會直接跳過不需要搬動或是交換。 ==**邊界條件處理**== 原本的程式碼在最後更新 `beg[]` 跟 `end[]` 的時候，狀態會是 L 跟 R 重疊(因為只有 L=R 的時候才會跳出迴圈)，但是在 L 與 R 重疊的 index 如果是最後面的話，`beg[i+1]=L+1;` 這個敘述會出現問題，因為起始點會超過邊界 |beg|0|1|2|3|4|...| |---|---|---|---|---|---|---| | |0|8| |end|0|1|2|3|4|...| |---|---|---|---|---|---|---| | |7|7| 起點是 8 ，終點是 7 ?這邊需要加上一個判斷 ```cpp= if (L->next) beg[i+1] = L->next; else beg[i+1] = L; ``` :::success 可以改進的地方： 1. 因為需要滿足作者提出的演算法，所以對於每個 `node_t` 新增了額外的儲存空間去紀錄上一個節點以及 index。 ::: :::success **Thinking:** 1. 函式呼叫( function call )實際需要花費的時間是如何呢?有甚麼方式可以實測不用 function call 節省的效率? ::: ### 仿效 Linux 核心的實作並予以簡化，探討 Linux 的 [linked list](https://github.com/sysprog21/linux-list) 和上述程式碼的落差，並改寫 [linux-list](https://github.com/sysprog21/linux-list) 的 quick sort 範例，避免使用遞迴呼叫 ==閱讀 `list.h`== ```cpp= #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` - **`container_of`** : 傳入某個 struct 內部成員的指標、所屬類型 - **`list_add:`** 跟資料結構中的插入新節點一樣，在 `head` 跟 `node1` 之間插入 ```graphviz digraph ptr { rankdir=LR; node[shape=box]; head[label= "head"]; a[label= "node1"]; b[label= "node2"]; c[label= "node3"]; extra[label="Newnode"]; head -> a[arrowhead=vee, tailclip=true, arrowsize=1] b -> a[arrowhead=vee, tailclip=true, arrowsize=1] c -> b[arrowhead=vee, tailclip=true, arrowsize=1] a -> head[arrowhead=vee, tailclip=true, arrowsize=1] a -> b[arrowhead=vee, tailclip=true, arrowsize=1] b -> c[arrowhead=vee, tailclip=true, arrowsize=1] rank=same } ``` ```graphviz digraph ptr { rankdir=LR; node[shape=box]; head[label= "head"]; a[label= "node1"]; b[label= "node2"]; c[label= "node3"]; extra[label="Newnode"]; a -> extra[arrowhead=vee, tailclip=true, arrowsize=1] head -> a[arrowhead=vee, tailclip=true, arrowsize=1] b -> a[arrowhead=vee, tailclip=true, arrowsize=1] c -> b[arrowhead=vee, tailclip=true, arrowsize=1] a -> b[arrowhead=vee, tailclip=true, arrowsize=1] b -> c[arrowhead=vee, tailclip=true, arrowsize=1] b -> c[arrowhead=vee, tailclip=true, arrowsize=1] subgraph g{rank=same;head;extra;} } ``` ```graphviz digraph ptr { rankdir=LR; node[shape=box]; head[label= "head"]; a[label= "node1"]; b[label= "node2"]; c[label= "node3"]; extra[label="Newnode"]; a -> extra[arrowhead=vee, tailclip=true, arrowsize=1] head -> a[arrowhead=vee, tailclip=true, arrowsize=1] b -> a[arrowhead=vee, tailclip=true, arrowsize=1] c -> b[arrowhead=vee, tailclip=true, arrowsize=1] a -> b[arrowhead=vee, tailclip=true, arrowsize=1] b -> c[arrowhead=vee, tailclip=true, arrowsize=1] extra -> a[arrowhead=vee, tailclip=true, arrowsize=1] subgraph g{rank=same;head;extra;} } ``` ```graphviz digraph ptr { rankdir=LR; node[shape=box]; head[label= "head"]; a[label= "node1"]; b[label= "node2"]; c[label= "node3"]; extra[label="Newnode"]; a -> extra[arrowhead=vee, tailclip=true, arrowsize=1] head -> a[arrowhead=vee, tailclip=true, arrowsize=1] b -> a[arrowhead=vee, tailclip=true, arrowsize=1] c -> b[arrowhead=vee, tailclip=true, arrowsize=1] a -> b[arrowhead=vee, tailclip=true, arrowsize=1] b -> c[arrowhead=vee, tailclip=true, arrowsize=1] extra -> a[arrowhead=vee, tailclip=true, arrowsize=1] extra -> head[arrowhead=vee, tailclip=true, arrowsize=1] subgraph g{rank=same;head;extra;} } ``` ```graphviz digraph ptr { rankdir=LR; node[shape=box]; head[label= "head"]; a[label= "node1"]; b[label= "node2"]; c[label= "node3"]; extra[label="Newnode"]; a -> extra[arrowhead=vee, tailclip=true, arrowsize=1] head -> extra[arrowhead=vee, tailclip=true, arrowsize=1] b -> a[arrowhead=vee, tailclip=true, arrowsize=1] c -> b[arrowhead=vee, tailclip=true, arrowsize=1] a -> b[arrowhead=vee, tailclip=true, arrowsize=1] b -> c[arrowhead=vee, tailclip=true, arrowsize=1] extra -> a[arrowhead=vee, tailclip=true, arrowsize=1] extra -> head[arrowhead=vee, tailclip=true, arrowsize=1] subgraph g{rank=same;head;extra;} } ``` - **`list_add_tail:`** 跟上面的作法一樣，但是因為插入的地方從 `head` `node1` 之間變成是 `head` `node3` 也就是最後一個 node 之間，所以 - **`list_del`**：移除節點，但是並沒有將這個節點的空間釋出(沒有 free )，而呼叫他的 `list_del_init` 除了移出這個節點以外還會將這個節點恢復回剛剛初始化過的狀態 - **`LIST_POISONING`**: 當想要存取非法記憶體的時候喚醒 - **`list_is_singular`**: 是不是只接了一個節點在 `head` 的後面 - **`list_splice`** 拼接，將 `list` 後面接的一串整個塞進 `head` 跟它原本後面接的一串之間 - **`list_cut_position`** 以 `node` 當作切割點，在 `node` 之前的(包含自己)會被分到一個以 `head_to` 的 list ，以後的 list 會被重新連結回原本的 `head_from`。 - **` list_move`** 將 `node` 拿出之後放到 list 的最前面 ( `head` ) ==分析 `quicksort.c`== ```cpp= static void list_qsort(struct list_head *head) { struct list_head list_less, list_greater; struct listitem *pivot; struct listitem *item = NULL, *is = NULL; if (list_empty(head) || list_is_singular(head)) return; INIT_LIST_HEAD(&list_less); INIT_LIST_HEAD(&list_greater); pivot = list_first_entry(head, struct listitem, list); list_del(&pivot->list); list_for_each_entry_safe (item, is, head, list) { if (cmpint(&item->i, &pivot->i) < 0) list_move_tail(&item->list, &list_less); else list_move(&item->list, &list_greater); } list_qsort(&list_less); list_qsort(&list_greater); list_add(&pivot->list, head); list_splice(&list_less, head); list_splice_tail(&list_greater, head); } ``` 我們觀察比對 [linux 核心的實作](https://github.com/torvalds/linux/blob/master/include/linux/list.h)，可以發現 double linked list 頭尾是相連的( circular )，分析 circular linked list 的好處如下 1. `*prev` `*next` 不會出現指向 NULL 指標 2. 如果想要實作 queue 非常方便 3. 方便對 linked list 的尾端做操作，只需要一步就可以，不需要經過整個 list ，這也是為什麼在 linux 的 `list.h` 中一個函式常常會出現另一個對尾端操作的變化版 4. 雙向的好處可以讓指標移動靈活性較高，雖然單向足以完成許多排序搜尋演算法且用到指標比較少，但是因為只能單向移動，對指針移動的靈活性差，而且某些時候可能產生 memory leak 的現象 :::success **Question:** 我們發現在 `list_qsort` 內部還有一個函式 `list_for_each_entry_safe` ，這蠻令我意外的，因為 C 應該是不支援巢狀函式的寫法才對， GNU C extension 有支援巢狀函式，但是這邊看起來並非如此，或許在 list.h 當中 #define `list_for_each_entry_safe (item, is, head, list)` 會用整串 for 替換掉 `list_for_each_entry_safe` ?但是這麼做的原因是甚麼呢? ```cpp=426 #define list_for_each_entry_safe(entry, safe, head, member) \ for (entry = list_entry((head)->next, __typeof__(*entry), member), \ safe = list_entry(entry->member.next, __typeof__(*entry), member); \ &entry->member != (head); entry = safe, \ safe = list_entry(safe->member.next, __typeof__(*entry), member)) ``` ::: ### 研讀冼鏡光教授撰寫的 [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)，思考高效率的 linked list 排序演算法在冼鏡光教授的文章當中，除了表明 Carraway (我查不到這個名字是誰)提出的 sediment sort 並不是在 linked list 中最快速有效率的程式碼，後面針對藉由 linked list 實作的搜尋演算法進行了記憶體、效能等指標的分析 - **Double linked list**:舉例像是 sediment sort 、 tree sort 都是屬於此類，原因是對於一個二元子樹來說， `prev` `next` 兩個指標足以表達 - **Single linked list**:提到如 selection sort 、 insersion sort 、 bubble sort ，雖然 shell sort 理論上用 single linked list 是可行的，但是因為 shell sort 會有一個跨 node 比較的動作，對於 linked list 無法直接用 index 取得資料，實作起來會比較困難。另外，有些版本的 quick sort （像是上面問題二實作的迴圈版本使用了「蠟燭兩頭燒」的方式從頭尾向中間靠攏，這種方式就必須使用 double linked list實做了 - **效能評比**:分成了 $O(n^2)$ : Double-Bubble 、 Single-Bubble 、 Selection Sort 以及 $O(nlog(n))$ : Merge Sort 、 Quick Sort 、 Tree Sort 兩種，觀察到 Quick Sort 跟 Tree Sort 兩者效率是最高的，但是因為輸入是隨機的，所以沒有考慮到某些極端狀況，如果序列呈現*反向排序*的話， Quick Sort 跟 Tree Sort 的特性導致表現反而會下降許多。對於有多個重複多次元素的序列(我現在想到的是身高、氣溫之類的)， Quick Sort 的表現將會比較突出，因為和 pivot 大小相同的元素不會繼續進入子序列。 > :bulb:想法是，如果對輸入的數列進行預處理的話，是不是就可以針對不同特性的數列搭配不同演算法呢? > :bulb:之前的資料結構有學過混合型的排序演算法，像是 merge sort 有個 partition 的動作，如果分割到太小的 subsequence 的話，可能會因為頻繁的 function call 而花不少時間，所以做法是分割到一定程度的子序列之後，如 n=100 ，就用 insertion sort 或是 selection sort 排序後再往上 merge :::success TODO:如何將冼教授的想法貫徹至程式碼中? ::: ###### tags: `linux2021`

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.