# 2024q1 Homework1 (lab0)
contributed by < `yenshipotato` >
### Reviewed by `yenslife`
#### `q_reverse`
> 將走訪到的節點之 prev 與 next 交換
利用 list API 來簡化 `q_reverse` 實作：其實可以用 `list_move` 直接將走訪到的節點移到開頭，增加程式碼可讀性。
```diff
struct list_head *cur, *next;
list_for_each_safe (cur, next, head) {
+ list_move(cur, head);
- cur->next = cur->prev;
- cur->prev = next;
}
- now = head->next;
- head->next = head->prev;
- head->prev = now;
```
#### `q_remove_tail` / `q_remove_head`
直接在 `q_remove_tail` 中呼叫 `q_remove_head` 即可，減少重複程式碼。
注意 `list_first_entry` 會回傳 `head` 的下一個節點，所以要傳入 `head->prev->prev` 才是指向尾端節點。
```graphviz
digraph main {
node[shape=plaintext]
head [fontcolor="red"];
l [label="list_first_entry(head->prev->prev, ...)",fontcolor="blue"];
node[shape=box]
s0 [label="1"];
s1 [label="2"];
s2 [label="3"];
s3 [label="4"];
s4 [label="5"];
s5 [label="6"];
{
rank="same";
s0->s1
s1->s0
s1->s2
s2->s1
s2->s3
s3->s2
s3->s4
s4->s3
s4->s5
s5->s4
s5->s0
s0->s5
}
head->s0
l->s5
}
```
```diff
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
- if (!head || list_empty(head))
- return NULL;
- element_t *rm_node = list_last_entry(head, element_t, list);
- if (sp) {
- strncpy(sp, rm_node->value, bufsize - 1);
- sp[bufsize - 1] = '\0';
- }
- list_del(&rm_node->list);
+ return q_remove_head(head->pre->prev, sp, bufsize);
}
```
> 感謝建議，已更新
#### Commit message
從無到有的函式實作用 "Fix" 開頭可能不太恰當，建議用 "Add" 或是 "Implement"。
## 開發環境
```shell
$ 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: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 13th Gen Intel(R) Core(TM) i5-13600K
CPU max MHz: 5100.0000
CPU min MHz: 800.0000
BogoMIPS: 6988.80
```
## 指定的佇列操作
### q_size
根據作業要求中「預期目標 + 開發環境設定」章節內的指示，以對應的 C 語言程式碼取代 `q_size` 中的 `return -1;`
### `q_new`
:::danger
列出程式碼之前，要充分討論你的想法、考量因素，也該談及你作法的副作用 (side effect)。
:::
<s>閱讀完 list.h 裡提供的 API 後，開始實作 queue.c 裡的功能。</s>
```c
struct list_head *q_new()
{
struct list_head *new_head = malloc(sizeof(struct list_head));
if (new_head)
INIT_LIST_HEAD(new_head);
return new_head;
}
```
:::danger
說好的進度呢？
:::
### `q_free`
`list_for_each_entry_safe` 走訪佇列每一個節點，並 `q_release_element` 釋放當前節點，最後再釋放 `head` 。
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *cur_entry, *safe_entry;
list_for_each_entry_safe (cur_entry, safe_entry, head, list)
q_release_element(cur_entry);
free(head);
}
```
### `q_insert_head`
宣告一個 `node` 用以存放新節點位址的指標，如果 `malloc` 失敗的話回傳 `false` 。若函式沒有回傳則判斷 `value` 在賦值後是否為空字串，若不然，則將節點新增至佇列中；反之則釋放 `node` 並回傳 `false` 。
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
if ((node->value = strdup(s)) != NULL)
list_add(&node->list, head);
else {
free(node);
return false;
}
return true;
}
```
### `q_insert_tail`
功能上與 `q_insert_head` 無異，只需把 `list_add` 替換成 `list_add_tail`
```diff
/* Insert an element at tail of queue */
if ((node->value = strdup(s)) != NULL)
- list_add(&node->list, head);
+ list_add_tail(&node->list, head);
```
### `q_remove_head`
查看 `queue.h` 後確認 `sp` 與 `bufsize` 的用途，宣告 `rm_node` 用以存放待移除節點位址的指標，若 `sp` 不為 `NULL` ，則將節點 `value` 中的字串複製到 `sp` ，最後呼叫 `list_del` 將節點從佇列中移除。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *rm_node = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, rm_node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&rm_node->list);
return rm_node;
}
```
### `q_remove_tail`
功能上與 `q_remove_head` 無異，只需將取得待移除節點位址的函式替換成 `list_last_entry` 即可
```diff
return NULL;
- element_t *rm_node = list_first_entry(head, element_t, list);
+ element_t *rm_node = list_last_entry(head, element_t, list);
if (sp) {
```
:::danger
diff 該針對「你程式碼之間的變異」，而非針對給定的程式碼。
開發紀錄中，應該要看到你的「開發過程」。
提高程式碼的可重用程度。
:::
### `q_delete_mid`
在閱讀了教材[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)其中關於快慢指標的的案例後，決定以此方法進行實作。宣告一組 `fast` 和 `slow` 快慢指標，其中 `fast` 以一次兩節點的方式走訪佇列； `slow` 則一次一節點，當 `fast` 到達佇列結尾時， `slow` 會在佇列中央，再移除 `slow` 所在的節點即可
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *fast = head->next, *slow = head->next;
while (fast->next->next != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
element_t *rm_node = list_entry(slow, element_t, list);
list_del(slow);
q_release_element(rm_node);
return true;
}
```
:::danger
diff 該針對「你程式碼之間的變異」，而非針對給定的程式碼。
開發紀錄中，應該要看到你的「開發過程」。
:::
### `q_reverse`
使用 `list_for_each_safe` 走訪佇列，並將走訪到的節點之 `prev` 與 `next` 交換，最後再處理 `head` 。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *now, *next;
list_for_each_safe (now, next, head) {
now->next = now->prev;
now->prev = next;
}
now = head->next;
head->next = head->prev;
head->prev = now;
}
```
:::danger
diff 該針對「你程式碼之間的變異」，而非針對給定的程式碼。
開發紀錄中，應該要看到你的「開發過程」。
:::
### `q_reverseK`
參考 [chiangkd](https://github.com/sysprog21/lab0-c/commit/06697595174ce67dc538943e69f5f4e69dacc14f)，以 `list_cut_position` 與 `list_splice_tail_init` 、 `list_splice_init` ，便可將佇列以 k 個為單位執行 `q_reverse` 。
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return;
int len = q_size(head), node_num;
struct list_head *temp = head->next;
if (len < k)
return;
LIST_HEAD(temp_head);
do {
for (node_num = 0; node_num < k && temp != head; node_num++)
temp = temp->next;
if (node_num == k) {
LIST_HEAD(cut);
list_cut_position(&cut, head, temp->prev);
q_reverse(&cut);
list_splice_tail_init(&cut, &temp_head);
}
} while (temp != head);
list_splice_init(&temp_head, head);
}
```
:::danger
diff 該針對「你程式碼之間的變異」，而非針對給定的程式碼。
開發紀錄中，應該要看到你的「開發過程」。
:::
### `q_swap`
`q_reverseK` 的特殊情境，與 `q_reverseK` with k = 2 無異。
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
q_reverseK(head, 2);
}
```
:::danger
diff 該針對「你程式碼之間的變異」，而非針對給定的程式碼。
開發紀錄中，應該要看到你的「開發過程」。
:::
### `q_ascend` 、 `q_descend`
#### 輔助函式 `cmp`
為使程式碼更好維護與簡潔，新增了 `cmp` 函式，接收兩個 `struct list_head*` 回傳內部節點 `value` 的比較結果
```c
static int cmp(struct list_head *a, struct list_head *b)
{
return strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value);
}
```
:::danger
明確指出你參考的 GitHub 帳號名稱。
:::
在觀摩 [25077667](https://github.com/sysprog21/lab0-c/commit/5b689d81b8e80a716177f92cd1a262d7c813faba)、[chiangkd](https://github.com/sysprog21/lab0-c/commit/cb78f8f06e613a6cf1d43df18145a94dceb31d37)、[cheezad](https://github.com/sysprog21/lab0-c/commit/9e84e978f056d94da9c7092ca31124507ee2ff40)的做法後，發現他們都額外新增了反向走訪的功能。於是我思考能不能直接做 `q_reverse` 搭配 `list_for_each_safe` ，我認為是一樣的效果，還可以讓程式碼更簡潔，決定直接以實作驗證我的想法。
:::danger
你的實驗佐證在哪裡？
> `q_reverse` 後，節點的 `next` 與 `prev` 會交換，於是 `list_for_each_safe` 中的走訪 `next` 節點在這裡就會是走訪原始佇列的 `prev` ，儘管這個做法所需的時間將會比直接新增反向走訪功能還長，但時間複雜度仍維持 O(n) ，而充分重複利用撰寫好的函式也讓程式碼更簡潔。
>
> 提供數學推導和實驗，工程人員要用客觀事實說話。 :notes: jserv
:::
#### `q_ascend`
於反轉後走訪節點時，移除 `value` 比前一個節點大的節點，再反轉即是結果。
```c
int q_ascend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
struct list_head *now, *safe;
q_reverse(head);
list_for_each_safe (now, safe, head->next) {
if (now == head)
break;
if (cmp(now, now->prev) > 0) {
list_del(now);
}
}
q_reverse(head);
return q_size(head);
}
```
#### `q_descend`
功能上與 `q_ascend` 無異，只需更改移除的條件(較大 -> 較小)
```diff
- if (cmp(now, now->prev) > 0) {
+ if (cmp(now, now->prev) < 0) {
```
在使用 qtest 測試時發現有記憶體錯誤，經確認是沒有釋放節點的空間。
```diff
+ element_t *rm_node = list_entry(now, element_t, list);
list_del(now);
+ q_release_element(rm_node);
```
修正後再度測試，沒有發現錯誤
### `q_delete_dup`
我在這裡思考很久，因為看了 queue.h 中並沒有提到執行此函式時佇列會是排序好的狀態，但附上的 leetcode 題目連結則說佇列預設是排序好的狀態，於是我去看 traces 目錄中有關於此功能的檔案，發現在 `dedup` 前會執行 `sort` ，於是我假設佇列在執行前會是排序好的狀態。而在排序好的情況之下，佇列中 `value` 重複的節點必定相鄰，於是只需要走訪佇列時檢查該節點與下一個節點是否重複，若然，移除該節點後繼續下一輪檢查。如此，便只需要走訪每個節點一次。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
element_t *now, *safe_now;
bool dup = false;
list_for_each_entry_safe(now, safe_now, head, list)
{
if (now->list.next != head &&
strcmp(now->value, safe_now->value) == 0)
{
list_del(&now->list);
q_release_element(now);
dup = true;
}
else if (dup)
{
list_del(&now->list);
q_release_element(now);
dup = false;
}
}
return true;
}
```
### `q_sort`
> commit [ca67e78](https://github.com/yenshipotato/lab0-c/commit/ca67e783b25bfbd5c35d340783dbb0b2cd5f3f75)
這裡我參考了 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 新增了 `merge` 和 `merge_final` 兩個函式輔助執行，前者執行兩個鏈結串列的單向合併(去掉了 `prev` )；後者則會鏈結串列的 `prev` 重建，以組成新的雙向鏈結串列。並搭配使用上述所提到的輔助函式 `cmp` 作為 `sort` 內的比較函式，最後將 list_sort.c 內的 sort 部分改寫，使得可以在此程式內運行。
:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
### `q_merge`
我重新查閱了 queue.h 發現有提供 `queue_contex_t` 作為佇列的存取點，接著，我首先想到的策略是，將除了第一個以外的所有佇列接到第一個佇列的末端，最後再用 `q_sort` 排序，並據此開始實作。
```c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return 0;
queue_contex_t *now, *first = list_entry(head->next, queue_contex_t, chain);
list_for_each_entry(now, head, chain)
{
if (now == first)
continue;
if (&now->chain == head)
break;
list_splice_tail_init(now->q, first->q);
}
q_sort(first->q, descend);
return q_size(first->q);
}
```
後來我看到 `queue.h` 聲明程式在呼叫此功能前，所有佇列都會是以排序好的狀態，說明我的方法在效率上還有改善的餘地。
至此， `make test` 裡的分數達到 95/100。根據作業說明應閱讀論文並著手修改 dudect 以修復判斷常數執行時間的功能
---
## `dudect`
:::danger
指出論文和實作程式碼有出入的地方並充分討論。
:::
在我參閱了 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h#L429) 後，在原始碼裡的 `dudect_main` 發現了作業檔案 `dudect/fixture.c` 也有的函式 `update_statistics` ，但不同的是，`dudect_main` 裡除了 `update_statistics` 還有 `prepare_percentiles` ，據 dudect.h 裡的註解，這是用以 set different thresholds for cropping measurements，結合作業說明所說， percentile 相關的功能沒有被實作，於是我先試著將有關於 `prepare_percentiles` 的部分加進作業裡。
直接加入了 dudect.h 中的 `cmp` 和 `percentile` 到 fixture.c 中
並把 `prepare_percentiles` 裡的參數改寫
```c
static void prepare_percentiles(int64_t *exec_times)
{
qsort(exec_times, N_MEASURES, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < N_MEASURES; i++)
{
exec_times[i] = percentile(
exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / N_MEASURES)),
N_MEASURES);
}
}
```
```diff
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
+ prepare_percentiles(exec_times);
update_statistics(exec_times, classes);
ret &= report();
```
經 make test 測試後通過，分數為 100/100
## 在 qtest 提供新的命令 shuffle
在參閱 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)後，以 original method 實作，在 `qtest.c` 中實作負責 shuffle 的函式，主要邏輯與 Fisher–Yates shuffle 原始的方法相同。
在佇列尚未被選中的部分裡隨機挑一個節點，將被選中節點移至最後面，並重複上述行為直到所有節點都被選中。
:::danger
`qtest.c` 已呼叫 `srand`，不該在 `do_shuffle` 額外呼叫。
:::
```c
bool do_shuffle()
{
if (!current)
return false;
for (int i = q_size(current->q); i > 0; i--) {
struct list_head *node = current->q;
int n = rand() % i + 1;
for (; n > 0; n--)
node = node->next;
list_del(node);
list_add_tail(node, current->q);
}
q_show(3);
return true;
}
```
:::danger
使用指定的程式碼縮排風格。
:::
### 以統計的原理來分析你的實作，探究洗牌的「亂度」
$H_0$ : Shuffle 的每個可能發生的機率相同，即符合 Uniform distribution
$H_1$ : Shuffle 至少有一可能結果發生的機率不同
我以對 `[1 2 3 4]` 執行 1000008 次 shuffle 為數據，進行卡方檢定
| 可能結果 | 觀測次數 | 預期次數 |
| --------- | -------- |:--------:|
| [1 2 3 4] | 41484 | 41667 |
| [1 2 4 3] | 41786 | 41667 |
| [1 3 2 4] | 41677 | 41667 |
| [1 3 4 2] | 41809 | 41667 |
| [1 4 2 3] | 41640 | 41667 |
| [1 4 3 2] | 41620 | 41667 |
| [2 1 3 4] | 41751 | 41667 |
| [2 1 4 3] | 41853 | 41667 |
| [2 3 1 4] | 41894 | 41667 |
| [2 3 4 1] | 41856 | 41667 |
| [2 4 1 3] | 41409 | 41667 |
| [2 4 3 1] | 41709 | 41667 |
| [3 1 2 4] | 41935 | 41667 |
| [3 1 4 2] | 41571 | 41667 |
| [3 2 1 4] | 41394 | 41667 |
| [3 2 4 1] | 41799 | 41667 |
| [3 4 1 2] | 41634 | 41667 |
| [3 4 2 1] | 41358 | 41667 |
| [4 1 2 3] | 41758 | 41667 |
| [4 1 3 2] | 41722 | 41667 |
| [4 2 1 3] | 41694 | 41667 |
| [4 2 3 1] | 41396 | 41667 |
| [4 3 1 2] | 41574 | 41667 |
| [4 3 2 1] | 41685 | 41667 |
經計算，卡方值為 15.170134638922889 ，自由度為 23(24-1) ，根據查表結果 p-value 會落在 (0.8, 0.9) ，顯著水準設定為 0.05 ，因為 0.8>0.05 ，故不拒絕虛無假說。
沒有足夠證據能否定此 shuffle 演算法符合 Uniform Distribution。
而根據圖表的結果來看 shuffle 的頻率大致符合 Uniform distribution 。
#### 測試程式
- [ ] `qtest` 的輸入 `input.txt`
```
new
it 1
it 2
it 3
it 4
shuffle
```
- [ ] 執行 1000008 次 shuffle 且僅將 shuffle 後的結果輸出
```bash
#!/bin/bash
for (( i=1; i<=1000008; i=i+1 )); do
./qtest < data/input.txt > data/temp.txt && sed -n "6p" data/temp.txt >> data/output.txt
done
```
Sign in with Wallet
Connect another wallet