2025q1 Homework1 (lab0)

# 2025q1 Homework1 (lab0) contributed by < `CodeStone1125` > ### Reviewed by `SimonLiu423` 1. `queue.h` 中已有 `q_release_element()` 函式可以去釋放指定的 element，為了增加可讀性及可維護性，建議將 `q_free()` 中釋放節點的部分改為利用這個函式達成。 2. > 另外也許可以結合 queue_contex_t 的使用在每次對佇列的操作都對 queue_contex_t.size 進行佇列長度的維護這樣的話呼叫 q_size 就直接回傳 queue_contex_t.size 即可。考量到封裝性，`queue_contex_t` 有種將 queue 包起來的感覺，提供關於該 queue 的一些額外資訊，我想透過 queue 的基本操作獲取外部的 struct 資訊也許不是一個好的方法？歡迎其他人提供更多想法。此外，考量到使用情況，若大部分時間只會對 queue 進行新增/移除元素，而不會詢問 queue 的大小，則會花費大量不必要的時間去更新 size 資訊。 3. Sorting Methods Comparison 的圖表中，X 軸的單位建議可以以 $10^3$(k) 為單位，顯示的數值便可從 $100000$, $200000$, ... 變成 $100$, $200$, ...，增加圖表的可讀性。 ### Reviewed by `NeedToDebugMyLife` 1. Commit [25c014d](https://github.com/sysprog21/lab0-c/commit/25c014daeb2f889c9e72f7368d73f42edc4574e2) 中，可以使用 `!head` 的寫法來替代 `head==NULL`，這樣的寫法更為精簡，`head->next == head` 的寫法可以使用 `<list.h>` 中的 `list_empty()` 來替代。 2. Commit [467decc](https://github.com/sysprog21/lab0-c/commit/467decc5a599d1f4a984eeaab6d3dfd66ea114fc) 中，可以透過將節點 "移除後再插入" 的方式完成節點的搬動，這邊可以直接使用 `<list.h>` 中的 `list_del()` 和 `list_add()` 這兩個巨集函式來完成，或者直接使用 `<list.h>` 中的 `list_move()`，這樣可以有效提高程式碼的可讀性。 {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 46 bits physical, 48 bits virtual CPU(s): 28 On-line CPU(s) list: 0-27 Thread(s) per core: 2 Core(s) per socket: 20 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 183 Model name: Intel(R) Core(TM) i7-14700 ＠ 1.50 GHz Stepping: 1 CPU MHz: 1100.3190 CPU max MHz: 5400.0000 CPU min MHz: 800.0000 BogoMIPS: 4224.00 Virtualization: VT-x L1d cache: 768 KiB L1i cache: 1 MiB L2 cache: 28 MiB L3 cache: 33 MiB NUMA node0 CPU(s): 0-27 ``` ## 教材閱讀 - [x] [你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-linked-list) - [x] [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) - [x] [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory) - [x] [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) - [ ] [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable) ## 佇列操作的程式碼實作 ### q_new > Commit [8a99fa7](https://github.com/sysprog21/lab0-c/commit/8a99fa70e8a3be4825058d84fb8b12603322727e) 使用 `malloc` 避免物件的生命週期隨著 `q_new` 一起結束。 > Commit [999800f](https://github.com/sysprog21/lab0-c/commit/999800f9fbdb0c2638afa8a530c94cdd0009c90e) 研讀 `list.h` 後使用 `INIT_LIST_HEAD` 簡化程式。 ### q_free 最一開始構思的程式碼有以下問題： 1. 沒有仔細研讀 `qtest.c` 導致沒有發現不需要在函式中釋放 `queue_contex_t` 的記憶體。 2. 誤用 `list_for_each` 而非 `list_for_each_safe` 導致 segemnt fault。修正後版本： > Commit [e07f9bb](https://github.com/sysprog21/lab0-c/commit/e07f9bba950e44dda16d5491d36173b41bc4a71e) ```c void q_free(struct list_head *head) { if (head == NULL) return; struct list_head *node; struct list_head *safe; list_for_each_safe (node, safe, head) { element_t *e_new = list_entry(node, element_t, list); if (e_new->value) free(e_new->value); free(e_new); } free(head); return; } ``` ### q_size > Commit [25c014d](https://github.com/sysprog21/lab0-c/commit/25c014daeb2f889c9e72f7368d73f42edc4574e2) 我使用了 `list_for_each_safe` 走訪佇列的每一個元素並計算佇列長度但因為操作沒有涉及元素的刪除應該使用 `list_for_each` 即可可以省下一半的走訪成本。另外也許可以結合 `queue_contex_t` 的使用在每次對佇列的操作都對 `queue_contex_t.size` 進行佇列長度的維護這樣的話呼叫 `q_size` 就直接回傳 `queue_contex_t.size` 即可。 ### q_del_mid > Commit [55147bf](https://github.com/sysprog21/lab0-c/commit/55147bfb01df095ab8a43017c1c38d60fd322c82) 參考指標篇的快慢指標實作 `q_del_mid`，值得注意的是 `slow` & `fast` 指標的起始點從 `head` 或是 `head->next` 結果是一樣的，因為已經設定了只要佇列長度小於1就不會進入迴圈計算而在佇列長度大於等於2的情況下兩者結果一樣，但是 `head->next` 可以減少一次迴圈次數所以我認為是更優異的選擇。 ```c struct list_head * slow = head->next; for(struct list_head * fast = head->next; fast->next!=head && fast->next->next!=head; fast=fast->next->next){ slow = slow->next; } ``` > Commit [5afc936](https://github.com/sysprog21/lab0-c/commit/5afc936b7bd41ca15b82dee09cdbf16bbb75e0c1) 這個提交修正了初版沒有手動釋放包含 `mid` 的元素記憶體空間，導致的記憶體洩漏。 ```diff + element_t *e = list_entry(slow, element_t, list); + free(e->value); + free(e); ``` ### q_insert_head ＆ q_insert_tail > q_insert_head：Commit [4a12cd0](https://github.com/sysprog21/lab0-c/commit/4a12cd04b49a7d4c4ef81fec8cb86bb212ba7a83) > q_insert_tail：Commit [879b201](https://github.com/sysprog21/lab0-c/commit/879b201464dd13df0008204a13790ae6d7edd5a5) > 插入在開頭和結尾的邏輯類似，差別在於只在於透過開頭的 `->prev` 存取結尾來操作。並且二者都要針對當前佇列是否為空做處理。 ```diff + element_t *e_new = (element_t *)malloc(sizeof(element_t)); + e_new->value = (char *)malloc(sizeof(char)*(1+strlen(s))); ``` 使用 `malloc` 分配記憶體空間到堆積避免插入的 `element_t` 及其中的物件生命週期隨著函式結束終止產生 `dangling pointer` 問題。 `malloc` 回傳的 `void *` 是不可以直接進行物件存取，要透過強制轉型成適配的資料型態以作進一步操作。 > Dangerous function detected in strcpy(e_new->value, s); > Read 'Common vulnerabilities guide for C programmers' carefully. 針對 `strcpy` 導致可能發生的溢位問題使用 `strlcpy` 限制使用的記憶體位址範圍防範。 ### q_remove_head & q_remove_tail > q_remove_head：Commit [5ad38c7](https://github.com/sysprog21/lab0-c/commit/5ad38c74582044d7abc519495f233dd160a5f12c) > q_remove_tail:：Commit [16be85b](https://github.com/sysprog21/lab0-c/commit/16be85b7160213611959ae0480ebc508304148a6) 需要注意的點和實作邏輯和 [q_insert_head ＆ q_insert_tail](https://hackmd.io/gKRaBCWZR3abBEfS8jBlLg#q_insert_head-%EF%BC%86-q_insert_tail) 類似故不贅述。 > Commit [4070736](https://github.com/sysprog21/lab0-c/commit/4070736a2c77dbb91e0c9cf4cac8347f5ea0131a) 這次提交修正了對於 `strlcpy` 理解不完全輸入錯誤的參數導致的無法通過 `truncated strings` 的測試。 ### q_ascend & q_descend > Commit [e43716f](https://github.com/sysprog21/lab0-c/commit/e43716f8ad078685e95019a074ca2f5bd5126888) `q_ascend` 和 `q_descend` 的實作邏輯類似 1. 利用堆疊儲存元素 2. 當下在堆疊頂端的元素嚴格大於（小於）當下的檢查的元素 3. 直到堆疊頂端不再嚴格大於（小於）當下的檢查的元素 4. 將堆疊的結果放回佇列中並釋放堆疊 ### q_reverseK & q_reverse > q_reverseK：Commit [5937720](https://github.com/sysprog21/lab0-c/commit/59377209931db7bb8ecdf97ac53470800e36841e8) > q_reverse：Commit [904be06](https://github.com/sysprog21/lab0-c/commit/904be06ca15c34bcaceca54fee4374c23233b0c6) `q_reverseK` 的做法利用兩個指標 `start` 和 `end`：用 while 迴圈走訪整個佇列，`start` 和 `end` 放在第一個元素並且 `end` 持續走訪佇列每當 `end` 向前走訪 K-1 個元素則用另一個 `tmp` 搭配 `list_add_tail` 反轉佇列在放回原本的佇列中。此外我的 `q_reverse` 是 `q_reverseK` 的特例 `q_size == K` ### q_delete_dup > Commit [672cee2](https://github.com/sysprog21/lab0-c/commit/672cee2b21ce8b65d8708d7469648f0072b05ad7) 首先我的想法是： 1. 利用 `q_sort` 將所有重複的元素排序在一起 2. 使用 `list_for_each_safe` 走訪所有元素 3. 兩兩比較確認是否有的重複元素，利用 `dup` 記錄當前的元素是否和下一個元素重複， - 如果重複，刪除當前的元素`dup` 改成 true。 - 如果沒有重複則把當下元素加入 `tmp` 暫時存放。 4. 當 `dup == true` 時可以知道當前的元素是重複的（即使當下兩兩比較的元素不同），因此刪除當前的元素並將 `dup` 改回 false。 5. 最後把 `tmp` 中不重複元素放回原本的佇列。 ### q_swap > Commit [467decc](https://github.com/sysprog21/lab0-c/commit/467decc5a599d1f4a984eeaab6d3dfd66ea114fc) 在迴圈中每兩個一組 `<first, second>` 的進行交換，每一次迴圈 `first` 指標指向下兩個元素並且將 `swp_tmp` 指向 `second` 進行元素的刪除和加入，此處應可用 `list_del_init` 簡化程式碼。 ```diff swp_tmp->next = first; first->prev = swp_tmp; + first = first->next; - first = first->next->next; ``` 另外，測試結果中發現我使用交換的方式，並且交換完後使用 `first->next->next` 存取下一對元素會出現錯誤，因為 `first` 經過交換後實際上只需要使用 `first->next` 即可存取到下一對元素的 `first`。以下是錯誤更正前的執行結果: ``` l = [a b c d e f] cmd> swap l = [b a c e d f] ``` ### q_sort > Commit [a14ee65](https://github.com/sysprog21/lab0-c/commit/a14ee65c6c7887d62a23f9a58765330869d78ea7) ![image](https://hackmd.io/_uploads/SJMDaBdjkx.png) 這個提交是我實作的 stable 的 `merge sort` ，利用遞迴版本 `q_sort` 切割佇列元素，並且用 `mergeTwoList（left, right）` 排序並結合分為兩種情況： 1. `left`， `right` 都非空及 `NULL` 2. 兩者其中一個是空或 `NULL` 情況1.需要分別比較兩者的最小元素比較小的元素來做合併，並重複比較直到情況2.後直接將剩餘的元素合併進入結果即可： - 參考了 [lib/list_sort.c](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-f%3Fstext%3D1546%253A80%253A0%253A1741344947%253AJ_nGlo) 利用 `strcmp >= 0` 來保證排序的穩定性 #### Segment Fault 我原本的思路是在 `mergeTwoList` 使用額外建立 `result` 儲存合併結果在情況2.後直接將剩餘的元素合併進入 `result` 並回傳。但是 `result` 是在 `mergeTwoList` 中建立的，物件的生命週期和函式運行週期綁定，所以回傳後再去存取 `result` 就會導致 Segment Fault。 ```diff if (!list_empty(left)) { - list_splice(left, &result); - return &result; + list_splice(&, left); + return left; } else { - list_splice(right, &result); - return &result; + list_splice(&result, right); + return right; } ``` 參考了 [alexc-313](https://hackmd.io/@alex-c1234/linux2025-homework1#q_sort) 情況2.的做法將 `result` 利用 `list_splice` 加入 `left` 或 `right`並回傳，我認爲使用指標的指標可以進一步把回傳值的部分移除。 ### q_merge 觀察 `qtest.c` 發現整體架構中有四種物件： - list_head：實際用來管理佇列的物件 - element_t：用於儲存佇列中的元素 - queue_context_t：用於鏈結和統計單一佇列資訊 - queue_chain_t：用於鏈結和統計所有佇列資訊 > Commit [324ef82](https://github.com/sysprog21/lab0-c/commit/324ef82dda4073dacef1d5f51dda82ab6fb547e0) `q_merge` 需要存取及管理到 `queue_chain_t` 和 `queue_context_t` 的部分。我目前的做法將每一輪都拿第一個佇列來做 `mergeTwoList`，導致第一個佇列的元素數特別多又做了很多次額外比較操作，如果能把這部分也改成 buttom-up 最後再把結果合併到第一個佇列應該可以提高效能。此外這個做法有一些記憶體洩漏問題沒有被解決依據 `queue.h` 需求必須把第一個佇列以外的佇列變成 NULL-queue 但是直接將佇列變成 NULL-queue 卻沒有初始化 `list_head` 會導致記憶體洩漏，因為不知道指標會指向哪裡。但在此同時直接在函式中呼叫 `free()` 釋放記憶體又是不被允許的，我有嘗試過將變成 NULL-queue 後呼叫 `INIT_LIST_HEAD` 或反過來的做法都會導致 Segment Fault，但不正確初始化會導致後續 `list_head` 的釋放出現記憶體洩漏，我目前還沒有找到解法先做紀錄。 ```diff ctx->q = NULL; + INIT_LIST_HEAD(ctx->q); ``` > Commit [4b0a9be](https://github.com/sysprog21/lab0-c/commit/4b0a9be414bdcb0a87f40c4e938a3ed00247dcc3) 參考 [allen741](https://hackmd.io/@wMTPWBL3SY-hXZO6zn-QmQ/ryamiY6cJx#q_merge) 的做法利用 `list_splice_init` 將所有佇列的元素移到第一個佇列再做 `q_sort`，這方法可以順利初始化並避免記憶體洩漏但是會導致已經排序過的序列再次排序造成額外的比較次數，這方法就算所有序列都沒有排序過也是用算是一個更廣泛的解法，但`list_splice_init` 的方式避免了 `mergeTwoList` 不同佇列間的元素比較，哪個方法比較好要透過實際的效能測量確定。 ## 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L13) ### 研讀 Linux 核心原始程式碼 **施工中** ### 嘗試引入 `list_sort.c` 到 lab0-c 專案 > Commit [93c6190](https://github.com/CodeStone1125/lab0-c/commit/93c6190494fc48fbe7530b80171bf393798d71f6) #### 修改 `list_sort.c` 我參考 [kart81604](https://hackmd.io/@kart81604/HkGHY1cTs#%E5%B0%87-liblist_sort-%E5%BC%95%E5%85%A5%E8%87%B3-lab0-c-%E5%B0%88%E6%A1%88) 的做法嘗試引入linux核心風格的程式碼到 lab-0-c： ```c // original version __attribute__((nonnull(2,3,4))) static struct list_head *merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b); __attribute__((nonnull(2,3,4,5))) static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, struct list_head *a, struct list_head *b); __attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp); ``` 為了引入這段程式碼我做了以下改寫： 1. 我移除了一些額外的部分像 `priv` `like` 和 `unlike` `__attribute__`， 2. 把 `merge`，`merge_final`，`list_sort` 加上前綴 `lx_` 方便識別 3. 把 `cmp` 用 `strcmp` 代替 ```c static struct list_head *lx_merge(struct list_head *a, struct list_head *b); static void lx_merge_final(struct list_head *head, struct list_head *a, struct list_head *b); void lx_list_sort(struct list_head *head); ``` 針對我做了以上改變後遇到執行 `lx_sort` 遇到 `segment fault`，透過`debug.py` 訊息發現問題出在 439 行因為我在取得 `element_t` 物件時錯誤使用成 `list_first_entry` 而非 `list_entry` 導致。 ```python Program received signal SIGSEGV, Segmentation fault. 0x000055555555c14d in lx_merge (a=a@entry=0x55555556a708, b=0x55555556a678) at queue.c:439 439 if (strcmp(e_a->value, e_b->value) <= 0) { ``` ```diff - element_t *e_a = list_first_entry(a, element_t, list); - element_t *e_b = list_first_entry(b, element_t, list); + element_t *e_a = list_entry(a, element_t, list) + element_t *e_b = list_entry(b, element_t, list)->value) if (strcmp(e_a->value, e_b->value) <= 0) ``` #### 為 `qtest.c` 添加指令 > Commit [fd00b86](https://github.com/CodeStone1125/lab0-c/commit/fd00b86e22e98aada39ebf1b6c7e9981f4219ca7) 為了可以在 `qtest.c` 呼叫 `c_sort` 必須為 `qtest.c` 添加指令 `c_sort` 功能並透過選項控制使用的排序演算法。 ```c /* Get sorting method */ const char *sort_method = argv[1]; ... if (strcmp(sort_method, "-l") == 0) { lx_sort(current->q); } else if (strcmp(sort_method, "-s") == 0) { sediment_sort(current->q); } else if (strcmp(sort_method, "-t") == 0) { tree_sort(current->q); } else { report(1, "Invalid sorting method: %s", sort_method); return false; } ``` 以下是呼叫範例： ``` l = [dlagrm kxuimm crecsp zqzde xczea oecvj thhbki gtiji jiuauin tlldmszei] cmd> c_sort -t // -t for treesort l = [crecsp dlagrm gtiji jiuauin kxuimm oecvj thhbki tlldmszei xczea zqzde] ``` 在 `console_init` 中加入後就可以在 `qtest.c` 中呼叫 `lx_sort` 並且呼叫後 `qtest.c` 會啟動 `do_lx_sort` ，這部分我直接複製 `do_sort` 並把 `q_sort` 改成 `lx_sort`。 ```c #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ADD_COMMAND(c_sort, "Various sorting queue methods, -t:tree_sort, -s:sediment_sort " ", -m:lx_sort", ""); ``` - `queue.h` 不能修改? 針對 `queue.h` 不能修改但是 `qtest.c` 需要從 `queue.h` 引入的解決辦法可以在 `qtest.c` 中 `#include "queue.h"` 的後面下一行（或更多行）宣告： ```diff + void lx_sort(struct list_head *head); ``` ---- ### 環狀雙向鏈結串列的排序效能比較 > 將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋 > Commit [c59ebc6](https://github.com/sysprog21/lab0-c/commit/c59ebc61d778a90c81bc88840ce719be92637998) 參考 [2025q1 第 2 週測驗 1](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-1) 穩定排序版的快速排序將程式碼整合進 [lab0](https://hackmd.io/@sysprog/linux2025-lab0) 提及的 `qtest` 將 `listitem` 改成 `element_t` 並稍微改變參數名稱和函式名即可。 > Commit [51db328](https://github.com/sysprog21/lab0-c/commit/51db328184ecb398460a68cdc8815fd5207d51b7) 先實作了一個 `sort_perf.bash` 使用 `perf` 測量不同排序法的不同指標，並且使用 `gnuplot` 畫圖片以下是測量長度十萬到一百萬的排序延遲時間： ![sort_comparison](https://hackmd.io/_uploads/SkO6op4hJl.png) - `Tree sort` 和 `Quick sort` 雖然是 `O(NlogN)` 的演算法但是隨著鏈結串列長度增加延遲大幅上升逼近甚至超過 `Sediment Sort` - **`Tree sort` 推測時間來自 `top-down` 建立二元搜尋數** - **`Quick sort` 推測來自大量的指標和陣列管理** - Linux 核心的 `List sort` 在不論鏈結串列長度幾乎都是最佳選擇 - 排除 `List sort` 的話 `Sediment Sort` 雖在鏈結串列長度短的很慢但表現穩定在很長的鏈結串列長度是比 `Tree sort` 和 `Quick sort` 更快的選擇。 ### 嘗試改進針對鏈結串列排序實作的效能 **施工中** --- ## 在 `qtest` 提供新的命令 `shuffle` > Commit [e09e4cf](https://github.com/CodeStone1125/lab0-c/commit/e09e4cf27ce477e965250d530674da88df3e704c) ### Fisher–Yates shuffle 實作以下是我利用 Fisher–Yates shuffle 演算法實作 `shuffle`: 針對以下 1.~2.要重複運行 `Ｎ - 1` 次，Ｎ取自佇列的尺寸 `q_size` 1. 從前面第 1 ~ `q_size - iteration` 個元素中隨機挑選一個元素 `Ｒ` 2. 將`Ｒ` 插入佇列尾端我透過以上想法實作 `shuffle` 並且在 `qtest.c` 加入`do_shuffle` ### 統計的原理來分析洗牌「亂度」 ``` Expectation: 4166 Observation: {'1234': 4166, '1243': 4180, '1324': 4234, '1342': 4327, '1423': 4251, '1432': 4173, '2134': 4186, '2143': 4113, '2314': 4142, '2341': 4173, '2413': 4209, '2431': 4223, '3124': 4168, '3142': 4183, '3214': 4174, '3241': 4180, '3412': 4061, '3421': 4072, '4123': 4183, '4132': 4053, '4213': 4166, '4231': 4163, '4312': 4107, '4321': 4096} chi square sum: 21.31757081132981 ``` 這是測試 100000次的結果： || 觀察到的頻率 | 期待的頻率 | ${(O_i - E_i)^2 \over E_i}$ | | -------- | -------- | -------- | --- | | [1, 2, 3] | 166391 | 166666 | 0.45375181500726003 | | [2, 1, 3] | 166829 | 166666 | 0.15941463765855063 | | [2, 3, 1] | 166807 | 166666 | 0.11928647714590858 | | [1, 3, 2] | 166790 | 166666 | 0.0922563690254761 | | [3, 1, 2] | 166862 | 166666 | 0.23049692198768795 | | [3, 2, 1] | 166321 | 166666 | 0.7141528566114265 | | Total | | | 1.76935907743631 | 從[卡方分布表](https://en.wikipedia.org/wiki/Chi-squared_distribution)找合適的 P value，我們的自由度為 23，$X^2$ 為 21.31757081132981，因為 21.31757081132981 < 32.007，於是 P value 大於 0.1 。 | df | 0.995 | 0.99 | 0.975 | 0.95 | 0.90 | 0.10 | 0.05 | 0.025 | 0.01 | 0.005 | | --- | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | | 20 | 7.434 | 8.260 | 9.591 | 10.851 | 12.443 | 28.412 | 31.410 | 34.170 | 37.566 | 39.997 | | 21 | 8.034 | 8.897 | 10.283 | 11.591 | 13.240 | 29.615 | 32.671 | 35.479 | 38.932 | 41.401 | | 22 | 8.643 | 9.542 | 10.982 | 12.338 | 14.041 | 30.813 | 33.924 | 36.781 | 40.289 | 42.796 | | 23 | 9.260 | 10.196 | 11.689 | 13.091 | **14.848** | **32.007** | 35.172 | 38.076 | 41.638 | 44.181 | | 24 | 9.886 | 10.856 | 12.401 | 13.848 | 15.659 | 33.196 | 36.415 | 39.364 | 42.980 | 45.559 | | 25 | 10.520 | 11.524 | 13.120 | 14.611 | 16.473 | 34.382 | 37.652 | 40.646 | 44.314 | 46.928 | 因為 P value（>0.1）> alpha（0.05），統計檢定的結果不拒絕虛無假說（$H_0$）也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution。 ![shuffle](https://hackmd.io/_uploads/B1PPcKV2Jg.png)

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.