HackMD
2024q1 Homework1 (lab0)
contributed by < Dainel-0224 >
Reviewed by david965154
這裡採取遞迴
merge_sort來實作q_sort
應該修改為 : 「這裡採取 merge sort 的遞迴版本來實作 q_sort 」較適當，加了底線會讓人誤以為你實作了這個函式，也應提到使用了下方函式 q_merge_two 完成 merge 的功能。
一開始想不到一個從頭走到尾的簡潔寫法，但在經過 HotMercury 及 devarajabc 的提醒，採取從尾走到頭的方式
可以解釋一下為什麼從頭走到尾不行，但可以從尾走到頭，例如 :
因為 q_descend 題目要求為 : 只要在此節點後方的節點有存在比此節點更大之成員 value 則刪去，因此等同於尋找佇列後方的嚴格遞減佇列，直接從後方找最大成員 value 並向前比對，只需逐一走訪一次就可以完成實作。
「從尾走到頭」不精準，因為在環狀雙向鏈結串列中，已是首尾相接，於是尾端必定會緊接著開頭。真正的關鍵是運用 prev 和 next 來存取節點的方向。
jservImage Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
開發環境
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz
CPU family: 6
Model: 165
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 5
CPU max MHz: 5100.0000
CPU min MHz: 800.0000
BogoMIPS: 7599.80
指定的佇列操作
q_new
用 malloc 來配置 head 所需記憶體，並使用INIT_LIST_HEAD初始化head。要注意的是malloc不一定會成功，在配置記憶體失敗時，得到指標值會是 NULL，因此需要在配置後檢查head。
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
q_free
藉由 container_of 巨集找到 element_t 結構的起始地址，offsetof(type, member) 可得知 member 在 type 這個結構體位移量。將絕對位址 (char ) pmember 減去 offset ，可得到結構體的起始位址。head 是個特例，無法藉由 containerof 巨集來找到對應的節點，因為後者並未嵌入到任何結構體之中，其存在是為了找到 list 整體。
q_insert_head & q_insert_tail
strdup 有使用 malloc 來配置字串存放的記憶體空間，空間配置失敗時要釋放記憶體，這裡要釋放整個 element_t。 而 q_insert_head 、q_insert_tail 分別使用 list_add 和 list_add_tail 來串接節點。
q_remove_head
利用 list_first_entry 找到第一個 element ,並用 list_del 將其與佇列斷開連接，再利用 strncpy 複製字串。
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || list_empty(head))
return NULL;
element_t *first = list_first_entry(head, element_t, list);
list_del(&first->list);
if(sp && first->value){
strncpy(sp, first->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return first;
}
q_remove_tail
一開始我只將 list_first_entry 改為 list_last_entry ，但在參考< alanjian >的想法後發現，這兩題程式碼相似度高，其實可以重複使用。
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || list_empty(head))
return NULL;
return q_remove_head(head->prev->prev, sp, bufsize);
}
q_size
用 list_for_each 走訪每個節點，並隨之遞增 count 。
q_delete_mid
這裡使用了 fast 和 slow 兩個指標，當 fast 走到序列結尾時，slow 走到序列一半，再將這個 element 刪除即可。
q_reverse
使用 list_for_each_safe 來走訪序列是因為需要 safe 來紀錄當前處理節點的下個節點，在使用 list_move 將 node 移至首位。
q_reverseK
我的想法是在走訪了 k 個節點後，將這 k 個節點利用 list_cut_position 從原序列截斷後再利用 q_reverse 反轉，最後再用 q_splice 接回原序列。我一開始想利用 q_new 創建一個節點來連接截斷的序列，然後發現在這個函式中不能使用 malloc ，並經過同學的題點改為使用 LIST_HEAD 。
$ ./qtest <test.cmd
FATAL ERROR: Calls to malloc disallowed
FATAL Error. Exiting
list_for_each_safe (node, safe, head) {
if (count != 1) {
count--;
} else {
- tmp = q_new();
+ LIST_HEAD(tmp);
count = k;
list_cut_position(tmp, cut, node);
q_reverse(tmp);
list_splice(tmp, cut);
cut = safe->prev;
}
}
q_swap
q_swap 可以想成 q_reverseK 而 k = 2 。
q_descend ＆ q_ascend
明確標注同學的 GitHub 名稱。
一開始想不到一個從頭走到尾的簡潔寫法，但在經過 HotMercury 及 devarajabc 的提醒，採取從尾走到頭的方式，在過程中會判斷目前節點與前一個節點的大小，如 descend 前一個節點小於目前節點，則需要將前一個節點刪除，相反則移動目前節點到前一個節點。
q_sort
這裡採取遞迴 merge sort 來實作 q_sort ，並且使用 q_merge_sort 來達成兩串列合併，一開始一樣以快慢兩個指標來找出中間點，再利用 list_cut_position 將串列分成兩串再進行一次 q_sort。
你如何確保目前的測試程式已涵蓋排序演算法的最差狀況？
q_merge_two
這裡逐一比對兩個串列的節點的大小，合併的方式是從輸入的二個串列中，根據 descend 參數取較小或較大的，放到一個暫存串列 tmp 中。
一開始我是以 list_add_tail 這個函式來將節點串接上新的串列，但在執行時遇到無窮迴圈。發現是這個函式沒有將節點從原本串列移除，最後改用 list_move_tail 將問題解決。
while (!list_empty(left) && !list_empty(right)) {
element_t *l = list_entry(left->next, element_t, list);
element_t *r = list_entry(right->next, element_t, list);
if (strcmp(l->value, r->value) >= 0) {
- list_add_tail(&l->list, &tmp);
+ list_move_tail(&l->list, &tmp);
} else {
- list_add_tail(&l->list, &tmp);
+ list_move_tail(&r->list, &tmp);
}
}
q_delete_dup
我的想法是用兩個指標指比對兩個節點是否相同，相同則刪除。原本我使用 list_for_each_entry_safe 來做比對，但是在 strcmp(cur->value, post->value) post 指向 head 時會造成 Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted 。
bool q_delete_dup(struct list_head *head)
{
if(!head)
return false;
bool flag = false;
element_t *post, *cur;
list_for_each_entry_safe(cur, post, head, list) {
- if(!strcmp(cur->value, post->value)) {
+ if(&post->list != head && !strcmp(cur->value, post->value)) {
flag = true;
list_del(&cur->list);
q_release_element(cur);
} else {
if(flag) {
list_del(&cur->list);
q_release_element(cur);
flag = false;
}
}
}
return true;
}
q_merge
利用兩個指標來走訪 chain ，每次迭代合併兩個 q_contex_t ，因為這裡使用 q_merge_two 來做合併，因此 first 串列會越來越長，使得走訪成本越來越高。
需要有更多討論。
論文研讀〈Dude, is my code constant time?〉
Step1. Measure execution time
a ) class definition
建立兩種類型的資料，並重複測量其作為輸入資料時的執行時間。
固定資料：這包括了特殊的極端情況。(such as low-weight input for arithmetic operations)
隨機資料：隨機生成的資料，以模擬實際情況下的不確定性和變化性。
b ) cycle counters
使用 CPU 的 cycle clock， 可準確取得執行時間。
c ) environment conditions
最大限度地減少環境變化對結果的影響，每次測量都對應一個隨機選擇的類別
Step2. Post-processing
在統計分析之前，我們對每個測量值進行了一些處理。
Cropping ：由於測量過程中可能會受到作業系統或其他活動的干擾，我們需要對測量值進行裁剪，去除受外部干擾的部分，以獲得準確的執行時間。
Higher-order preprocessing : 根據所應用的統計測試，去應用像是 centered product mimicking higher-order DPA attacks 預處理得到更好的數據。
Step3. Apply statistical test
採用統計檢定方法來試圖反駁「兩個時序分佈相等」的原假設。成功反駁這個假設將證明該假設錯誤，從而表明程式執行時間不是常數。
- t-test：為 dudect 所使用的 Welch's t-test。
Valgrind 與 Address Sanitizer
這部份是因為我在 q_free 少寫了一行 free(head) 所導致的。
$ valgrind -q --leak-check=full ./qtest <tttt.cmd
l = []
l = [b]
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
==20977== 56 bytes in 1 blocks are still reachable in loss record 1 of 1
==20977== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==20977== by 0x10F327: test_malloc (harness.c:133)
==20977== by 0x10F72C: q_new (queue.c:17)
==20977== by 0x10CDE3: do_new (qtest.c:155)
==20977== by 0x10E011: interpret_cmda (console.c:181)
==20977== by 0x10E5C6: interpret_cmd (console.c:201)
==20977== by 0x10F230: run_console (console.c:691)
==20977== by 0x10D403: main (qtest.c:1258)
==20977==
更改完程式碼後執行 ＄valgrind --tool=massif ./qtest <tttt.cmd 得到 massif.out.19175 檔案。再利用以下指令可視化程式執行時期的記憶體行為。
$ ms_print massif.out.19175
--------------------------------------------------------------------------------
Command: ./qtest
Massif arguments: (none)
ms_print arguments: massif.out.19175
--------------------------------------------------------------------------------
KB
20.45^ :::
| :::#:
| : #:
| : #:
| : #: :
| @ #: @
| :@ #: @
| :@ #: @
| :@ #: @
| :@ #: @
| :@ #: @
| :@ #: @
| :@ #: @
| :@ #: @
| :@@@ #: @
| :@@@ #: @@
| :@@@ #: @@
| :@@@ #: @@
| :@@@ #: @@
| @@:@@@ #: @@
0 +----------------------------------------------------------------------->ki
0 313.0
$massif-visualizer massif.out.19175
實作 shuffle
根據〈你所不知道的 C 語言: linked list 和非連續記憶體〉中提到的 Fisher–Yates shuffle 演算法來實作 shuffle 。
- 假設初始的序列如下:
| 隨機數範圍 | 選擇隨機數 | 原始序列 |
|---|---|---|
| 1 2 3 4 5 |
- 從 1~5 間隨機選一數字，例如這裡的
3，將原始序列從左開始數的第 3 個數字和最後 1 個數字對調
| 隨機數範圍 | 選擇隨機數 | 更新後序列 |
|---|---|---|
| 1-5 | 3 | 1 2 5 4 3 |
- 從 1~4 間隨機選一數字，以這裡為例是 2，所以把原始序列從左開始數的第 2 個數字和倒數第 2 個數字交換
| 隨機數範圍 | 選擇隨機數 | 更新後序列 |
|---|---|---|
| 1-4 | 2 | 1 4 5 2 3 |
- 重複這個流程，直到隨機數範圍為 0
實作
- 模仿 do_reverse 在 qtest.c 中產生 do_shuffle。
- 在 queue.c 中實作 q_shuffle
Expectation: 41666
Observation: {'1234': 41886, '1243': 41890, '1324': 41603, '1342': 41557, '1423': 41721, '1432': 41872, '2134': 41610, '2143': 41395, '2314': 41707, '2341': 41679, '2413': 41962, '2431': 41945, '3124': 41790, '3142': 41464, '3214': 41562, '3241': 41347, '3412': 41504, '3421': 41982, '4123': 41643, '4132': 41867, '4213': 41370, '4231': 41482, '4312': 41600, '4321': 41562}
chi square sum: 21.029184466951474
