# 2024q1 Homework1 (lab0)
contributed by < `RRbell1027` >
### Reviewed by `SimonLee0316`
* 在git commit的時候 不同功能應該分開
* commit message 並沒有寫，可以參考[如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
> 明確指出 git commit 並提供參考做法，實際做一次給學員看，不要只提「心法」。
> :notes: jserv
### Reviewed by `SHChang-Anderson`
* 筆記中可以加入 commit 紀錄連結，以更好追蹤討論相關程式碼。
* 嘗試使用 List API 如 : list_move_tail 或 list_move 透過不同順序移動節點達成 q_swap 實作。
* shuffle 實作中，你對四個節點的鏈結串列進行實驗，但由於只執行了 1000 次測試，無法驗證是否符合 Uniform distribution ，可以嘗試先針對三個節點的鏈結串列進行實驗，提高測試的次數，觀察實驗結果。
### Reviewed by `Shawn531`
* Shuffle 實作中提到 Fisher–Yates shuffle 演算法在鏈結串列上會比陣列多處理上 n 倍的時間。是否可以說明以及提出解決方法。
* Shuffle 實作中，考慮 `old` 剛好為串列中最後一個元素之狀況或許能幫助改善結果。
* 可以附上 commit 連結。
### Reviewed by `ShawnXuanc`
* commit 中有看到標題為 `1-13 and 16 complete` 可能會不太容易了解意思，提交內容一次涵蓋太多功能
* 可以嘗試將程式碼重複利用像是 `q_remove` 以及 `q_insert` 的部份
### Reviewed by `Shiang1212`
在[如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/) 有提到：限制標題最多只有 50 字元。
> 50 字元的限制不是一個硬規則，而是一個經驗法則。讓標題保持在 50 字以下能夠確保標題的可讀性，並且強迫作者思考如何用更簡潔的方式表達發生什麼事情。
如 [d9f91cb](https://github.com/sysprog21/lab0-c/commit/d9f91cbbf85221313bc19cbd3002c4be6d6d6b12) 就沒有滿足要求。儘可能的概括這個 commit 的更動內容，能有效提高 commit message 的可讀性。如果你發現沒辦法在 50 字內描述這個 commit，那你該想想是否在該 commit 內做了太多的更動。
## 開發環境
```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: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
Virtualization: VT-x
L1d: 192 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 1.5 MiB (6 instances)
L3: 9 MiB (1 instance)
NUMA node0 CPU(s): 0-11
```
## 針對佇列操作的程式碼實作
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
:::info
好的，已改寫。
:::
依照我原先對鏈結串列的了解，在看完 lab0 敘述後，我原以為的 `list_head` 結構體會是：
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
char *value;
};
```
在想要存取的資料 `value` 之上加上指標 `prev` `next` 來實作資料間的串連。因此，當翻閱 `list.h` 以及 `queue.h` 對 `struct lsit_head` 的運用感到非常訝異。c 語言不具備類別 ，但卻可以運用物件在結構中擺放的順序實作繼承(is a)，更可以添加功能豐富且成熟的結構實作組合(has a) 概念，利用 `container_of` 存取包含 `struct list_head` 的 `element_t` 。藉此，便不需要為每個具有鏈結串列特性的資料集都實作一整個函式庫。
`struct list_head` 設計了不含有效資料的指標頭 `header`，操作時使用指向 `header` 的指標 `*head`，實作[「linked list 和非連續記憶體」](https://hackmd.io/@sysprog/c-linked-list)中提到的間接指標技巧，在寫完作業回過頭複習時 <s>格外印象深刻</s>。
:::danger
不用說「格外印象深刻」，資訊科技領域變化極快，你每天都會發現令你「印象深刻」的議題。
:::
本次作業要求滿足 `qtest.c` 中的 17 項題目要求，目前進度為功能完善（trace-01-ops 到 trace-13-mlloc 完成），卻缺乏效率（除了 trace-16-perf 以外都沒過關）。在後續的檢討中我將近一步改善程式效能，並研讀課程筆記裡的論文。
### `q_new`
初始化 `queue->q` ，依照需求建立「」。
`queue.h` 的註釋，空佇列是指 `queue->q` 需包含 `head` 且 `header->next` 和 `header->prev` 皆指向 `head` 。
```graphviz
digraph {
rankdir = LR
node [shape=plaintext];
head [label=<<table>
<tr><td port="next">next</td>
<td>value</td>
<td port="prev">prev</td></tr>
</table>>];
q->head[constraint=false];
head:next:w->head:w;
head:prev:e->head:e;
}
```
:::danger
allocate 的翻譯是「配置」，以區隔 dispatch (分配/分發) 的翻譯。
:::
可以在 `malloc` <s>分配</s> 空間後，利用 `list.h` 中的巨集`INIT_LIST_HEAD` 來實作。
要注意確認 `malloc` 是否成功指派空間， `qtest.c`會模擬指派空間失敗。
```c
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
```
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
時間複雜度和空間複雜度都是 $O(n)$
### `q_free`
`list.h` 提供了相當於 `container_of` 的 `list_entry` 巨集，並結合 `list_each` 實作迭代 `element_t` 的迴圈。
```diff
- for (struct list_head *li = head->next; li != head; li = li->next) {
- element_t *ele = (element *)((char *)li - offset(element_t, lsit));
+ element_t *ele;
+ list_for_each_entry(ele, head, list) {
```
`list.h `提供了 `list_for_each_safe` 以防對當前節點的操作會導致丟失下個節點。
值得注意的是，`element_t->value` 是 `char *`，在接下來的 `q_insert_head` 和 `q_insert_tail` 中都是指派 `strdup` 的回傳值，可以通過 `free()` 來清空記憶體空間。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
空間複雜度 $O(1)$ ，時間複雜度 $O(n)$
### `q_insert_head`
利用 `list.h` 提供的 `list_add` 可以將節點放入 linked list 頭部。
```c
element_t *ele = malloc(sizeof(element_t));
/* ... */
list_add(&ele->list, head);
```
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
要注意 `strdup` 內部也使用了 malloc 來分配空間，所以要做檢查。
```c
ele->value = strdup(s);
if (!ele->value) {
free(ele);
return false;
}
```
空間複雜度 $O(1)$ ，時間複雜度 $O(1)$
### `q_insert_tail`
與 `q_insert_head` 同理。
空間複雜度 $O(1)$ ，時間複雜度 $O(1)$
### `q_remove_head`
先用指標指向 target element 避免找不到空間， `list_del` 不會更動目標節點資訊，有可能發生非預期結果。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
如果不加上 `\0` ， 當 `bufsize` 小於 `strlen(node->value)` 會導致字串讀取不會終止。
```c
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
```
空間複雜度 $O(1)$ ，時間複雜度 $O(1)$
### `q_remove_tail`
與 `q_remove_head` 同理。
空間複雜度 $O(1)$ ，時間複雜度 $O(1)$
### `q_size`
原先想利用 `q_contex_t` 尋找 `size` ，後續發現無法從 `*head` 找到 queue 的 `q_contex_t` ，於是用回作業牛刀小試的程式碼。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
空間複雜度 $O(1)$ ，時間複雜度 $O(n)$
### `q_delete_mid`
利用快慢指標找尋中間節點。
<s>[time=Wed, Mar 6, 2024 11:42 PM]list_sort.h 程式碼對快慢指標找中間節點有更好的寫法，記得改。</s>
:::danger
HackMD 會記錄日期，你不用在開發紀錄中標示。
:::
```c
struct list_head *slow = head->next, *fast = head->next;
while (fast->next != head && fast->next->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_del(slow);
```
空間複雜度 $O(1)$ ，時間複雜度 $O(n)$
### `q_delete_dup`
利用兩個迴圈來比對兩節點字串是否重複，因為外迴圈不會訪問到內迴圈中已經被刪除的節點，故時間複雜度不是 $O(n^2)$ 而是 $O(n)$ 。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
因為會更改到當前外迴圈<s>訪問</s> 節點的下個節點，所以 `for` 中的 `safe` ，要在內迴圈跳出後才能指派。
:::danger
access 的翻譯是「存取」，而非「訪問」(visit)
:::
```c
for (li = head->next; li != head; li = safe) {
e1 = list_entry(li, element_t, list);
bool flag = false;
while (li->next != head) {
e2 = list_entry(li->next, element_t, list);
if (strcmp(e1->value, e2->value) == 0) {
flag = true;
/* free e2 */
} else {
break;
}
}
safe = li->next;
if (flag) {
/* free e1 */
}
}
```
空間複雜度 $O(1)$ ，時間複雜度 $O(n)$
### `q_swap`
* 利用兩個指標兩個兩個訪問節點，故迭代的 `for` 迴圈要另外寫。
* `l1` 和 `l2` 交換後順序發生了變動，expression-3 要注意寫法。
```c
for (l1 = head->next, l2 = head->next->next; l1 != head && l2 != head;
l1 = l1->next, l2 = l2->next->next->next)
```
空間複雜度 $O(1)$ ，時間複雜度 $O(n)$
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
### `q_reverse`
想在一個迴圈內連同 `head` 一起處理，故不使用 `list.h` 的巨集，而實作了 do-while 迴圈。
```c
do {
/* swap next and prev */
} while (li != head);
```
空間複雜度 $O(1)$ ，時間複雜度 $O(n)$
### `q_reverseK`
新增兩個 linked list head `rev` 和 `batch` ，利用 `list_cut_position` 將 K 個節點裁切到 `batch` 翻轉後暫存到 `rev` ，來確保 `batch` 之間的順序不變。
```c
list_for_each_safe (li, safe, head) {
cnt++;
if (cnt == k) {
/* remove k node
* reverse
* store into rev
*/
}
}
```
空間複雜度 $O(1)$ ，時間複雜度 $O(n \times k)$
### `q_sort`
<s>[筆記未完成]</s>
:::danger
不要輕易說「完成」，工程領域是持續的檢討和改進。
> 好的，後續會再優化或更新
:::
:::danger
某些濫用「優化」的語境，根本與「改良」和「改善」無異，那為何不直接講「改良」和「改善」呢？
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
* 使用了快速排序法，因為無法分配陣列所以用遞迴。
* 模仿了測驗一的演算法，將節點分成三部分：大於 piv、 piv 和小於等於 piv
```c
/* Seperate list into 3 part.*/
list_for_each_entry_safe (ele, safe, head, list) {
list_del(&ele->list);
if ((strcmp(pivot->value, ele->value) > 0) ^ descend)
list_add(&ele->list, &left);
else
list_add(&ele->list, &right);
}
/* recursive */
q_sort(&left, descend);
q_sort(&right, descend);
/* store back to list*/
list_splice(&left, head);
list_add_tail(&pivot->list, head);
list_splice_tail(&right, head);
```
空間複雜度 $O(log(n))$，時間複雜度 $O(nlog(n))$
:::danger
明確標注你參閱的 GitHub 帳號名稱。
:::
參考了<s>同學</s> 程式碼後，嘗試使用合併排序法，效率高於快速排序法。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
使用遞迴將佇列二分，並利用 `q_merge` 做合併。
```c
q_sort(&left, descend);
q_sort(head, descend);
/* Create a queue chain for q_merge */
queue_contex_t left_queue = {.q = &left};
queue_contex_t right_queue = {.q = head};
LIST_HEAD(q_head);
list_add_tail(&right_queue.chain, &q_head);
list_add_tail(&left_queue.chain, &q_head);
q_merge(&q_head, descend);
```
:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
### `q_ascend`
* 反過來迭代，當前節點如果大於下一個節點就刪除。
```c
/* iterate from the last to first */
for (struct list_head *li = head->prev->prev, *safe = li->prev; li != head;
li = safe, safe = li->prev) {
element_t *cur = list_entry(li, element_t, list),
*pre = list_entry(li->next, element_t, list);
/* if cur > pre */
if (strcmp(cur->value, pre->value) > 0) {
/* free cur */
}
}
```
空間複雜度 $O(1)$ ，時間複雜度 $O(n)$
### `q_descend`
與 `q_ascend` 同理。
空間複雜度 $O(1)$ ，時間複雜度 $O(n)$
### `q_merge`
與 `q_swap` 類似的兩兩合併，發現效能比依序和第一的佇列合併來得好。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
利用快慢指標找到中心點，將鏈結串列拆分成兩半依序合併，利用遞迴重複動作。
```c
/* Seperate queue chain */
struct list_head *qchain1 = head;
LIST_HEAD(qchain2);
list_cut_position(&qchain2, slow, head->prev);
/* Merge two list */
int size = q_merge(qchain1, descend) + q_merge(&qchain2, descend);
/* Merge qchain1 and qchain2 */
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
:::danger
明確標注你參照的 GitHub 帳號名稱。
:::
參考了<s>同學</s> 程式碼，改為同時合併所有佇列，刪除了遞迴邏輯，效能比兩兩合併好。
```c
/* Compare all the queues in the same time.
* Append the maximum(or minimum) node to sorted list.
* I just post the most important part of the code.
*/
list_for_each (qi, head) {
if (!target)
target = ctx->q->next;
else {
int cmp =
strcmp(list_entry(ctx->q->next, element_t, list)->value,
list_entry(target, element_t, list)->value);
if (descend ^ (cmp < 0))
target = ctx->q->next;
}
}
list_del(target);
list_add_tail(target, &sorted_list);
```
---
## 在 qtest 提供新的命令 shuffle
鏈結串列在索引上效能不彰， Fisher–Yates shuffle 演算法在鏈結串列上會比陣列多處理上 n 倍的時間。
:::danger
很好，你的改進方案呢？
:::
```c
/* queue.c */
/* Shuffle queue 8*/
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int size = q_size(head);
struct list_head *old, *tmp;
for (int i = size; i > 1; i--) {
old = head;
int r = rand() / (RAND_MAX / (i - 1) + 1) + 1;
while (r > 0) {
old = old->next;
r--;
}
tmp = old->prev;
list_del(old);
list_move(head->prev, tmp);
list_add_tail(old, head);
}
}
```
:::danger
command 的翻譯是「命令」，而非「指令」(instruction)
:::
在 `qtest.h` 上新增 `do_shuffle` 函式，並在 `Makefile` 上新增<s>指令</s> `make` 來執行 lab0 的 Python 程式碼。
```shell!
# Makefile
shuffle: qtest scripts/shuffle.py
scripts/shuffle.py -c
```
:::warning
授課教師現在還用 2012 年出貨的 MacBook Air，後者性能更好，足以開發課程的所有程式碼，那你呢？
> 抱歉，因為第一次測試時當機，故降低了測試次數。但確實不該是電腦性能不佳的問題，我會再找找看原因。
:::
* <s>由於電腦性能不佳</s> ，僅測試了1000次。
Sign in with Wallet
Connect another wallet