# 2021q1 Homework1 (quiz1) contributed by < tigger12613 > > [2021q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz1) > [GitHub](https://github.com/tigger12613/quiz1) ## 作業要求 - [x] 1. 解釋程式運作原理，搭配 Graphviz，比照 Linked List 練習題 在 HackMD 筆記上視覺化展現 - [x] 1.1 測試程式使用到 random，多執行幾次可發現輸出結果相仿，請修正，並引入其他 Pseudorandom number generator - [x] 2. 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫 - [ ] 3. Linux 核心內部也有 linked list 實作，但是 circulr doubly-linked list，[linux-list](https://github.com/sysprog21/linux-list) 仿效 Linux 核心的實作並予以簡化，在 examples/ 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫 - [ ] 4. 研讀 Ching-Kuang Shene (冼鏡光) 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中 ## 在電腦上重現程式 quiz 缺少兩個函式，予以實作 cpp static node_t *list_make_node_t(node_t *list, long num) { node_t *tmp = malloc(sizeof(node_t)); if (!tmp) { return list; } tmp->value = num; tmp->next = list; return tmp; } static void list_free(node_t **list) { node_t *tmp; while (*list) { tmp = *list; *list = (*list)->next; free(tmp); } }  運作正常  shell $valgrind --leak-check=full ./link_list ==45637== Memcheck, a memory error detector ==45637== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==45637== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info ==45637== Command: ./link_list ==45637== NOT IN ORDER : 1016 84 706 124 326 483 763 498 939 186 205 809 236 74 255 81 115 105 966 359 IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016 ==45637== ==45637== HEAP SUMMARY: ==45637== in use at exit: 0 bytes in 0 blocks ==45637== total heap usage: 21 allocs, 21 frees, 1,344 bytes allocated ==45637== ==45637== All heap blocks were freed -- no leaks are possible ==45637== ==45637== For lists of detected and suppressed errors, rerun with: -s ==45637== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)  ## 程式運作過程 ### Main 產生長度為 20 的 linked list 並隨機給予 0 ~ 1023 的數值，列印 linked list ，排序，再列印 linked list ，確認排序是否正確，free linked list cpp int main(int argc, char **argv) { size_t count = 20; node_t *list = NULL; while (count--) list = list_make_node_t(list, random() % 1024); list_display(list); quicksort(&list); list_display(list); if (!list_is_ordered(list)) return EXIT_FAILURE; list_free(&list); return EXIT_SUCCESS; }  ### List add node 將節點插入 list 的頭部 cpp static inline void list_add_node_t(node_t **list, node_t *node_t) { node_t->next = *list; *list = node_t; }  graphviz digraph a { rankdir=LR; node[shape=box]; "node"->"head" "head"->"..." "..."->"tail" }  ### List concat 將 right list 鏈結在 left list 後面 cpp static inline void list_concat(node_t **left, node_t *right) { while (*left) left = &((*left)->next); *left = right; }  graphviz digraph a { rankdir=LR; node[shape=box]; node1 [label = "..."] "left"->"..." "..."->"left tail" "left tail" -> "right"[color = red label="concat"] "right"->node1 node1->"right tail" }  ### Quick sort cpp= 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 ? &right : &left, n); } quicksort(&left); quicksort(&right); node_t *result = NULL; list_concat(&result, left); list_concat(&result, pivot); list_concat(&result, right); *list = result; }  這段用於把 pivot 拆出來 cpp=6 node_t *pivot = *list; int value = pivot->value; node_t *p = pivot->next; pivot->next = NULL;  while loop 把比 pivot 大的放到 right list 上面，小或等於的放到 list list 上面 cpp=12 while (p) { node_t *n = p; p = p->next; list_add_node_t(n->value > value ? &right : &left, n); }  graphviz digraph sort{ rankdir=LR; node[shape=box]; right left pivot n1 [label = "> pivot"] n2 [label = " <= pivot"] right-> n1 left->n2 }  接下來排序 left list and right list ，然後接起來 cpp=18 quicksort(&left); quicksort(&right); node_t *result = NULL; list_concat(&result, left); list_concat(&result, pivot); list_concat(&result, right); *list = result;  graphviz digraph sort{ rankdir=LR; node[shape=box]; right result pivot { rank = same left -> lleft } lright [label = " sorted and > pivot"] lleft [label = " sorted and <= pivot"] { rank = same right-> lright } lleft->pivot [label = "concat" color = "red"] pivot->lright [label = "concat" color = "red"] result->lleft }  ### 隨機種子 加上隨機種子在使用 random() 之前就可以每一次都產生不同的隨機數 cpp srand(time(NULL));  PRNG 使用初始值產生一串帶有隨機性質的數字序列，如果初始值相等，序列也會相等，因此不是真隨機。在使用時使用 time 作為初始值可以讓初始值看似隨機數，產生的數字序列也會看起來隨機。 :::warning 倘若 time 函式得到的時間數值是可預測的話，PRNG 的輸出也可預測，該如何改進？留意到 entropy 相關討論 :notes: jserv ::: ## Iterative quicksort 新增一個 stack 用於紀錄還未排序的 linked list sorted 紀錄已經排序好的範圍 每次 loop 從 stack 中最右邊的 linked list 進行切分，如果只有一個節點，代表這個節點是 stack 上數值最大的節點，並且小於等於 sorted 鏈上的每一個節點，所以將其放到 sorted 鏈 的第一個上，然後從 stack 上移除($i--$)，持續重複這個過程直到 stack 為空。 cpp void quicksort_iterative(node_t **list) { #define MAX_LEVELS 1000 if (!*list) return; int i = 0, j = 0; node_t *stack[MAX_LEVELS]; node_t *sorted; sorted = NULL; stack[0] = *list; while(i>=0 && i<MAX_LEVELS){ if(!stack[i]){ i--; continue; } if(!stack[i]->next){ stack[i]->next = sorted; sorted = stack[i]; i--; continue; } node_t *pivot = stack[i]; 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 ? &right : &left, n); } stack[i] = left; stack[i+1] = pivot; stack[i+2] = right; i +=2; } *list = sorted; }  接著對效能測試，重複 5000 次對長度 1000 的 list 做排序 iterative 版本快了46% 的速度 | recursive version | iterative version | | ----------------- | ----------------- | | 0.832864 sec | 0.567636 sec | MAX_LEVELS的數值選擇應該考慮到 worst case 的狀況，如果每一次的 pivot 都選到最小的那一個 也就是說 left 都為 NULL ，也就是需要$2 \times (n-1)\$ 個位置去儲存 linked list node graphviz digraph { node [color=black shape=none margin=0 height=.3 ] values [label=< <table border="0" cellborder="1" cellspacing="0"> <tr> <td port="f0" bgcolor = "lightyellow"> NULL </td> <td port="f1" bgcolor = "lightyellow"> pivot1 </td> <td port="f2" bgcolor = "lightyellow"> NULL </td> <td port="f3" bgcolor = "lightyellow"> pivot2 </td> <td port="f4" bgcolor = "lightyellow"> ... </td> <td port="f5" bgcolor = "lightyellow"> NULL </td> <td port="f6" bgcolor = "lightyellow"> pivot_end </td> <td port="f7" bgcolor = "lightyellow"> right_end </td> </tr> </table> >]; "stack"->values:f0 { rank=same; "stack"; values } }  :::warning MAX_LEVELS 數值設定的依據為何？做數學分析來指定更適切的數值。 :notes: jserv :::