# 2024q1 Homework1 (lab0)
contributed by < `Libright1558` >
:::danger
務必詳閱作業規範
:::
## 開發環境
```
$ 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): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-5350U CPU @ 1.80GHz
CPU family: 6
Model: 61
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
Stepping: 4
CPU max MHz: 2900.0000
CPU min MHz: 500.0000
BogoMIPS: 3600.04
Virtualization: VT-x
Caches (sum of all):
L1d: 64 KiB (2 instances)
L1i: 64 KiB (2 instances)
L2: 512 KiB (2 instances)
L3: 3 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
```
## 佇列實作
### `q_new`
> [commit 93da0b0](https://github.com/Libright1558/lab0-c/commit/93da0b0ed3d7a729cad1d51a6ae1c811c06020c7)
q_new 函式功能為新增一個 prev 指標與 next 指標均指向自身的佇列開頭。首先分配 struct list_head 大小的空間，如果分配失敗，則回傳 NULL，如分配成功，則使用 INIT_LIST_HEAD 函式將 prev 指標與 next 指標指向自身，最後回傳該佇列開頭。
```c
struct list_head *q_new()
{
struct list_head *head_node = malloc(1 * sizeof(struct list_head));
if (!head_node)
return NULL;
INIT_LIST_HEAD(head_node);
return head_node;
}
```
### `q_free`
> [commit 93da0b0](https://github.com/Libright1558/lab0-c/commit/93da0b0ed3d7a729cad1d51a6ae1c811c06020c7)
> <s>3/2 更新</s> ，[commit bb886d6](https://github.com/Libright1558/lab0-c/commit/bb886d604bc813d180b386786498641bc2cbdc95)
:::danger
1. 不需要在開發紀錄提到日期，因為 GitHub 和 HackMD 皆可追蹤變革。專注程式碼的改進。
2. 列出你 GitHub 帳號對應的超連結
:::
q_free 先檢查 head 是否存在，如果不存在則不做任何事。此處使用指標的指標 indirect，指向佇列開頭的 next 指標，指標 target 用以釋放節點空間,使用間接指標的好處在於 indirect 指標本身不需要在節點之間移動，可藉由改變 value of indirect 將節點上的 next 指標指向下一個節點，最後再釋放開頭節點空間。
:::danger
不需要在開發紀錄提到日期，因為 GitHub 和 HackMD 皆可追蹤變革。專注程式碼的改進。
:::
> <s>3/2 更新</s> ，`q_free` 因為考量到 `element_t` 物件的加入，故實作方式改為先取得 element_t 物件的位置，`並藉由q_release_element` 來刪除節點。
```c
void q_free(struct list_head *head)
{
if (head) {
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head) {
q_release_element(container_of(node, element_t, list));
}
free(head);
}
}
```
:::danger
改進你的漢語表達。
:::
### `q_insert_head/q_insert_tail`
> [commit bb886d6](https://github.com/Libright1558/lab0-c/commit/bb886d604bc813d180b386786498641bc2cbdc95)
:::danger
本 commit 並未依循 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 的規範，使用 `git rebase -i` 更正，隨時準備跟世界各地的開發者協作！
:::
q_insert_head/q_insert_tail 先檢查開頭節點、字串是否存在，如果存在則複製字串,並分配 element_t 大小的空間，將字串賦值到 element_t 的 value memeber 裡，最後將 element 加入到佇列裡。
### `q_remove_head/q_remove_tail`
> [commit bb886d6](https://github.com/Libright1558/lab0-c/commit/bb886d604bc813d180b386786498641bc2cbdc95)
:::danger
本 commit 並未依循 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 的規範，使用 `git rebase -i` 更正，隨時準備跟世界各地的開發者協作！
:::
q_remove_head/q_remove_tail 先檢查開頭節點、字串是否存在，如果存在，則取出指向 element_t 的指標，如果 element_t 物件內存在字串，且 sp 不為 NULL，則先將字串複製到 sp 內，之後在字串尾端加入中止符號，最後移除該節點。
### `q_size`
> [commit 239892a](https://github.com/Libright1558/lab0-c/commit/239892a3b7f6f419a4f6fd618e1a6a861baf71e7)
藉由<s>遍歷</s> 節點來計算節點數量。
:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
### `q_delete_mid`
> [commit 1493d63](https://github.com/Libright1558/lab0-c/commit/1493d6355ac23006730c52311efd4fe0a9e00f62)
:::danger
本 commit 並未依循 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 的規範，使用 `git rebase -i` 更正，隨時準備跟世界各地的開發者協作！
:::
如果開頭佇列存在且不為空佇列，則透過 q_size 計算總節點數量並除以二，得知中間節點的相對位置，找到節點後，先用 `list_del` 將其移出佇列，之後用 `q_release_element` 釋放空間。
### `q_swap`
> [commit f5f5a63](https://github.com/Libright1558/lab0-c/commit/f5f5a63ab41d45e4894873d031e03c352ccd021a)
`q_swap` 在佇列不為空且節點不為單一的條件下，使用 `prev` 與 curr 兩個指標，分別指向 `head->next` 與 `prev->next` ，之後紀錄 `prev->prev` 與 `curr->next` 的指標，並將 `prev` 與 `curr` 指向的節點交換位置。
### `q_reverse`
>[commit f5f5a63](https://github.com/Libright1558/lab0-c/commit/f5f5a63ab41d45e4894873d031e03c352ccd021a)
`q_reverse` 在佇列不為空且節點不為單一的條件下，將頭節點與尾節點兩兩對應並交換位置。
### `q_reverseK`
>[commit f78600f](https://github.com/Libright1558/lab0-c/commit/f78600fda797f5409356be00e203d923c629cbc4)
`q_reverseK` 藉由 `q_reverse` 反轉特定數量節點的位置。
### `q_ascend`
>[commit f78600f](https://github.com/Libright1558/lab0-c/commit/f78600fda797f5409356be00e203d923c629cbc4)
`q_ascend` 藉由從佇列尾部開始往前走訪，遇到比前一個節點字串值還要小的節點，就刪除它。
### `q_descend`
>[commit f78600f](https://github.com/Libright1558/lab0-c/commit/f78600fda797f5409356be00e203d923c629cbc4)
`q_descend` 藉由從佇列尾部開始往前走訪，遇到比前一個節點字串值還要大的節點，就刪除它。
### `q_sort`
>[commit fdcbea4](https://github.com/Libright1558/lab0-c/commit/fdcbea4a281238655463dc3467ac42a4dcf799b4)
透過將 [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1) 中所提到的 Timsort 引入作為 `q_sort` 實作。原先嘗試以 [Powersort](https://arxiv.org/pdf/1805.04154.pdf) 進行實作，然而在串列節點個數在 18000 以上時，遇到執行時間超時的問題，有待解決。
### `q_merge`
## 效能評測
#### `timsort vs listsort`
`listsort` 參考 linux 核心排序演算法的實作，`timsort` 參考 [2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)，測驗二對 `timsort` 的實作。
生成 49999 個 `element_t` 節點，節點內包含長度 5~10 個字元的隨機值，上述測試資料被用於測試 `timsort` 與 `listsort` 執行效能，分別各執行 49999 次，結果以 `gnuplot` 呈現如下(綠色為 timsort ，紫色為 listsort)︰
參考 [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh) ，使用F檢定來決定 `timsort` 與 `listsort` 是否有相同的平均執行時間。
1. 首先建立虛無假說：
虛無假說：
+ $H_0$ : $\mu_1 = \mu_2 = ... \mu_k$
對立假說：
+ $H_1$ : $Not\ all\ means\ are\ equal$
其中 $\mu_i$ 為每種演算法的平均執行時間。
2. 之後計算 F 值：
mean square due to treatment 公式如下：
$MSTR = \frac{\sum\limits_{j=1}^k n_j(\mu_j-\mu)^2}{k-1}$
mean square error 公式如下：
$MSE = \frac{\sum\limits_{j=1}^k (n_j-1)s_j^2}{n_T-k}$ , $n_T = \sum\limits_{j=1}^k n_j$
k 為所有排序演算法的種類數量，$\mu$ 為所有排序演算法的執行時間總平均，$n_j$ 為每種排序演算法的執行次數，$s_j$ 為每種排序演算法執行時間的變異數。
F 值公式：
$F = \dfrac{MSTR}{MSE}$
本次評測所得到的 F 值為 99996 。
3. 是否拒絕虛無假說：
[參考材料](https://online.stat.psu.edu/stat200/book/export/html/213)
(Numerator) Degrees of Freedom ：
$df_{between}=k-1$
(Denominator, Error) Degrees of Freedom ：
$df_{within}=n-k$
$n$ 為所有排序演算法執行次數合計，$k$ 為排序演算法種類數量
本評測 (Numerator) Degrees of Freedom 為 1，(Denominator, Error) Degrees of Freedom 為 99998 。
[查表得知](http://www.socr.ucla.edu/Applets.dir/F_Table.html)，critical value 在 $a=0.05$ 的情況下約為 3.84 ，而本評測 F 值為 99996，遠大於 critical value ，因此 reject null hypnothesis ，表示 `timsort` 與 `listsort` 執行時間平均值在統計學上不相同。
`timsort` 執行時間為：38908 (cycles_per_sec) ， `listsort` 執行時間為：40677 (cycles_per_sec），顯示 `listsort` 相較於 `timsort` 在隨機的 49999 筆資料下，執行 49999 次，花費較多執行時間。
Sign in with Wallet
Connect another wallet