HackMD
2025q1 Homework1 (lab0)
contributed by < yuto0226 >
開發環境
$ 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: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 10
Socket(s): 1
Stepping: 3
BogoMIPS: 5376.02
修改 queue.[ch]
list.h 筆記
LIST_HEAD(head)：直接初始化節點，下一行可以直接使用head節點list_add：將node插入head節點之後list_add_tail：將node插入head節點之前list_cut_position(head_to, head_from, node)：從第一個節點到node移到head_to串列
Image Not Showing Possible Reasons- 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
list_move(node, head)：將同一個串列上的node插入至head之後list_move_tail(node, head)：將同一個串列上的node插入至head之前
實作注意事項
- 檢查傳入函式指標是否為
NULL，或是環狀佇列是否包含節點!head || list_empty(head)
q_new
使用 malloc 配置記憶體後，應檢查是否配置成功，接著才初始化節點。
Commit 8720df4
q_free
要釋出的節點有兩種：struct list_head、element_t，可以個別使用 free、q_release_element 釋放記憶體空間。
提交時觸發了 cppcheck 的 unusedLabel 錯誤：
Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:32:5: style: Label 'int' is not used. [unusedLabel]
list_for_each_entry_safe (entry, safe, head, list) {
^
Fail to pass static analysis.
原因還無法釐清，發現有可能是 Commit 1d68fae 造成的問題，用 git checkout 回到 Commit 9cf7f12 便可以通過 scripts/pre-commit.hook。
在 issue #211 中，有同學回覆表示有相同問題，原因是 cppcheck 舊版本的程式錯誤，自己編譯 cppcheck 就可以解決這個問題了。
Commit 1ef5317
q_insert_head、 q_insert_tail
這兩個函式要做的事情幾乎一樣，配置節點的記憶體空間，接著插入佇列中，唯一的差別在於插入的位置。
一開始的想法是使用 list_add、list_add_tail 去對應不同位置的情況，再參考 2023 年 Eroiko 的開發紀錄 中提到的巨集的方式定義這兩個函式。
後來重新研讀 list.h ，發現 list_add 函式可以延伸為新增節點到 head 之後，也就是說 list_add_tail 甚至可以替換成 list_add(head->prev)。參考 2023 年 yanjiew 的開發紀錄，q_[insert,remove]_tail 可以重用 q_[insert,remove] 的程式碼。
Commit 692d17e
在使用 strdup 配置字串的記憶體空間時，若配置失敗就要回傳 false，同時也需要釋放先前配置給節點的記憶體空間。在測試後發現並修正。
Commit 03e118e
q_remove_head、q_remove_tail
這兩個函式會從佇列中移除頭或尾的節點，因此除了要檢查 head 外，也要檢查是否至少包含一個節點。複製字串時，除了考量 sp 是否為 NULL，檢查節點的 value 使否有配置記憶體，可以省去 strncpy 的執行。
而 q_remove_head 不同於 q_insert_head，不是操作 head，而是操作 head->next，所以在 q_remove_tail 傳入參數時要改成 head->prev->prev。
Commit f303894
q_size
考慮使否要使用 list_empty() 作為一開始檢查的條件。閱讀 list.h 可以看到 list_empty() 會回傳 (head->next == head)。而若放棄檢查，list_for_each() 巨集中的 for 迴圈一樣會檢查，只是換個結構而已。使用 list_for_each() 巨集則可以節省函式呼叫的棧空間，故不須搭配 list_empty() 檢查。
Commit 0b7f422
q_delete_mid
閱讀第二周的教材 分析「快慢指標」，文中描述：相較於「單一指標」，「快慢指標」方式具有更好的時間局部性。
Commit f52ba78
q_delete_dup
q_delete_dup 會刪除已經排序佇列中具備重複內容的節點。初步的想法是使用兩個指標 curr、next 走訪佇列，判斷 next、prev 指向的節點的內容是否相同，若相同則刪除 curr 節點。
但上述的流程會漏掉一個節點沒有刪除，因此可以使用一個變數判斷目前節點的內容是否重複，並刪除該值的最後一個節點。
diff --git a/queue.c b/queue.c
index 6ccbaad..04128f6 100644
--- a/queue.c
+++ b/queue.c
@@ -135,12 +135,16 @@ bool q_delete_dup(struct list_head *head)
if (!head || list_empty(head))
return false;
+ bool isdup = false;
element_t *curr = NULL, *next = NULL;
list_for_each_entry_safe (curr, next, head, list) {
if (&next->list != head && !strcmp(curr->value, next->value)) {
list_del(&curr->list);
q_release_element(curr);
+ } else if (isdup) {
+ q_release_element(curr);
+ isdup = false;
}
}
Commit 1add3c8
注意到上述更動包含不完整的實作，在測試的過程中遺漏了，更正如下：
diff --git a/queue.c b/queue.c
index f059b92..9174568 100644
--- a/queue.c
+++ b/queue.c
@@ -142,7 +142,9 @@ bool q_delete_dup(struct list_head *head)
if (&next->list != head && !strcmp(curr->value, next->value)) {
list_del(&curr->list);
q_release_element(curr);
+ isdup = true;
} else if (isdup) {
+ list_del(&curr->list);
q_release_element(curr);
isdup = false;
}
Note
提交程式碼應小心謹慎、步步為營
Commit 628403f
q_swap
參考 2025-02-25 第一次問答簡記，q_swap 是 q_reverseK 的特例(
Commit cbeec82
q_reverse
走訪整個佇列，使用 list_move 將所有節點移動到頭節點後。
- 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
Commit c5bd310
q_reverseK
Commit cbeec82
inorder
在後續的排序或是合併的實作中，都會透過 descend 來控制升序或降序排列。因此包裝一個 strcmp 函式的實作是必須的。參考 2024 年 Eriko 的實作，發現會導致 merge sort 無法穩定排序。
Commit ebd7667
q_merge_two
後續實作合併排序與 merge 函式，皆會需要合併兩個佇列。q_merge_two 會依照升序或降序合併 sub 到 main 上。
Commit 67286be
q_sort
搭配 q_merge_two 實作合併排序。
Commit d5a2440
q_ascend、q_descend
q_ascend 是刪除所有節點 curr 右邊節點 next 的內容比 curr 小的函式，維持佇列節點內容遞增。q_descend 則相反。
初步想法是倒著走訪佇列，記住最小內容的節點 min，若有節點的內容大於 min 就刪除該節點。
Commit 22944d3
q_merge
在 qtest.c 中，多個佇列會透過 queue_context_t 串在一起，這個實作採用最簡單的方式從第一個柱列合併到最後一個佇列。
Commit 0e39489
Valgrind + 自動測試程式
TODO
整合網頁伺服器
TODO
亂數 + 論文閱讀
實作 shuffle 指令
新增 shuffle 指令參考作業說明和 do_sort 的實作。要添加 do_shuffle 函式並在 console_init 中使用 ADD_COMMAND 巨集新增指令。
@@ -1096,6 +1126,7 @@ static void console_init()
"");
ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time",
"[K]");
+ ADD_COMMAND(shuffle, "Shuffle the queue", "");
add_param("length", &string_length, "Maximum length of displayed string",
NULL);
add_param("malloc", &fail_probability, "Malloc failure probability percent",
Commit 6e795d6
q_shuffle 函式先採用 Pencil-and-paper method 實作。透過 rand() 選擇節點，並使用 list_move_tail 移到暫存佇列，最後剩下一個節點時再使用 list_splice 合併。
Commit daa29bd
經過腳本測試後，發現實作有問題。執行腳本結果：
Expectation: 41666
Observation: {'1234': 167322, '1243': 0, '1324': 165895, '1342': 0, '1423': 0, '1432': 0, '2134': 166635, '2143': 0, '2314': 166719, '2341': 0, '2413': 0, '2431': 0, '3124': 166820, '3142': 0, '3214': 166609, '3241': 0, '3412': 0, '3421': 0, '4123': 0, '4132': 0, '4213': 0, '4231': 0, '4312': 0, '4321': 0}
chi square sum: 3000073.3336533387
上述的實驗結果嚴重分布不均，重新依照作業說明的流程實作。
diff --git a/qtest.c b/qtest.c
index 63b236e..794fbc8 100644
--- a/qtest.c
+++ b/qtest.c
@@ -1062,17 +1062,19 @@ void q_shuffle(struct list_head *head)
return;
int range = q_size(head) - 1;
- LIST_HEAD(tmp);
- for (; range > 1; range--) {
- struct list_head *curr = head->next;
+ struct list_head *new = head->prev;
+ for (; range; range--) {
int j = rand() % range;
-
+ struct list_head *old = head->next;
for (int i = 0; i < j; i++)
- curr = curr->next;
+ old = old->next;
- list_move_tail(curr, &tmp);
+ // swap old and new
+ struct list_head *tmp = old->prev;
+ list_move(old, new);
+ list_move(new, tmp);
+ new = old->prev;
}
- list_splice(&tmp, head);
}
Commit d46fe78
統計方法驗證-shuffle
1. 先計算計算 chi-square statistic
參考 rota1001 的開發紀錄，將腳本中輸入的字串操作改成乘法，也新增了一些提示訊息。使用 time.perf_counter 計時，比較兩個方法的效能差異：
test_count = 1000000
start_time = time.perf_counter()
input_str = "new\nit 1\nit 2\nit 3\nit 4\n"
for i in range(test_count):
input_str += "shuffle\n"
input_str += "free\nquit\n"
end_time = time.perf_counter()
print(f"執行時間: {end_time - start_time:.6f} 秒")
| 使用 loop | 字串乘法 |
|---|---|
| 452.90100 秒 | 0.00397 秒 |
Commit 4c858d3
Expectation: 41666
Observation: {'1234': 41430, '1243': 41782, '1324': 41855, '1342': 41923, '1423': 41823, '1432': 41725, '2134': 41509, '2143': 41963, '2314': 41902, '2341': 42156, '2413': 41341, '2431': 41806, '3124': 41641, '3142': 41761, '3214': 41611, '3241': 41838, '3412': 41447, '3421': 41657, '4123': 41416, '4132': 41186, '4213': 41455, '4231': 41481, '4312': 41706, '4321': 41586}
chi square sum: 28.869533912542597
後續進行 10 次計算，所有計算的結果如下：
28.86953391254259、25.4207747323957、23.952335237363798、 18.182786924590797、33.6160418566697、15.172274756396103、19.215955455287286、34.29611673786781、34.7917726683627、 17.876686026976433、21.46018336293381
結果大致介於 15~35 之間，但需要更多統計結果才能驗證其計算值的範圍。
2. 決定自由度
總共有
3. 選擇顯著水準
常見的
4. 統計檢定的結果
參考rota1001同學開發紀錄的腳本計算 P-value：
from scipy.stats import chi2
# print(chi2.ppf(0.05, 23))
# 35.17246162690806
# 可以看出自由度為 23 時，卡方值要多大才能讓大於此卡方值出現的機率小於 0.05
print(1 - chi2.cdf(28.869533912542597, 23))
# 0.18467433647899123
計算出來的結果大於顯著水準 P value(0.1~0.2) > alpha(0.05)，因此不拒絕
Entropy
論文〈Dude, is my code constant time?〉
Linux 核心的鏈結串列排序
TODO
