# 2025q1 Homework1 (lab0)
contributed by < `alexc-313` >

### Reviewed by `SimonLiu423`
1. 在 `q_free()` 的實作中（commit [aca44ec](https://github.com/sysprog21/lab0-c/commit/aca44eca6483d44880c5a602f5ad933d8ce06cf2)），每次在釋放節點前會呼叫 `list_del(cur)` 將節點從該 list 中移除，但這步驟是可以省略的，因為釋放目前節點不會影響 `list_for_each_safe` 的運作，所以沒必要確保刪除過程中 list 的每個節點 `prev`、`next` 都是合法的。
2. `queue.h` 中已有 `q_release_element()` 函式可以去釋放指定的 element，為了增加可讀性及可維護性，建議將 `q_free()`、`q_delete_dup()` 中釋放節點的部分改為利用這個函式達成。
3. 大部分 commit message 中都沒有提及你如何實作該函式，會讓讀者難以理解你為何做這次修改，以及你如何實作。
4. 在 `queue_insert_*` 中，

    ...
    int len = strlen(s) + 1;
    new->value = malloc(sizeof(char) * len);
    if (!new->value) {
        free(new);
        return false;
    }
    ...

可以確定每次新增一個節點，該節點的 `value` 必定不會是 `NULL`，如此一來，在 `q_delete_node()` 中是否沒有必要先檢查再釋放？

    ...
    if (node->value)
        free(node->value);
    ...

5. Commit [e1647b8](https://github.com/sysprog21/lab0-c/commit/e1647b8fcd9106470537849cfb3331f3b2b4f16b) 中有不相干的修改。
6. `q_swap()` 中沒有判斷傳入的 `head` 是否為 `NULL` 或 list 是否為空，可能會造成不合法的記憶體存取。
7. `q_merge()` 若改為將所有節點移到第一個 queue，隨後在進行一次 `q_sort()`，速度是否會比原本的做法快？
8. Shuffle result 的直方圖中，X 軸的值重疊，無法看出該軸代表意義為何，該段落也沒有加以說明，建議可以為每個排列對應一個索引值，如 `1234 -> 0, 1243 -> 1, ...`，並用該索引值取代原本 X 軸的值。

### Reviewed by `NeedToDebugMyLife`
1. Commit message 應該包含程式的實作方式，而不是只有程式的功能。像是 Commit [eb73a28](https://github.com/sysprog21/lab0-c/commit/eb73a284f8979d2c40f1802b987ec1a8b1e3e6f6) 中，你的 commit message 只寫了 "This function reverses the list in groups of K elements at a time."，這段話說明了 `q_reverseK` 這個函式的 "功能"，而不是你實作這個函式的 "方式"。<br>
一個專案可能是跟其他開發者和未來的自己共同開發維護的。當不同開發者要針對你寫的程式做改動時，就能透過瀏覽你寫的 commit message 的內容來快速了解程式的運作原理是什麼，以快速針對問題來做處理，但如果 commit message 只寫了函式的功能，就會造成其他人需要先"重頭讀一遍"並且"理解"你的程式，才能夠對問題作後續的處理。這樣會大幅降低專案維護以及開發的效率。

2. Commit [112896d](https://github.com/sysprog21/lab0-c/commit/112896d5945ba2c2d0344fd86d9d76d3ba851b60) 中實作了 `q_delete_node` 函式，這部分可以使用 `<list.h>` 的 `list_del()` 加上 `<queue.h>` 內的 `q_release_element()` 來實現。

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ 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](https://github.com/sysprog21/lab0-c/commit/117a180a42f5733cb899c0d1eda96fce92e4216b)

使用 `malloc` 分配所需的記憶體，並用 `list.h` 中的 `INIT_LIST_HEAD` 函式來初始化佇列的 head。

### q_free
> Commit [aca44ec](https://github.com/sysprog21/lab0-c/commit/aca44eca6483d44880c5a602f5ad933d8ce06cf2)

在判斷 `head` 不是空指標後，用 `list.h` 中的 `list_for_each_safe` 巨集走訪每個節點，因為此巨集使用 `*safe` 來預先存放下一個指標，我們便可以使用 `free` 先釋放 `value` 使用的記憶體，再用第二個 `free` 釋放 `node` 本身所使用的記憶體，在走訪完整個佇列後，再用一次 `free` 釋放 `head`。

### q_insert head/tail
> Commit [a38b8fc](https://github.com/sysprog21/lab0-c/commit/a38b8fc814c53f02ce66a0ee6985a628c40b2cdd)

因為這兩個函式在概念上非常類似，所以在實作上我將這兩個函式放在同一個commit中。方法都是先判斷`head` 不是空指標後，用 `malloc` 逐次分配並確認記憶體成功的被分配，依據 [CERN Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 的建議，改用 `strncpy` 函式複製要插入佇列的數值，再分別使用 `list.h` 中的 `list_add` 或 `list_add_tail` 函式將複製完成的變數插入佇列中。

### q_remove head/tail
> Commit [f62cfd5](https://github.com/sysprog21/lab0-c/commit/f62cfd5f629f2f714d9f29802ffe092561114872)

如同上個 commit，這兩個函式在概念上非常類似，所以在實作上我也將這兩個函式放在同一個commit中。方法都是先判斷 `head` 不是空指標且非空佇列後，用 `list.h` 中的 `list_first_entry` 或 `list_last_entry` 找出目標節點的 `value`，再用 `strncpy` 函式複製到指定的變數，並確保字串的最後是終止字元 `\0` ，最後用 `list_del_init` 來移除節點並確保移除後的節點的指標有被妥善的處理，以避免後續使用上發生未定義的行為。

### q_size
> Commit [961c87b](https://github.com/sysprog21/lab0-c/commit/961c87bfdd318f898e81b941c378ece41bde5c19)

在判斷 `head` 是否空指標與是否是空佇列後，使用 `list.h` 中的 `list_for_each` 走訪並記錄節點數量。

### q_delete_mid
> Commit [e1647b8](https://github.com/sysprog21/lab0-c/commit/e1647b8fcd9106470537849cfb3331f3b2b4f16b)

在判斷 `head` 是否空指標與是否是空佇列後，使用快慢指標找出佇列的中點，將節點從佇列中釋放，並釋放節點所使用的記憶體。

### q_delete_dup
> Commit [f610366](https://github.com/sysprog21/lab0-c/commit/f610366bce1cb474a73b2a4f44905c4aa455b94f)

在判斷 `head` 是否空指標與是否是空佇列後，使用 `list.h` 中的 `list_for_each_entry_safe` 走訪整個佇列，當目前的節點的 `value` 跟下一個節點的 `value` 相同時，用變數 `found_dup` 記錄，並刪除目前節點。當目前節點不等於下個節點時，若 `found_dup == true` ，代表目前節點與上個已刪除的節點相同，故刪除該節點。

### q_delete_node
> Commit [112896d](https://github.com/sysprog21/lab0-c/commit/112896d5945ba2c2d0344fd86d9d76d3ba851b60)

在觀察到許多函式皆有使用以下程式碼後

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](https://github.com/sysprog21/lab0-c/commit/66086299d8fd99b7d1a00f6a715dabde75ea0e3f)

使用 `list.h` 中的 `list_move` 函式讓 `cur` 跟 `cur->next` 互換，此時 `cur` 在原本 `cur->next` 的位置，再將 `cur` 設為 `cur->next` 就可完成兩兩互換。
### q_reverse
> Commit [bc01842](https://github.com/sysprog21/lab0-c/commit/bc01842d4b65d92ec0baaad0a1161c0e1b2a82c9)

在判斷 `head` 是否空指標與是否是空佇列後，使用 `list.h` 中的 `list_for_each_safe` 走訪整個佇列把每一個節點逐一用 `list_move` 移動到佇列的 `head->next` 位置。
### q_reverseK
> Commit [eb73a28](https://github.com/sysprog21/lab0-c/commit/eb73a284f8979d2c40f1802b987ec1a8b1e3e6f6)

使用兩個 for 迴圈，用 `*start` 來記錄第一個將被倒置的節點，內部迴圈用來倒置 `*start` 後的 K 個節點，外部迴圈用更新 `*start`。

### merge_two
> Commit [2424ca7](https://github.com/sysprog21/lab0-c/commit/2424ca77bb9280e48e6b52d2701e40d9c27df3f2)

這是一個 `q_sort` 的輔助程式，此函式接收兩個 `*list_head` 參數，並使用迭代的方式將兩個佇列以遞增或遞減的方式合併，實作上我使用 `list_del` 將兩個節點從各自的佇列中移除，在比較其 `value` 後用 `list_add_tail` 把較小或較大的節點加到新的佇列 `merge` ，當其中一個佇列為空時，若其中一個佇列有尚未加入 `merge` 的節點，利用 `list_splice` 把剩餘的節點加在 `merge` 尾端，並在將第一個或第二個 `*list_head` 指向合併完成的佇列後回傳。

> Commit [8873e16](https://github.com/sysprog21/lab0-c/commit/8873e165768e59d1486d51ea0464f1cb61a40131)

為了讓 `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](https://github.com/sysprog21/lab0-c/commit/2424ca77bb9280e48e6b52d2701e40d9c27df3f2)

這個函式用遞迴實做 merge sort 演算法。
在用快慢指標找到佇列的中點後使用 `list_cut_position` 函式將佇列剖半，再呼叫自己並傳入剖半完的佇列，最後呼叫 `merge_two` 函式將所有佇列組合起來。

### q_ascend/descend
> Commit [8827730](https://github.com/sysprog21/lab0-c/commit/88277307c98288aab401a621e58a056f5c94bde7)

參考 `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](https://github.com/sysprog21/lab0-c/commit/94075cc419ef8bfeb470f8edd24b016e76169b75)

用 for 迴圈走訪除了第一個以外每個 `queue_contex_t` ，呼叫 `merge_two` 函式將佇列一個個合併到第一個佇列裡。

### 結果
由於我尚未完成 `lab0-c` 的 Welch's test 測試項目，所以除了 `trace-17` 的部份沒有通過以外，其他部份皆順利通過。
## 亂數
### shuffle
> Commit [a87564f](https://github.com/sysprog21/lab0-c/commit/a87564ff3fada11f262667d273b025a9a6916fdc)

在 `q_test.c` 中加入 `do_shuffle` 函式，再用 `ADD_COMMAND` 就可以使用新的命令 `shuffle`。

其中 `do_shuffle` 的實做方法如下：
先用 `q_size` 取得佇列長度 `len` ，用 `rand` 抽出一個在區間 $[0, len-1]$ 中的隨機數，並將 `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），所以統計檢定的結果不拒絕虛無假說。統計檢定的結果不拒絕虛無假說 $(H_0)$，也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻。
### 啟發和疑惑

由於 Fisher–Yates shuffle 是適用於陣列的演算法，在佇列上使用因為取用每個節點的時間並非 $O(1)$ 造成時間複雜度大幅增加，從 $O(n)$ 變成 $O(n^2)$，應該要使用適合佇列的演算法或是將佇列轉換成陣列。