HackMD
2025q1 Homework1 (lab0)
contributed by < alexc-313 >
開發環境
$ 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
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 7640U w/ Radeon 760M Graphics
CPU family: 25
Model: 116
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU(s) scaling MHz: 32%
CPU max MHz: 4971.0000
CPU min MHz: 400.0000
BogoMIPS: 6986.86
Virtualization features:
Virtualization: AMD-V
Caches (sum of all):
L1d: 192 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 6 MiB (6 instances)
L3: 16 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-11
針對佇列操作的程式碼實作
q_head
Commit 117a180
使用 malloc 分配所需的記憶體，並用 list.h 中的 INIT_LIST_HEAD 函式來初始化佇列的 head。
q_free
Commit aca44ec
在判斷 head 不是空指標後，用 list.h 中的 list_for_each_safe 巨集走訪每個節點，因為此巨集使用 *safe 來預先存放下一個指標，我們便可以使用 free 先釋放 value 使用的記憶體，再用第二個 free 釋放 node 本身所使用的記憶體，在走訪完整個佇列後，再用一次 free 釋放 head。
q_insert head/tail
Commit a38b8fc
因為這兩個函式在概念上非常類似，所以在實作上我將這兩個函式放在同一個commit中。方法都是先判斷head 不是空指標後，用 malloc 逐次分配並確認記憶體成功的被分配，依據 CERN Common vulnerabilities guide for C programmers 的建議，改用 strncpy 函式複製要插入佇列的數值，再分別使用 list.h 中的 list_add 或 list_add_tail 函式將複製完成的變數插入佇列中。
q_remove head/tail
Commit f62cfd5
如同上個 commit，這兩個函式在概念上非常類似，所以在實作上我也將這兩個函式放在同一個commit中。方法都是先判斷 head 不是空指標且非空佇列後，用 list.h 中的 list_first_entry 或 list_last_entry 找出目標節點的 value，再用 strncpy 函式複製到指定的變數，並確保字串的最後是終止字元 \0 ，最後用 list_del_init 來移除節點並確保移除後的節點的指標有被妥善的處理，以避免後續使用上發生未定義的行為。
q_size
Commit 961c87b
在判斷 head 是否空指標與是否是空佇列後，使用 list.h 中的 list_for_each 走訪並記錄節點數量。
q_delete_mid
Commit e1647b8
在判斷 head 是否空指標與是否是空佇列後，使用快慢指標找出佇列的中點，將節點從佇列中釋放，並釋放節點所使用的記憶體。
q_delete_dup
Commit f610366
在判斷 head 是否空指標與是否是空佇列後，使用 list.h 中的 list_for_each_entry_safe 走訪整個佇列，當目前的節點的 value 跟下一個節點的 value 相同時，用變數 found_dup 記錄，並刪除目前節點。當目前節點不等於下個節點時，若 found_dup == true ，代表目前節點與上個已刪除的節點相同，故刪除該節點。
q_delete_node
Commit 112896d
在觀察到許多函式皆有使用以下程式碼後
element_t *node = list_entry(n_ptr, element_t, list);
list_del(n_ptr);
free(node->value);
free(node);
我增加了 q_delete_node 來取代這些重複的程式碼。這個函式多了
if (node->value)
free(node->value);
避免盲目的釋放記憶體。
q_swap
Commit 6608629
使用 list.h 中的 list_move 函式讓 cur 跟 cur->next 互換，此時 cur 在原本 cur->next 的位置，再將 cur 設為 cur->next 就可完成兩兩互換。
q_reverse
Commit bc01842
在判斷 head 是否空指標與是否是空佇列後，使用 list.h 中的 list_for_each_safe 走訪整個佇列把每一個節點逐一用 list_move 移動到佇列的 head->next 位置。
q_reverseK
Commit eb73a28
使用兩個 for 迴圈，用 *start 來記錄第一個將被倒置的節點，內部迴圈用來倒置 *start 後的 K 個節點，外部迴圈用更新 *start。
merge_two
Commit 2424ca7
這是一個 q_sort 的輔助程式，此函式接收兩個 *list_head 參數，並使用迭代的方式將兩個佇列以遞增或遞減的方式合併，實作上我使用 list_del 將兩個節點從各自的佇列中移除，在比較其 value 後用 list_add_tail 把較小或較大的節點加到新的佇列 merge ，當其中一個佇列為空時，若其中一個佇列有尚未加入 merge 的節點，利用 list_splice 把剩餘的節點加在 merge 尾端，並在將第一個或第二個 *list_head 指向合併完成的佇列後回傳。
Commit 8873e16
為了讓 merge_two 能被 q_merge 使用，我們必須做一些修改，因為我在 q_merge 中的寫法需要確保 merge_two 回傳並將第一個 *list_head 指向合併完的佇列。
if (!list_empty(head_1)) {
list_splice_init(&head, head_1);
} else {
list_splice_init(&head, head_2);
list_splice_init(head_2, head_1);
}
所以在第二個佇列剰於的情況下，會多使用一個 list_splice_init 把第二個佇列接到第一個佇列上。
q_sort
Commit 2424ca7
這個函式用遞迴實做 merge sort 演算法。
在用快慢指標找到佇列的中點後使用 list_cut_position 函式將佇列剖半，再呼叫自己並傳入剖半完的佇列，最後呼叫 merge_two 函式將所有佇列組合起來。
q_ascend/descend
Commit 8827730
參考 list.h 中的 list_for_each_safe 寫出
for (node = (head)->prev, safe = node->prev;
node != (head);
node = safe, safe = node->prev)
來安全的反著走訪所有的節點，用 biggest 變數存放最大的字串，再用 q_delete_node 刪除 value 比 biggest 大或小的節點。
q_merge
Commit 94075cc
用 for 迴圈走訪除了第一個以外每個 queue_contex_t ，呼叫 merge_two 函式將佇列一個個合併到第一個佇列裡。
結果
- 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
由於我尚未完成
lab0-c 的 Welch's test 測試項目，所以除了 trace-17 的部份沒有通過以外，其他部份皆順利通過。亂數
shuffle
Commit a87564f
在 q_test.c 中加入 do_shuffle 函式，再用 ADD_COMMAND 就可以使用新的命令 shuffle。
其中 do_shuffle 的實做方法如下：
先用 q_size 取得佇列長度 len ，用 rand 抽出一個在區間 len-1 跟隨機數做指標交換，再將 len - 1。
統計方法驗證 shuffle
測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次結果：
Expectation: 41666
Observation: {'1234': 41517, '1243': 41531, '1324': 41621, '1342': 41430, '1423': 42093, '1432': 41945, '2134': 41828, '2143': 41186, '2314': 41658, '2341': 41775, '2413': 41515, '2431': 41375, '3124': 41727, '3142': 41975, '3214': 41575, '3241': 41663, '3412': 41318, '3421': 41791, '4123': 41669, '4132': 41943, '4213': 41993, '4231': 41601, '4312': 41728, '4321': 41543}
chi square sum: 28.45183122929967
直方圖：
有 24 個樣本，自由度為 23 ，直方圖呈現 uniform distribution ， chi square sum 為 28.45 。查卡方分佈表可知 p-value 介於 0.1~0.9 ，因為 P value（0.1~0.9）> alpha（0.05），所以統計檢定的結果不拒絕虛無假說。統計檢定的結果不拒絕虛無假說
啟發和疑惑
由於 Fisher–Yates shuffle 是適用於陣列的演算法，在佇列上使用因為取用每個節點的時間並非
