2023q1 Homework1 (lab0)

contributed by < kata1219 >

開發環境

$ gcc --version
gcc version 11.3.0 (Ubuntu 11.3.0-1ubuntu1~22.04) 
$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
CPU max MHz:                     5600.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4992.00
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           151
Model name:                      12th Gen Intel(R) Core(TM) i5-12400
Stepping:                        2
BogoMIPS:                        4991.99
Virtualization:                  VT-x
L1d cache:                       288 KiB
L1i cache:                       192 KiB
L2 cache:                        7.5 MiB
L3 cache:                        18 MiB

修改 queue.[ch]

q_free

清理 element 時忘記先把 element 內的 value 釋放掉，卡住很久，後來看了 q_release_element() 如何釋放記憶體後才發現問題

用語要精準，「卡住」是什麼？
jserv

q_insert_head / q_insert_tail

element 的 value 需要 strlen(s) + 1 的空間，包含結尾的 '\0'

想法: 一開始看不懂題目要求的 將字串 s 添加到 head 的開頭，struct list_head 中並無存放 char * 的欄位，看了教材及前輩的筆記後才了解到實際上是要添加一個新的 element 到 queue 的開頭。
<commit a60781e>

改進漢語表達。
jserv

更新: 使用 q_insert_head() 實現 q_insert_tail() 以降低重複程式碼。
<commit 92303d1>

q_delete_mid

想法: 找到中間的元素後，先分配其前後的 prev、next，再將其釋放。
<commit c093a8e>

更新: 原本實作需要先用 q_size() 得到 list 長度後，再釋放中間的元素，需要走訪整個 list 共 1.5 次(q_size() 1 次加上選定到中間的元素 0.5 次)。改成用快慢指針搭配 indirect 指標實作只需要走訪整個 list 一次。
<commit e66a933>

q_delete_dup

想法: 開發過程中需要思考如何標注出現過的字串，剛開始我一直在思考能不能用同一條 queue 就紀錄是否出現並在上面標注是否重複出現，想到的方法是在重複出現的 value 前面新增一個 element 並在裡面儲存特殊字元，之後檢查有無特殊字元就能知道字串是否重複，但一來是無法保證原本 queue 中的字串會不會含有特殊字元，二來是有可能會把 queue 變得很長，增加比對時間，並且需要大量的 list 操作。

最後決定配置兩條新的 queue，一條用於儲存出現過的字串，另一條用來儲存重複出現的字串，之後使用迴圈比對原本 queue 與儲存重複字串的 queue，如有相同則刪除。

q_swap

想法: 交換 curr 和 curr->next，先處理 next 指標，再處理 prev 指標
<commit 60d3374>

更新: q_swap() 為 q_reverseK() 的特例，可以用 q_reverseK 實作
<commit f39fc56>

q_reverseK

想法: 將 list 分成 q_size() / k 組，用 list_move() 從最後一組依序往前進行 reverse，完成所有組別的排序後，第一組將會回到最前面的位置。下圖為假設 k = 2 時。

在 git commit 時會出現 Possible misspelled word(s): reverseK 的提示，目前先改成 "Implement q_reverse_K()"，但在搜尋 commit title 時可能會有問題

你應該用合適的英語撰寫標題。
jserv

q_sort

想法: 使用 merge sort 進行排序，與其他演算法相比 merge sort 可以充分利用 linked list 的特性，只須改變 list 的指向不須另外配置記憶體即可完成交換。

在 Linked List 上使用 Quick Sort 的效率可能比使用 Merge Sort 低，主要是由於 Quick Sort 需要頻繁地存取前方和後方的節點，而 Linked List 的節點在記憶體中是不連續的，存取節點的前驅和後繼可能需要額外的時間消耗。

另外，Quick Sort 還需要進行遞迴操作，對於 Linked List 來說，每次遞迴都需要建立新的鏈結串列，這會增加額外的空間消耗，因此在 Linked List 上使用 Quick Sort 可能不如使用 Merge Sort 高效。

當然，如果資料集比較小，且對時間和空間的要求不是非常高，使用 Quick Sort 在 Linked List 上也是可行的。但對於大型資料集和高效率的排序需求，使用 Merge Sort 通常是一個更好的選擇。

– ChatGPT

上述是經典演算法描述，但 merge sort 的實作手段不見得總是如此。
jserv

q_descend

想法: 使用兩層迴圈檢查，外層迴圈-遍歷-走訪所有元素，內層迴圈比對元素的右方是否都小於該元素，如不合預期則刪除該元素。

注意用語，參見 資訊科技詞彙翻譯
jserv

謝謝老師提醒

q_merge

想法: 使用 q_sort 中的 mergeTwoLists() 將每一個 queue 都合併到第一個 queue。

可能會有效率問題，待改進。

比較 Linux 核心原始程式碼的 lib/list_sort.c 與 lab0-c 實作

研讀論文〈Dude, is my code constant time?〉

Welch's t-test

lab-0 的 simulation 模式使用了 Welch's t-test 進行比對，Welch's t-test 會取兩類資料，關於如何選擇輸入資料有不同方式，論文中使用 fix-vs-random，一類為固定資料，另一類為隨機選取。Welth's t-test 假設兩類的執行時間皆為 Student's t-distribution，Student's t-distribution 接近於常態分布，在樣本數較少的情況下相比於常態分布較為扁平，尾端的機率較高，當樣本數越多則會越接近常態分布，計算

$$t=\frac{\mathrm{\Delta }\overline{X}}{s_{\mathrm{\Delta }\overline{X}}}=\frac{\overline{X_1}-\overline{X_2}}{\sqrt{s_{\overline{X_1}}^2+s_{\overline{X_2}}^2}}$$

$$v=\frac{{(\frac{s_1^2}{n_1}+\frac{s_2^2}{n_2})}^2}{\frac{(s_1^2/n_1{)}^2}{n_1-1}+\frac{(s_2^2/n_2{)}^2}{n_2-1}}$$

得出兩類數據的 Welch's t-statistic(

$t$) 與自由度(

$v$) 後，由

$t$ 和

$v$ 運算出的 CDF 求出

$p$，若

$p$ 小於我們設定的閾值代表兩者的執行時間分布相似，我們可以判定程式執行時間為常數時間

$O(1)$，相反地，若

$p$ 大於我們設定的閾值代表程式執行時間不為常數時間。