HackMD
2025q1 Homework1 (lab0)
contributed by < Mike1117 >
開發環境
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 8845HS w/ Radeon 780M Graphics
CPU family: 25
Model: 117
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 2
Frequency boost: enabled
CPU(s) scaling MHz: 29%
CPU max MHz: ha5137.0000
CPU min MHz: 400.0000
BogoMIPS: 7585.59
進度記錄
以下複製自「作業要求」
- 在 GitHub 上 fork
lab0-c - 依據上述指示著手修改
queue.[ch]和連帶的檔案，測試後用 Git 管理各項修改，要能滿足make test自動評分系統的所有項目。- ⚠️ 在提交程式變更前，務必詳閱 如何寫好 Git Commit Message
- 詳閱 你所不知道的 C 語言: linked list 和非連續記憶體 並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- 參閱 2023 年 Linux 核心設計課程第一次作業檢討，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越四千萬行的 Linux 核心
- 研讀 Linux 核心原始程式碼 並嘗試引入到
lab0-c專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能- 詳閱 改進
lib/list_sort.c（含解說錄影）
- 詳閱 改進
- 在
qtest提供新的命令shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」 - 在
qtest中執行option entropy 1並搭配ih RAND 10一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在qtest切換不同的 PRNG 的實作（可選定 Xorshift），搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質 - 研讀論文 Dude, is my code constant time?，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。
- 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
- 除了修改程式，也要建立 HackMD 筆記，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- 詳閱第 1 週所有教材及作業描述 (一), (二), (三), (四), (五)，記錄你的啟發和疑惑
- 開啟 Address Sanitizer，修正
qtest執行過程中的錯誤 - 運用 Valgrind 排除
qtest實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗 - 解釋 select 系統呼叫 在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
- 填寫 Google 表單 提交程式碼和開發紀錄，當系統檢查完畢時，預期將在 作業區 見到登記的 HackMD 與 GitHub 超連結
- 截止日期：Mar 11, 2025 (含) 之前
- 越早在 GitHub 上有動態並及早接受 code review 且持續改進者，評分越高
檢查事項
N03 作業要求
- 檢查事項 1: 確認分析 Linux 核心的 lib/list_sort.c 實作並評估其效益、針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式，該設計對應的排序測試實驗方案
- 檢查事項 2: 閱讀指定的論文〈Dude, is my code constant time?〉及列於 lib/list_sort.c 修改紀錄 (即 commit b5c56e)中的 3 篇論文，闡述你的洞見，需要指出論文和現有 Linux 核心原始程式碼不同的地方，並予以討論，過程中該有對應的效能分析實驗。參考 CPython 的 listsort 的說明文件，對不同的資料分佈進行測試
- 檢查事項 3：請先詳讀〈Git 教學與 GitHub 設定指引〉（包含解說錄影），接著使用 git fetch 命令以取得 sysprog21/lab0-c 的最新更新，並利用 git rebase 將你已提交的 commit 移至 3 月 18 日或之後的更新之上。注意：在操作過程中可能會出現衝突，需自行解決。此外，請確保所有 commit 訊息皆符合〈How to Write a Git Commit Message〉的規範，必要時可使用 git rebase -i 命令進行修改，最終再以 git push –force（請務必謹慎操作）將更新公開推送至 GitHub。確保你在 rebase 時，基底包含 commit 4a2ff9f
- 檢查事項 4: 確保符合指定的書寫規範，技術用語依循〈資訊科技詞彙翻譯〉，並針對授課教師的要求，以清晰、明確，和流暢的漢語書寫。倘若你選擇用英語書寫開發紀錄，則依正式英語技術報告慣例。
- 檢查事項 5: 針對現有 (及自己的) 程式碼，提出可重用程度更高、效能更好，且更安全的實作，過程中應有對應的實驗及分析。過程中，應查閱 C 語言規格書 (原文) 及 The Linux Programming Interface
- 檢查事項 6: 研讀 select(2) 並探討 sysprog21/lab0-c 如何偵測程式執行的超時、現有的網頁伺服器如何與 linenoise 並存，以及相關的 signal(7) 使用方式。
- 檢查事項 7: 使用 valgrind, massif, gdb, perf 等課程提及的開發量化程式碼執行時期的資訊，應分析記憶體開銷、執行的指令 (instruction) 數量、cache 表現，和程式熱點 (hotspot)，並予以改進，過程中應有充分的實驗紀錄及討論。
- 檢查事項 8: 紀錄研讀第 1 到第 4 週課程教材的發現和疑惑，描述於上述開發紀錄，之後授課教師和其他學員會參與討論。
- 檢查事項 9: 改寫 lab0-c 既有的 shannon_entropy.c 和 log2_lshift16.h，採用更有效、
- 檢查事項 10: 針對 sysprog21/lab0-c 專案，提交 pull request 以修正你在作業過程中發現的缺失和提出改進，並於 GitHub 進行 code review
- 檢查事項 11: 詳閱〈Teach Yourself Programming in Ten Years〉，闡述你的認知和發現，並描述你在本課程發現可對應到該文章的觀點。
實作 queue.[ch]
q_new()
使用 malloc() 為 list 的 Dummy head 配置記憶體空間，若成功則呼叫 INIT_LIST_HEAD 初始化並回傳，失敗則回傳 NULL 。
q_free()
使用 list_for_each_entry_safe 逐一走訪每個節點，再呼叫 q_release_element 釋放每一節點的記憶體空間，最後釋放 head 之記憶體空間。
q_insert_head() & q_insert_tail()
此二函式為插入一個新的節點至 list 的頭部或尾端。
首先需要為新節點配置記憶體空間，再用 strdup() 將節點的值設為傳入之字串 s 。
再呼叫 API 將這個節點插入頭部或尾端。
q_remove_head() & q_remove_tail()
queue.h 中的描述提到 "remove" is different from "delete" 。
故此處僅需將節點從頭部或尾部 unlink ，同時回傳節點的值即可。
首先透過 API 獲得首個或尾端節點的指標，再利用 list_del 將其 unlink ，再將節點的值 copy 至傳入之字串 sp 。
需要注意的是，此處傳入之字串 s 有規定大小 bufsize ，故 copy 後需要根據 bufsize 截斷字串，使其符合大小。
q_size()
呼叫 list_for_each 來逐一走訪每個節點，並以一 Counter 計算迴圈的次數，最後回傳該 Counter 的值就是此 queue 的 size 。
q_delete_mid()
在第一次實作時，我選擇先以 q_size 獲取 queue 的長度，再除以 2 以獲得中間節點的 index ，最後 unlink 及 free 該節點。
在第一次實作中我發現我的 +1 放錯位置，故修改。
在閱讀了 案例探討: Leetcode 2095. Delete the Middle Node of a Linked List 後，我將原本的實作改為透過快慢指標來獲取 mid 節點的指標。
兩種實作方法獲得 mid 節點的時間複雜度其實相同，但第一次實作中實際上多了 O(n) 的複雜度來獲取 queue 的長度，故此處還是選擇更有效率的實作方法。
q_delete_dup()
此 Function 的作用為移除 連續 的重複節點，而非整個 queue 中的重複節點。
故此處我以 list_for_each_entry_safe 來走訪節點，同時以一 Boolean 變數來記錄目前是否有 dup 的情況。
若 curr 與 safe 的 value 相同，則刪除 curr 這個節點，並將 dup 設為 true。
若 curr 與 safe 的 value 不相同，且 dup 為 true ，則同樣刪除 curr 這個節點，再將 dup 設為 false。
q_swap()
此Function為交換queue中的每兩個節點。
故我以 list_for_each_entry_safe 來走訪節點，swap curr 與 safe的value後將curr指向safe，如此即可跳過safe，繼續交換下兩個節點。
q_reverse()
以一 tmp 節點記錄原節點的 next ，再逐一反轉每一節點的 prev 及 next 。
q_reverseK()
該函式其實與 q_swap 類似， q_swap 為每兩個節點 swap 一次，而該函式則為每 k 個節點進行一次 reverse， q_swap 本質上為 k = 2 時的特例。
而我的想法是在該函式內複用 q_reverse 函式，每次依序取 k 個節點作為子串列，並給他們一個臨時的 Dummy Head ，再呼叫 q_reverse 對該子串列進行 reverse 的操作即可。
假設我們目前的 queue 有 7 個節點，k = 3 。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
在第一輪的外層迴圈中，臨時 dummy head tmp_h 會指向 head ，當前子串列的第一個節點 curr_head 則會指向 tmp_h->next。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
而內層迴圈會以一 Counter i 記錄目前走訪的節點數，當 i==k 時，表示當前蒐集的節點數已滿足 k ，需要呼叫 q_reverse 作 reverse 的操作。
但 q_reverse 需要串列是雙向鏈結串列，所以在呼叫前我們需要先做一些操作，使子串列符合雙向鏈結串列的性質。
這邊由於 k == 3 ，故我們的子串列會是 Node 1 ~ Node 3 ，我們需要將尾端節點的 next 指標指向 tmp_h ， tmp_h 的 prev 指向尾端節點。同時將 tmp_h 的 prev 作記錄，以便 reverse 完後接回原串列。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
此時呼叫 q_reverse(tmp_h) ， 傳入值為 tmp_h ，即可完成對子串列的 reverse 。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
最後將原先子串列的第一個節點(目前子串列的尾節點) curr_h 的 next 指向 safe ， safe 的 prev 指向 curr_h ， 臨時 dummy tmp_h 的 prev 指向原 prev o_prev ，最後需要將 tmp_h 設為 curr_h 當做下一輪子串列的 dummy ，這樣即可在保持原鏈結串列完整的情況下對 k 個節點完成 reverse 。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
後續幾輪也是相同作法，直至 safe == head 時便會跳出迴圈 ， 剩餘節點若數量不足 k ，則維持原樣。
q_sort()
q_ascend() & q_descend()
參考 LeetCode 中的 hint ：Iterate on nodes in reversed order. 。
在要求節點排列為 descend 時 ，應該從尾往頭進行 traverse ， 移除比當前最大值小的節點。
在要求節點排列為 ascend 時 ，應該從頭往尾進行 traverse ， 移除比當前最小值大的節點。
在此處僅概述於 q_descend 中的實作 ， q_ascend 因高度相似故不多作贅述。
這裡舉 LeetCode 中的 Example 1 為例，鏈結串列會如下所示：
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
而根據 hint ，我們需要從尾部開始 traverse ， 所以宣告一指標 curr = head->prev ，而此時前一個節點就是 curr->prev 。
只需比較 curr 及 curr->prev 的節點值大小，若 curr 值較大(此時的情況)，則呼叫 list_del unlink 該curr->prev，再透過 q_release_element 釋放其記憶體空間。
移除 curr->prev 點後，串列會變成下面這樣：
同樣只需比較 curr 及 curr->prev 的節點值大小，
但此時就會出現一個小問題，可以看到在 LeetCode 中，該題目之 ListNode 結構儲存 value 的方法為 int val ，故 value 是整數，可以簡單地用運算子(> < ==)來比較。但在 lab0 中，value 是 char *value ，為一字串，故需要用 strcmp 來比較字串的大小。
而在 strcmp 中，是依照字典序來比較字串之大小， 8 會比 13 大，在此處直接舉 LeetCode 中的例子效果不彰，所以我們可以做一點簡單的調整，將 13 替換為 9：
那此時 8 < 9 ，我們要做的僅是移動 curr 指標，使其指向值為 9 的這個節點，繼續下一輪操作。
而當 curr->prev == head 時，便會停止操作，此時串列如下所示：
這樣便完成了使鏈結串列變為 descend 形式的操作。
q_merge()
要撰寫 q_merge 這個函式，首先要做的就是理解 queue_contex_t 這個結構是如何存放多條 queue 的。可以看到結構的定義如下：
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
閱讀 queue.h 中的注釋，我們可以知道 q 存放的是指向每一條 queue 的 head 之指標， chain 則是用來鏈接每一條 queue 的 head 。
size 則是當前節點指向之 queue 的大小，而 id 為每一條 queue 的 identification number 。
閱讀完上述結構之定義，我們可以知道 queue_contex_t 的結構會如下所示，因 size 及 id 在我的實作中並未使用，此處省略繪製：
而在 q_merge 中，傳入參數是這個存放 queue 的鏈結串列的 head 以及布林函數 descend 。
我們需要做的就是將不同條的 queue 依 descend 或 ascend 合併為一條，並放入鏈結串列的第一個節點中，同時其他節點的 q 需要被設定為 NULL：
觀察這個函式的實作要求，我們可以先簡單拆分成兩個子問題：
如何挑選將要被合併的兩條 queue ？
如何撰寫合併函式，使其可以以 ascend / descend 的形式合併兩條 queue ？
針對第一個問題，在 你所不知道的 C 語言: linked list 和非連續記憶體 - 案例探討: LeetCode 21. Merge Two Sorted Lists 中，老師已有做過詳細的探討，我在這邊選擇的方法是將鏈結串列中的 queue 頭跟尾兩兩合併，這樣在多數的情況下兩條串列的長度比較平均，合併會比較快。
（思考：若透過存取 queue_contex_t 中的 size ，以 queue 的 size 大小作為挑選基準進行合併，是否會比較快？ TBD ）
基於此方法，我在 q_merge 中宣告了三個指標， ptr_first 、 ptr_i 以及 ptr_j 。其中 ptr_first 指向鏈結串列中的第一個 queue ，也就是最後合併完成的 queue 需要存放的位置，而 ptr_i 以及 ptr_j 分別用來指向鏈結串列的頭及尾，用以挑選待合併的 queue 。
在函式的內層迴圈中，會呼叫 merge_two_sorted_queue 來合併 ptr_i 及 ptr_j ,並將合併完成的 queue 放入 ptr_i ，之後將 ptr_i 向後移一個節點，而 ptr_j 向前移一個節點，繼續合併，直至兩指標相遇後退出內層迴圈。
而外層迴圈則是將 ptr_i 重新設定為 ptr_first 的下一個節點， ptr_j 重新設定為尾端節點，再繼續執行合併，直至 ptr_i 及 ptr_j 都指向串列的第二個節點，即代表此時只剩下最後兩條 queue ，退出外層迴圈後完成最後兩條 queue 的合併即可。
以下是具體例子，這是一個有四條 queue 的鏈結串列：
此時合併 ptr_i 及 ptr_j ， ptr_j 所指向的串列會變成 NULL 。
移動 ptr_i 及 ptr_j ，兩指標相遇：
將 ptr_j 設為ptr_i ，此時的 ptr_j 會指向串列中最後一個不為 NULL 的 queue；將 ptr_i 重新設定為 head->next->next ，即指向串列中第二條 queue 之 head 。
同樣合併 ptr_i 及 ptr_j ：
移動 ptr_i 及 ptr_j ，兩指標相遇，重設ptr_j 為ptr_i ， ptr_i 為 head->next->next ，此時會發現兩指標仍相遇，代表目前的鏈結串列中只剩下最後兩條 queue ：
退出迴圈，此時作最後的合併，合併 ptr_first 及 ptr_i ：
至此即完成合併鏈結串列中的所有 queue 為一條，並存放在第一條 queue 中。
此處合併最後兩條 queue 時，才會根據傳入參數 desend 來決定合併的方式，為何如此實作在第二個子問題會再提到。
針對第二個子問題，同樣參考 你所不知道的 C 語言: linked list 和非連續記憶體 - 案例探討: LeetCode 21. Merge Two Sorted Lists ，使用 indirect pointer 的技巧來解決。
這邊用一個實際的例子來作解釋，現有兩條 sorted 的 queue ，宣告兩個指標 L1 及 L2 來指向他們各自的 head。因為函式的目的是 合併兩個 queue 並存入第一個 queue ，故我此處將 L1 的 head 作為最後要回傳的 head ，宣告間接指標 ptr 指向 L1 的 head 以及另一個間接指標 node 。
首先將 L1 及 L2 都指向他們的 next ，即 queue 中第一個節點，此處會進入迴圈，用以比較 L1 及 L2 所指向之節點的大小，將節點陸續放入合併後的串列中，直至有一條原始串列為空。
此處我們用 strcmp 比較節點值的大小， node 會指向值較小的指標，而 ptr 則會指向
head->next 。
由於此處 L1 所指向之節點值較小，需要先將他放到合併後的陣列中，透過 *ptr = *node ，即可將 head->next 指向目前被 node 指向之指標 L1 所指向的節點(紅色表示新連結的 chain)。此處再透過 *node = (*node)->next 將 L1 指向原節點的下一個節點，prev 指向原節點， ptr 則指向 prev 的 next 。
node 則會在第二輪迴圈中因 2 < 3 ，被設定為指向 L2 。
此處重複前述操作，將目前合併串列尾端接上 node 所間接指向的節點。
此處為了方便區分原本的 L1 及 L2，將前一張圖中的灰色箭頭隱藏（實際執行過程中是仍然連結的）。此處接上 node 所間接指向的節點後，再繼續前述過之指標調整。
經過幾輪類似的操作後，可以看到 L1 的節點已被全數合併入新的串列，僅剩 L2 仍有剩餘節點。由於兩個被合併的串列本身就是 sorted 的，我們只需將剩下那條串列直接接入新串列的尾部即可完成合併，可以看到原先 L1 的 head 所連結的串列是 sorted 的。
但此時還不能直接回傳原 L1 之 head ，首先需要 traverse 剩下那條串列的節點至尾部，將其與原 L1 之 head 相連，才算是一條完整的雙向鏈結串列。
而更需要注意的時，原 L2 之 head 仍然指向原先的 next 與 prev ，但此時實際上他應該為指向自己的 Singular head ，故需要呼叫 INIT_LIST_HEAD 來使其指向自己。
至此便完成了兩條 sorted 雙向鏈結串列的 ascend 合併。
至於如何合併為 descend 的串列，實作方法其實跟 ascend 大同小異，但經過仔細思考跟實作後發現有一些潛在的問題：
一開始的想法是統一從串列尾端往頭部開始合併，但實作後發現合併完的串列時常與預期不符，後來才想到若有多條串列需要合併，合併後的串列就已經是 descend 的了，若此時再從尾端開始合併，就不符合所有串列都是 ascend 的假設了。
但若加上當前串列是 ascend 還是 descend 的判斷，整體的實作會變得非常複雜，也會增加非常多不必要的計算，所以我最後採用的做法是先將所有串列都以 ascend 的形式合併，最後在合併 ptr_first 及 ptr_i 時，再採用從串列尾端往頭部合併的方法合併為 descend 的形式。
以下是截取的部分實作程式碼，可以看到在迴圈中合併串列時，都採 ascend 的形式，直至最後合併 ptr_first 及 ptr_i 時，再傳入 q_merge 的 parameter descend 。
這樣實作上既降低了複雜度，也減少了不必要的計算開銷。
while (ptr_i != ptr_j) {
while (ptr_i != ptr_j && ptr_j->next != ptr_i) {
list_entry(ptr_i, queue_contex_t, chain)->q =
merge_two_sorted_queue(
list_entry(ptr_i, queue_contex_t, chain)->q,
list_entry(ptr_j, queue_contex_t, chain)->q, 0);
ptr_i = ptr_i->next;
ptr_j = ptr_j->prev;
}
ptr_i = head->next->next;
}
list_entry(ptr_first, queue_contex_t, chain)->q = merge_two_sorted_queue(
list_entry(ptr_first, queue_contex_t, chain)->q,
list_entry(ptr_i, queue_contex_t, chain)->q, descend);
比較自己實作的 merge sort 和 Linux 核心程式碼之間的效能落差
Temp
研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能
詳閱改進 lib/list_sort.c含解說錄影
確認分析 Linux 核心的 lib/list_sort.c 實作並評估其效益、針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式，該設計對應的排序測試實驗方案。
分析 Linux 核心的 lib/list_sort.c 實作並評估其效益
觀察 list_sort.c ，其與我實作的 merge sort 差異主要有以下幾點：
· 在一開始時會斷開尾部與頭部的鏈接，使其變為單向的鏈結串列，並且在合併的過程中都只維持單向的鏈接，直至最後一次 merge 才會將各節點之 prev 連上。而我的實作全程都維持雙向的鏈接。
· 不同於傳統的透過遞迴分割子串列再合併的方法，而是透過一種 bottom-up 的方法，將所有節點都視為單個的節點，再依節點數作合併。而我則是採用傳統的遞迴方法實作。
開發 Timsort 排序程式
在 qtest 提供新的命令 shuffle
實作 Fisher–Yates shuffle 演算法
以統計的原理來分析實作
設計一組新的命令或選項，在 qtest 切換不同的 PRNG 的實作
在設計新的命令前，需要先了解原來的實作做了什麼。
在 qtest 中輸入 option entropy 1 以及 ih RAND 10 後，可以看到如下輸出：
cmd> option entropy 1
cmd> ih RAND 10
l = [odghcw(29.69%) cmtyo(26.56%) oqakef(29.69%) lzqxsrxr(29.69%) katvnsnl(32.81%) zwfpg(26.56%) rcgfkfps(32.81%) hyugosvr(35.94%) fyuztwwal(35.94%) hyatn(26.56%)]
option entropy 1 為將顯示 shannon entropy 開啟，
ih RAND 10 為在 queue 中插入十個長度及內容隨機的字串，字串後的括號內就是計算出的 shannon entropy 。
根據 entropy 的公式：
我們可以知道，越隨機，也就是出現機率越平均的信息源熵就越大，而看到我們 ih RAND 時所使用的chaset為：
static const char charset[] = "abcdefghijklmnopqrstuvwxyz";
也就是小寫的英文字母，共26個，所以此時我們的最大熵為
log26 = 4.7
我們所期望的便是隨機生成字串時，他的熵可以貼近這個最大值，當越貼近最大值時，代表我們的字串越隨機、品質越好。
那為什麼這裡的熵值是一個 % 數而不是一個具體的值呢，我們需要看到具體的計算函式，位於 shannon_entropy.c 中。
可以看到在
const uint64_t entropy_max = 8 * LOG2_RET_SHIFT;
這一行中，定義了 entropy_max 為 8
而最後
return entropy_sum * 100.0 / entropy_max;
表示最終值是以 entropy_max 為基準的一個比例值。
由此我們可以知道，在完全隨機的情況下，最大可以達到的%數便是log26/8，也就是58.76%左右，而原實作方法的熵以肉眼觀察，平均大概落在30%左右，明顯低於剛剛計算出的 58.76%。
那麼為什麼會這樣呢？可以看到
#define MIN_RANDSTR_LEN 5
#define MAX_RANDSTR_LEN 10
將隨機生成的字串之長度限制在 5 ~ 10 之間，而在熵值的計算中，最大值是跟樣本的數量相關的，而在字串長度為 5 時，樣本的數量最多只能為 5 個，那麼此時的熵最大只能為
log5 = 2.32
大概為 29 % 左右
所以我們需要將生成字串的長度增加，至少需要 >= 26 ，才有機會使熵接近 58.76% 。
#define MIN_RANDSTR_LEN 50
#define MAX_RANDSTR_LEN 100
將字串長度設定為 50 ~ 100 ，再重複之前操作
cmd> ih RAND 10
l = [hahxsxqaviyyrsbitipdvklsmypxjagtuxaiwqavrqbhjqvrpnivfdpjimytnjkdtljcjvhdyqnnqiscugposndgzzwbenayghk(54.69%) rjswadgiltuaixwixuboiriuytivulzowwjirmwbacpoqjmfrsvssfazxvhvlthoicqzmbskct(53.12%) zrycnlydohlnqmrhorsuhbzddqgariykehygufwlnzmblupiekvyngkliozdzscxtafjfnxxfxkvsh(54.69%) axtqqqpbqybevjzreeqldmdkdjcojkksiwuoitrjjfbufwqnwmmylmddszftvjbmbdacqodxigtfnl(54.69%) qnqqljjrnadcajmrryswfqzzrifewjxoyldlxsxlrxsxznyyhi(50.00%) hlocfgmuizhqqyjyvqcljgujegbrbawxglisekzmtcvnavcvyoepeequdqjbqesulptsyolhtivsvjasgbap(54.69%) jbvucvrsakbggwwxocibloydfwylccniponmjxiwxaommawbvxpkruqnjihjpwzqfkijtcoyisrgvoce(54.69%) hbcekyszmjauvkfkjolhxwkthjjamovccerxoxvexfzjwxlciqaytaglhvvgklscfrwsgawxymvhxvrjhgbeijstzd(53.12%) yblpwedtmnivlpdmrlzehanqrkglucskxtijxteltbinureilckqchgsxhqzkngogppwrruugdzmcwjcrjuhofbpeg(54.69%) mzrlqpbwzcqzboirbjdvdpvrbwbgoypzeldfzwgfwwcbzywfaqpgkfxjsgqtbbskbbhmmrbvsk(51.56%)]
此時可以看到計算出的平均熵值已經很接近 58.76% 。
研讀論文 Dude, is my code constant time?
一開始看到作業要求中的 注意：現有實作存在若干致命缺陷，請討論並提出解決方案 時，我並沒有將他與自動評分系統關聯起來，所以在 實作 queue.[ch] 這一部分卡了很久，因為我無論如何都過不了 trace-17-complexity 。
於是我便去翻閱其他 checks 已經為 √ 的同學 lab0 的 Actions 部分，後來看到 salmoniscute 這位同學的 Actions 中，經過 Add percentile processing in dudect fixture 這一 Commit 後，就成功通過評分系統，我才知道原來要先改進 dudect 的實作，才能通過最後一個 trace 。
要想改進 dudect 的實作，首先要閱讀論文及其 Source code。
