# 2024q1 Homework1 (lab0)
contributed by < [`Shawn531`](https://github.com/Shawn531) >
### Reviewed by `ssheep773`
<s>建議</s> 在呈現函式的程式碼時，可以加上函式名稱和輸入的參數，因為輸入的參數和回傳的型態也是很重要的資訊
### Reviewed by `SimonLee0316`
> 你的洞見呢？
### Reviewed by `SHChang-Anderson`
* 使用 [perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 效能分析工具針對 Linux 核心的鏈結串列排序進行實驗。
> 審查學員的 git commits 了嗎？
### Reviewed by `ShawnXuanc`
可以考慮不要將未正確執行的功能 `push` 上去像是 q_delete_dup 的 `commit` 內容為 `segmentation now` 後面有修復一次但還是一樣未成功，還有其他的功能也有這樣的問題
後面在成功修復函式功能後可以加上功能的解說
`commit` 的標點符號沒有統一，像是有些 `commit` 最後缺少標點符號
### Reviewed by `Shiang1212`
以 `q_sort` 的開發來說，你上傳 [2746d01](https://github.com/sysprog21/lab0-c/commit/2746d014f795a042dc0230107e55e8dd0c1307ff)、[268745e](https://github.com/sysprog21/lab0-c/commit/268745eddafdc53ef4d8a529627c87d4cb931492)、[5b4f0ab](https://github.com/sysprog21/lab0-c/commit/5b4f0ab94bd8a2346c35ad039ba42da1de0dcac5) 三個 commit，前兩個 commit 的 `q_sort` 都無法正常運作，最後一個 commit 才完成了 `q_sort` 的開發。我建議上傳最後這個 commit 到 Github 上就好，並將開發思路記錄在 commit message 中，減少 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: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 24
On-line CPU(s) list: 0-23
Vendor ID: GenuineIntel
Model name: 13th Gen Intel(R) Core(TM) i7-13700K
CPU family: 6
Model: 183
Thread(s) per core: 2
Core(s) per socket: 16
Socket(s): 1
Stepping: 1
CPU max MHz: 5400.0000
CPU min MHz: 800.0000
BogoMIPS: 6835.20
```
## 指定的佇列操作
### `q_new`
```c
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
```
首先利用 malloc 配置記憶體空間，並宣告一個指向 list_head 的指標，並檢測是否發生記憶體配置是否失敗。接下來使用 "list.h" 中提供的 `INIT_LIST_HEAD` 完成佇列的初始化。
### q_free
```c
if (!head)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list)
q_release_element(entry);
free(head);
```
使用 `list_for_each_entry_safe` 走訪整個鏈結串列，並且使用 q_release_element 釋放所有節點所配置的記憶體，最後再將 head 釋放掉。這邊會使用 list_for_each_entry_safe 的原因是若只用 list_for_each_entry 會發生將目前節點釋放而找不到下一個節點的問題，因此這邊使用 safe 先移到下一個，再將前一個刪掉。
### q_insert_head and q_insert_tail
```c
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
node->value = strdup(s);
if (!node->value) {
free(node);
return false;
}
list_add(&node->list, head);
return true;
```
首先要做的是檢查 head 是否為 NULL ，接下來配置一個 element_t 的節點node，並將此節點的 value 設為 s ，`strdup` 會將 s 複製一份，然後分配足夠的記憶體空間儲存這個 replica 並 return 這個新空間的指標，這樣做可以避免直接對原始字串做修改。如果複製的這一步驟出錯，也需要將 node 釋放掉，若對的話則繼續往下做，將這個節點加入到鏈結串列的頭或尾中。
### q_remove_head and q_remove_tail
```c
if (!head)
return NULL;
element_t *node = list_first_entry(head, element_t, list);
if (!node)
return NULL;
list_del(&node->list);
if (!sp || !bufsize)
return NULL;
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
return node;
```
> commit [aab1bad](https://github.com/sysprog21/lab0-c/commit/aab1badcf837f52de3f2d592ec89ee27af0d5bb7)
透過巨集所寫好的 `list_last_entry` `list_first_entry` 可以輕鬆地找到第一個節點和最後一個節點，並使用 list_del 將目標 node 從鏈結串列拔除，並且將要移除的 node 的 value 複製到 sp 裡面，最後加上`sp[bufsize - 1] = '\0';`使最後一個元素為結數字元，若不這樣做結尾的話會出現無法預期的錯誤。
```
ERROR: Removed value meerkat_panda_squirrelXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerka
```
原先的想法為`sp=node->value;`我認為在功能上是與`strcpy(sp, node->value)`是一樣的，但要考慮到若`node->value`在某些狀況被改變獲釋放將會改變 sp，因為他們是共用同一個記憶體位置。
```diff
- sp = node->value;
+ strcpy(sp, node->value);
```
### q_size
```c
int count = 0;
if (!head)
return 0;
element_t *entry;
list_for_each_entry (entry, head, list) {
count++;
}
return count;
```
使用 list_for_each_entry 走訪所有節點，並使用 count 去紀錄 size。
### q_delete_mid
```c
if (!head)
return false;
int len = q_size(head);
struct list_head *prt = head->next;
int count = 0;
while (count <= len / 2 - 1) {
prt = prt->next;
count++;
}
element_t *node_to_delete = list_entry(prt, element_t, list);
list_del(prt);
q_release_element(node_to_delete);
return true;
```
採用一個較為直觀的作法，先使用`q_size()`得到鏈結串列的長度，爾後使用一個指標 prt 紀錄搭配 while loop 來找到中間的地址，找到後透過 list_entry 將 prt 由小範圍的`list_head`映射大範圍`element_t`，最後將 prt 從鏈結串列拔除再使用 q_release_element 釋放掉 node_to_delete。
:::danger
改進你的漢語表達。
:::
```目前分數 53/100```
```bash!
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
Probably constant time
ERROR: Freed queue, but 80080 blocks are still allocated
```
寫完 q_delete_mid 後會出現 not constant time 的問題，會再思考更佳解。此外發現目前尚有 80080 blocks 沒有被釋放，代表上面有些 function 的記憶替配置用完沒有好好的釋放，會多注意。
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」。
:warning: 留意詞彙的使用：
* [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
* [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
:::
### q_delete_dup
```c
struct list_head *pivot = head->next;
while (pivot != head) {
struct list_head *current = pivot->next;
while (current != head) {
element_t *pivot_e = list_entry(pivot, element_t, list);
element_t *current_e = list_entry(current, element_t, list);
struct list_head *next = current->next;
if (strcmp(pivot_e->value, current_e->value) == 0) {
list_del(current);
q_release_element(current_e);
} else
break;
current = next;
}
pivot = pivot->next;
}
return 1;
```
> commit [58cc771](https://github.com/sysprog21/lab0-c/commit/58cc7710ee7464f90ac2bc854505416c2f765e16)
在實作這一個函式的時候，我的想法是使用兩個 for loops 進行檢查，其中 pivot 為第一層 while loop 的變數，它會跟著這一層 while 遞增，下一層 while 則會有 current next 兩個變數。主要會讓 pivot 和 current 進行比較，若是一樣則會將 current 從鏈結串列拔掉並刪除此 element，若是不一樣則會直接 break。目前到這邊並沒有刪除 pivot，因此如下方的 command line，`[2 1 1]`做 dedup 後預期輸出會是 `[2 1]`。
```bash!
l = [2 1 1]
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [2 ... ]
ERROR: Queue has more than 1 elements
```
然而卻一直得到 `[2 ...]` 這個結果，不管怎麼樣檢查就是檢查不出來，大概在這邊耗費了兩個小時，最後索性繼續完成這個 function。加入了 flag 來檢查是否一樣，若一樣則會刪除pivot。
```diff!
+ bool flag = 0;
while (pivot != head) {
+ element_t *pivot_e = list_entry(pivot, element_t, list);
struct list_head *current = pivot->next;
while (current != head) {
- element_t *pivot_e = list_entry(pivot, element_t, list);
+ pivot_e = list_entry(pivot, element_t, list);
element_t *current_e = list_entry(current, element_t, list);
struct list_head *next = current->next;
if (strcmp(pivot_e->value, current_e->value) == 0) {
list_del(current);
q_release_element(current_e);
+ flag = 1;
} else
break;
current = next;
}
pivot = pivot->next;
+ if (flag) {
+ list_del(pivot->prev);
+ q_release_element(pivot_e);
+ flag = 0;
+ }
```
> commit [2f17f7b](https://github.com/sysprog21/lab0-c/commit/2f17f7b2f1a2aa1389323fb6a77fb420ac842489)
```bash!
l = [2 2 1]
cmd> dedup
l = [1]
```
竟然就這樣得到正確答案，所以會卡這麼久就是因為原來輸出不會如實輸出，只要錯了就會報 `...` 給你，這結局著實讓我意外。
### q_swap
```c
while (node != head && node->next != head) {
struct list_head *next = node->next;
list_move(next, node->prev);
node = node->next;
}
```
:::danger
- [ ] traverse (動詞) 和 traversal (名詞)
根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* to pass or move over, along, or through.
* to go to and fro over or along.
其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。
還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞：
* ergon (對應英語的 work)
* odos (對應英語的 path 或 way)
最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。
因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
透過<s>遍歷</s> 的方始從左到右，將目前節點的下一個節點 next 使用` list_move `移到目前節點的左邊，爾後直接將目前節點設定成下一個元素。原先在寫這個函式的時候，有考慮到奇數與偶數的問題，但使用`list_move`後，目前節點前面會再多一個元素，而往下跳一個後正好前面會有兩個元素，巧妙地解決這個問題。
### q_reverse
```c
while (next != head) {
next = node->next;
list_move(node, head);
node = next;
}
```
在反轉的這個函式，使用了一個很簡單的概念 : 從左到右依序將目前的元素放到鏈結串列的第一個。搭配`list_move`可以輕鬆地實作這件事。需要注意的是要在移動節點之前，先將 next 記錄起來，若是沒有做這一步，那麼 node 更新到的地址將會是第一個的下一個。
### q_reverseK
```c
while (next != head) {
while (count < k) {
next = current->next;
list_move(current, next_head);
current = next;
count++;
}
next_head = next->prev;
count = 0;
}
```
使用與 q_reverse 相似的概念，依序將第一個元素使用``` list_move(current, next_head) ```移至鏈結串列的第一個，與 q_reverse 較為不同的地方是，在移動節點時，會依照 K 值更新 next_head 的位置，q_reverse 則為固定head，裡面的 while loop 會利用記數的方式來更新 next_head 的位置，以達到分段 K 個元素的功能。
```diff=
while (next != head) {
- while (count < k) {
+ while (count < k && next != head) {
```
> commit [d414353](https://github.com/sysprog21/lab0-c/commit/d4143532c2146113f3bb1522a797349ebc0b7396)
後來發現原先程式碼無法處理鏈結串列數量不是 K 的倍數之狀況，因此在裡面的 while loop 新增條件以檢查 next 是否超出鏈結串列。
寫到這邊往上回顧發現我的命名很不一定，像是目前節點一下為 node 一下為 current ，有時會將自己搞混，在往後的 coding 我會特別注意這個問題，至於寫完的函式，我打算之後再來做修改。
```diff!
- if (!head)
+ if (head == NULL || head->next == head)
return false;
```
將所有非插入類函式對 head 的第一個檢查的條件做修改，以確保若為空鏈結的話就 return。
### q_ascend and q_descend
```diff
struct list_head *current = head->next;
struct list_head *next = current->next;
- struct list_head *temp = current;
+ struct list_head *temp = current->prev;
+ bool flag = 0;
int len = q_size(head);
while (next != head) {
while (next != head) {
element_t *current_e = list_entry(current, element_t, list);
element_t *next_e = list_entry(next, element_t, list);
- temp = current;
- if (strcmp(current_e->value, next_e->value) >= 0) {
+ temp = current->prev;
+ if (strcmp(current_e->value, next_e->value) > 0) {
list_del(current);
q_release_element(current_e);
len--;
+ flag = 1;
break;
}
next = next->next;
}
- current = temp->next;
- next = current->next;
+ if (flag) {
+ current = temp->next;
+ next = current->next;
+ } else {
+ current = current->next;
+ next = current->next;
+ }
+ flag = 0;
+ }
```
在實作這個函式時也遇到一點困難，第一點是會錯說明的意思，我原先以為比較後要刪除目前節點的點，之後仔細看才發現是要刪除目前節點。此外我一開始也犯了一個基本錯誤，就是將```temp = current```，之後將 current 刪掉，雖然我有做 temp 的動作，但實際上還是訪問到同樣的地址，因此會出錯，較為保險的做法式刪除``` next->prev ```，此外我也加了一個 flag 以分辨哪些是要刪除那些式不刪除，正確採去下一步行動。
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
:::
### q_sort
原先使用 bubble sort 作為排序的演算法，然而由於時間複雜度的限制，因此將演算法改為 merge sort，也順便呼應最後的 q_merge。除了 q_sort 以外，額外寫了兩條 function 已達成 q_sort，分別是 `merge()`和`midPoint()`。
採用遞迴的方法實作 merge sort，會先將一個 linked-list 分成兩個 linked-list，使用`list_cut_position`將 head 到 mid 的節點全部接到 a_head 後面，再使用`list_splice_init`將剩餘的節點 (mid 到最尾端節點)接到 b_head 後面，這樣就會實作分割的動作。接下來分別再對 a_head 和 b_head 做 q_sort，當分到不能再分的時候，最後被 call 的 function，則會進到 merge 裡面，將兩個串列接起來，爾後一直往外跳，最後將整個串列接起來，完成 merge sort。
```diff
struct list_head *mid = midPoint(head);
list_cut_position(&a_head, head, mid);
- list_splice(head, &b_head);
+ list_splice_init(head, &b_head);
q_sort(&a_head, descend);
q_sort(&b_head, descend);
merge(&a_head, &b_head, head, descend);
```
值得注意的是在一開始我使用 `list_splice` 而不是 `list_splice_init`，這兩者的差別在於後者會多一個`LIST_HEAD_INIT`，而這個用意就是要將 head 正確地與其他元素段開連結，若少了這一步，將會出現分法存取記憶體的錯誤。
```c
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
list_splice(list, head);
INIT_LIST_HEAD(list);
}
```
:::danger
你如何確保目前的測試程式已涵蓋排序演算法的最差情況？
:::
#### merge
`merge`函式主要的功能就是將兩個串列升序或降序合併在一起。概念也相當簡單，若 a_head->next 和 b_head->next 都不為空就會一直比較 a_head->next 和 b_head->next，假設現在為 ascending，若 a_e 小於 b_e，則會將目前 a_head->next 這個指標移到 c_head 中。值得一提的是不用特地取下一個元素，因為當目前元素被移走後，下一個元素就會遞補上來，利用這個特性完成比較並串接的步驟。
最後若是跳出 while loop 若存在任一非空串列的話，就需要將此串列接到 c_head 後面。
:::danger
改進你的漢語表達
:::
```c
while (a_head->next != a_head && b_head->next != b_head) {
element_t *a_e = list_entry(a_head->next, element_t, list);
element_t *b_e = list_entry(b_head->next, element_t, list);
if (descend) {
if (strcmp(a_e->value, b_e->value) >= 0)
list_move_tail(a_head->next, c_head);
else
list_move_tail(b_head->next, c_head);
else
if (strcmp(a_e->value, b_e->value) <= 0) {
list_move_tail(a_head->next, c_head);
else
list_move_tail(b_head->next, c_head);
}
}
if (a_head->next != a_head)
list_splice_tail(a_head, c_head);
if (b_head->next != b_head)
list_splice_tail(b_head, c_head);
```
#### midPoint
`midPoint`顧名思義就是在取中點，採取了 slow 走一步，fast 走兩步的方式來實作，當 fast 走到終點時，slow 正好會走到中點。
```c
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
```
### q_merge
```c
queue_contex_t *q_contex = list_entry(head->next, queue_contex_t, chain);
struct list_head *q_current = head->next->next;
while (q_current != head) {
queue_contex_t *current_contex =
list_entry(q_current, queue_contex_t, chain);
list_splice_init(current_contex->q, q_contex->q);
q_current = q_current->next;
}
q_sort(q_contex->q, descend);
return q_contex->size;
```
> commit [0a3f7c3](https://github.com/sysprog21/lab0-c/commit/0a3f7c3a4363d7b9c591364424ba4abfdaf1bee0)
最後實作 q_merge，由於 q_sort 的部分是用 merge sort 實作，因此 merge 的想法就單純是把每個 queue 接起來再進行 merge sort。這邊用到一個先前沒有用到的結構`queue_contex_t`如下:
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
使用以下圖示說明，head 會鏈結到 chain，其中 chain 又可以映射到 queue_contex_t 這個結構，裡面會有 q, chain, size, id，chain 為縱向的指標，而 q 相對於單條鏈結串列的 head。因此只要依序從 head 開始往後找，並使用 list_entry，即可訪問到每條鏈結串列。
<s>
</s>
:::danger
使用 Graphviz 重新製圖，嵌入到 HackMD 筆記中。
:::
而目前的分數為 95 分，剩餘的五分是有些記憶體沒有正確被釋放，目前找不到問題在哪裡。
> 正確答案: 程式結束時有未釋放的記憶體，不過卻還有指標指著。請參照<s>下一章</s>
>
```bash
ERROR: Freed queue, but 40040 blocks are still allocated
--- trace-17-complexity 0/5
--- TOTAL 95/100
```
##### 最後 debug
:::danger
明確標注你參考的 GitHub 帳號名稱
:::
透過比對<s>同學</s> 的程式碼，發現將 remove 的函式改成下方這樣終於讓分數達到100了。我認為是因為原先若 sp 為 NULL 會 return NULL，會造成若在外面有釋放這個動作的話，原本的狀況會造成 node 無法正確被釋放，因為 return NULL。因此下放這樣就算 sp 為 NULL 還是會 return node，合理解釋 blocks are still allocated 的問題。
```diff
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
- if (!head)
+ if (head == NULL)
return NULL;
element_t *node = list_first_entry(head, element_t, list);
- if (!node)
+ if (node == NULL)
- return NULL;
list_del(&node->list);
- if (!sp || !bufsize)
- return NULL;
- strncpy(sp, node->value, bufsize - 1);
- sp[bufsize - 1] = '\0';
+ if (sp) {
+ strncpy(sp, node->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
+ }
return node;
}
```
> commit [bd45485](https://github.com/sysprog21/lab0-c/commit/bd454851e39fb9072974b45e7921648bf0fe8398)
:::warning
縮減非必要的修改，例如 `node == NULL`
:::
```bash
--- TOTAL 100/100
```
---
## Valgrind + 自動測試程式
我是先將 queue.c 實作完成才開始細看 Valgrind 的說明，發現這就是我先前 qtest 卡關 95 分找不到哪裡出錯最完美的 debug 工具。儘管在實作 queue.c 時會報錯，但只是一句簡單的英文 `Freed queue, but 40040 blocks are still allocated`，我也不知道要從何開始檢查，只能人工一個一個比對。
因此我透過這個工具來檢查我 commit 前的版本究竟有甚麼問題。執行以下命令:
`$ valgrind -q --leak-check=full ./qtest `
然後手動將 trace-17-complexity.cmd 裡的命令輸入進去，就可以得到以下報錯資訊，在此僅列出四個中的一個。
```bash
ERROR: Freed queue, but 40040 blocks are still allocated
==113119== 479,239 bytes in 10,010 blocks are still reachable in loss record 1 of 4
==113119== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==113119== by 0x10F2E7: test_malloc (harness.c:133)
==113119== by 0x10F55F: test_strdup (harness.c:212)
==113119== by 0x10F7A7: q_insert_head (queue.c:43)
==113119== by 0x110465: measure (constant.c:116)
==113119== by 0x110905: doit (fixture.c:134)
==113119== by 0x110905: test_const (fixture.c:164)
==113119== by 0x110A54: is_remove_head_const (fixture.c:177)
==113119== by 0x10C472: queue_remove (qtest.c:302)
==113119== by 0x10C8BC: do_rh (qtest.c:410)
==113119== by 0x10DFD1: interpret_cmda (console.c:181)
==113119== by 0x10E586: interpret_cmd (console.c:201)
==113119== by 0x10F1F0: run_console (console.c:691)
```
valgrind 的 memory lost 可以分為幾種
* definitely lost: 真的 memory leak
* indirectly lost: 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak，但是只要修好前面的問題，後面的問題也會跟著修復。
* possibly lost: allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間
* still reachable: **程式結束時有未釋放的記憶體，不過卻還有指標指著**，通常會發生在 global 變數。
檢查上述報錯資訊所提到的程式碼 `q_insert_head`, `qtest`，其中 `q_insert_head` 在這邊會報錯我認為只是因為沒有釋放掉的記憶體是在這邊 malloc 的，並不代表是因為這個函式沒有正確釋放。因此我進而檢查 `qtest`裡面的`queue_remove`函式。可以看到就如同我使用觀察法得到的結論，由於 remove 只將 node 從串列拔除，需要透過 `q_remove_head, q_remove_tail` return 那個節點，給`queue_remove`這段程式碼做釋放的動作，因此若是像我先前寫的若 sp 出錯則 return NULL，就會造成記憶體 still reachable 的情況。
`queue_remove`
```c
element_t *re = NULL;
if (current && exception_setup(true))
re = pos == POS_TAIL
? q_remove_tail(current->q, removes, string_length + 1)
: q_remove_head(current->q, removes, string_length + 1);
exception_cancel();
bool is_null = re ? false : true;
if (!is_null) {
// q_remove_head and q_remove_tail are not responsible for releasing
// node
q_release_element(re);
```
`q_remove_head`
```diff
list_del(&node->list);
- if (!sp || !bufsize)
- return NULL;
- strncpy(sp, node->value, bufsize - 1);
- sp[bufsize - 1] = '\0';
+ if (sp) {
+ strncpy(sp, node->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
+ }
return node;
```
---
## 亂數 + 論文閱讀
### 利用 Fisher–Yates shuffle 演算法來實作洗牌（shuffle）
(https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法來實作洗牌（shuffle）
1. 先用 `q_size` 取得 queue 的大小 `len`。
2. 隨機從 0 ~ (len - 1) 中抽出一個數字 `random`，然後 `old` 將指向從前面數來第 random 個節點，`new` 會指向最後一個未被抽到的節點，將 `old` 和 `new` 指向的節點的值交換，再將 len - 1。
3. 隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。
新增 `q_shuffle`至`queue.c`，新增`do_shuffle`至`qtest.c`
```diff
srand(time(NULL));
int len = q_size(head);
while (len > 0) {
int random = rand() % len;
struct list_head *old = head->next;
int count = 0;
while(count < random) {
old = old->next;
count++;
}
struct list_head *new = head->prev;
+ if(new != old){
list_move(new, old);
list_move_tail(old, head);
+ }
len--;
}
```
需要特別注意`new == old`，由於我是使用 `list_move`移動指標，而 `list_move`的原始碼是先`list_del`再`list_add`，因此不加這個條件會造成 new 和 old 同時被刪掉，而下一句`list_move_tail`會無法讓 old 順利被加到串列裡，進而使 list 會有元素缺失。
```bash
/usr/bin/sha1sum: WARNING: 1 computed checksum did NOT match
[!] You are not allowed to change the header file queue.h or list.h
```
要 commit 的時候發現不能改到 queue.h，因此只在這裡展示。
透過測試程式發現我的 shuffle 非常不隨機。
進一步檢查我的程式碼，只要刪除`srand(time(NULL))`就可以達到很隨機的洗牌。因為 `driver.py`會執行`qtest`，然後會在裡面做 1000000 次的 shuffle，因此 `srand(time(NULL))`也會被執行 1000000 次，又 srand 是跟著時間戳選擇亂數表，而我認為是由於時間戳會有一個精度限制，代表在一段時間內，`rand()`產生的亂數會完全相同，進而造成上面部隨機的 shuffle，可以參考下方的小實驗程式碼，類比若將`srand`放在`q_shuffle`裡面。
:::danger
你依據什麼「理論」說話呢？工程人員說話要精準。
:::
<s>理論上來說</s> ，我若是不加`srand(time(NULL))`每一次的執行結果應該都會一樣，然而做了一些測試發現還每一次都會不一樣，因此檢查`qtest`，發現果然在 main 中已經有 `srand(os_random(getpid() ^ getppid()))`，我想這種根據 pid 而產生的亂數種的產生會比使用時間戳的還來的更 robust。
:::danger
後續數學分析，參見 [weihsinyeh](https://hackmd.io/@weihsinyeh/SJUVTnEn6)
:::
```c
int main(void)
{
int i, ranvals[5];
for (i = 0; i < 5; i++)
{
srand(time(NULL));
ranvals[i] = rand();
printf("Iteration %d ranvals [%d] = %d\n", i+1, i, ranvals[i]);
}
}
```
```base
$ ./a.out
Iteration 1 ranvals [0] = 427016034
Iteration 2 ranvals [1] = 427016034
Iteration 3 ranvals [2] = 427016034
Iteration 4 ranvals [3] = 427016034
Iteration 5 ranvals [4] = 427016034
```
```diff
- srand(time(NULL));
int len = q_size(head);
while (len > 0) {
...
}
```
> commit [c3a0fba](c3a0fba3df314ea574066375e1462f58db95c897)
### 亂數
「資訊與熵互補，資訊就是負熵」: Self-information 即每個隨機事件發生所傳達的資訊量，定義上資訊量與隨機事件發生的機率成反比，且機率爲 1 時資訊量爲 0，根據定義我們發現 log 有這樣的性質。
$$
\begin{split}
I(A+B) &= log_b (\frac{1}{P(A)P(B)}) \\
&= log_b (\frac{1}{P(A)}) + log_b (\frac{1}{P(B)}) \\
&= I(A)+I(B)
\end{split}
$$
因 $\sum_{i=1}^{n} P(x_i) = 1$，Entropy 的極大值發生在 $P(x_1)=P(x_2)=...=P(x_n)=\frac{1}{n}$ 時 $(S=log_b n)$， 此分佈即爲 uniform distribution。因此我們要設計一個亂數產生器，讓它趨近於 uniform distribution 的分佈，並與不同的 PRNG 做比較。PRN 是透過一些手段讓亂數雖然是以確定的方式產生，但卻可以在我們較小的使用範圍內不可預測，PRNG 即為 PRN 的產生器。
#### 程式實作
分析亂數工具我欲使用作業說明裡介紹的 ent ，在 `dev/` 路徑中可以看到 `random` 的存在，我嘗試用 `cat` 打開 `random` 發現這個檔案就是亂數表。同時思考若要透過 `qtest` 讓 `ent` 評估亂度要怎麼做，發現 ent 需要餵進去產生後的亂數表。
```bash
$ head -c 10M /dev/random | ent
Entropy = 7.999982 bits per byte.
Optimum compression would reduce the size
of this 10485760 byte file by 0 percent.
Chi square distribution for 10485760 samples is 255.57, and randomly
would exceed this value 47.82 percent of the times.
Arithmetic mean value of data bytes is 127.4605 (127.5 = random).
Monte Carlo value for Pi is 3.144157846 (error 0.08 percent).
Serial correlation coefficient is 0.000057 (totally uncorrelated = 0.0).
```
參閱去年同學的寫法，他在 `qtest` 中新增了自定義的 flag `-r` 可以直接產生亂數進而讓 `ent` 可以評估亂度。
`$ ./qtest -r 0 | head -c 10M | ent`
要整合進 `qtest` 還需要支援在我們所新增的 PRNG 與系統內建的 PRNG 做切換，作法大概是再新增一個檔案 `qrandom.c` 作為 `qtest` 使用 `random function` 的 entry，原先專案是寫在 `random.c`， 其中 `qrandom.c` 裡面也包刮我們做切換的 flag，會在這一個檔案決定要使用哪一種亂數產生器。
新增檔案記得要去 makefile 裡面新增 `.o`，實作 `-r` flag 需要在主程式裡面的 while 新增字元 r。
```diff
- while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
+ while ((c = getopt(argc, argv, "hv:f:l:r:")) != -1) {
```
亂數產生器的部分我預計使用 `xorshift64` `xorshift128p` `xoshiro256+` `xoshiro256**`來比較各種 PRNG 的亂度，並將這些產生器整合進 `prng.c` 中，要使用的話可以透過外層的 `qrandom.c` 做選擇。
#### xorshift64
`xorshift` 是一種很簡單快速的 PRNG，他是線性反饋移位站存器的子集(linear-feedback shift registers)，他簡單透過使用左移右移和 xor 對先前的`狀態`進行運算，`xorshift`有非常多種變形，各種位元長度的變形。`xorshift32` 會有一個 32 位元的狀態，`xorshift64` 會有一個 64 位元的狀態，`xorshift128`會有 4 個 128 位元的狀態。要產生隨機數很重要的一點是初始化 state ，且初始化不能為 0。
```c
uint64_t x = state->a;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return state->a = x;
```
#### xorshift128p
`xorshift128p` 會在最後透過加法達成非線性的轉換，相比在最後加上乘法的 `xorshift128star`，在運算時間達到非常好的提升。
```c
uint64_t t = state->x[0];
uint64_t const s = state->x[1];
state->x[0] = s;
t ^= t << 23; // a
t ^= t >> 18; // b -- Again, the shifts and the multipliers are tunable
t ^= s ^ (s >> 5); // c
state->x[1] = t;
return t + s;
```
#### xoshiro256p and xoshiro256ss
`xoshiro256p`與`xoshiro256ss`在架構上基本相同，只差在非線性項的產生。這個架構被用於 GNU Fortran compiler, LUA 等框架。
```c
uint64_t rol64(uint64_t x, int k)
{
return (x << k) | (x >> (64 - k));
}
```
:::danger
使用指定的程式碼縮排風格。
:::
```c
uint64_t xoshiro256p(struct xoshiro256p_state *state)
{
uint64_t* s = state->s;
uint64_t const result = s[0] + s[3];
// uint64_t const result = rol64(s[1] * 5, 7) * 9; // for xoshiro256ss
uint64_t const t = s[1] << 17;
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= t;
s[3] = rol64(s[3], 45);
return result;
}
```
#### Initialize
:::danger
清楚標註
:::
<s>作者</s> 提到在初始化 state 的時候，建議使用**與初始產生器完全不同且不會得到全 0 的產生器做初始化**。作者建議使用 slpitmix64 位的 seed 產生器。在實作部分需要針對每一種 PRNG 做不同狀態的初始化。
```c
uint64_t splitmix64(struct splitmix64_state *state) {
uint64_t result = (state->s += 0x9E3779B97f4A7C15);
result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
return result ^ (result >> 31);
}
```
#### 整合進 prng.c
在作業說明裡提供的 [xorshift](https://en.wikipedia.org/wiki/Xorshift) 裡面有介紹各種 generator 的形式與原始碼，如今要怎麼把不同種類不同資料型態的 generator function 整合進去 `prng.c` 裡成為首要目標。seed 的概念就是初始化，而搭配作者建議的 splitmix64 實作。首先若狀態為`s[4]`，我們需要對 4 位分別做 splitmix64 的動作。之後就可以直接呼叫產生器。
```c
void xorshift128_seed(const uint64_t seed)
{
seeded = true;
splitmix64_seed(seed);
for (int i = 0; i < 2; i++)
s[i] = splitmix64();
}
```
> commit [2331493](https://github.com/sysprog21/lab0-c/commit/23314938d39df9a28148ebed43655dd25be03046)
在我整合的 `qrandom.c` 中，`0`為系統內建的 PRNG，`1`為 `xoshiro+`，`2`為`xoshiro**`，`3`為`xorshift64`，`4`為`xorshift128+` 。會選用這幾種 PRNG 就是因為他們的 state 皆是 uint64_t 的資料型態，不同的就只有 state 個數，方便使用 splitmix64 實作初始化。
#### 實驗結果
| PRNG | 內建 | xorshift64 | xorshift128+ | xoshiro+ | xoshiro** |
| ------------------------------ | ----------- |:-----------:|:------------:| ----------- |:-----------:|
| Entropy | 7.999982 | 7.999981 | 7.999982 | 7.999983 | 7.999984 |
| Compression | 0% | 0% | 0% | 0% | 0% |
| Chi square distribution | 258.69 | 269.09 | 255.15 | 244.50 | 227.94 |
| confidence level | 42.39% | 26.04% | 48.56% | 67.08 | 88.75% |
| Arithmetic mean vlue | 127.4907 | 127.4756 | 127.5119 | 127.5036 | 127.4449 |
| Monte Carlo value | 3.143301828 | 3.142072732 | 3.141436440 | 3.142024667 | 3.143034036 |
| Serial correlation coefficient | -0.000258 | 0.000169 | 0.000142 | -0.000350 | 0.000024 |
1 個位元組的字元能夠表示的空間為 $2^8$，則最大的 entropy 為 $S = \log_2(2^8)=8$，可以看到這次測試的 5 種 PRNG 的 entropy 皆非常接近最大值 8 ，最大壓縮率皆趨近於 0。算術平均、蒙地卡羅法計算 Pi 值、及序列相關係數在 5 種 PRNG 皆相當接近，而對照參考值顯示五種 PRNG 皆足夠分散。
這一次實驗最能看出 5 種 PRNG 的效能是 Chi square distribution，信心水準離 5% 越遠，代表產生的亂數越可能符合 Uniform distribution，`xorshift64` 為最差，這是由於只有他是線性的，其他的 PRNG 都是非線性的變形。`xoshiro**`為這一次表現最好的 PRNG，信心水準來到了 88.75% ，<s>非常大的機率</s> 是常態分布，但由於 `xoshiro**`的運算時間會比`xoshiro+`來的多，因此權衡之際下`xoshiro+` 已成為相當多框架的 PRNG。
:::warning
使用精準的詞彙。
:::
在這個亂數的部分我主要學到的是如何將 PRNG 整合進現有的框架中，未來可以應用在各領域中，對於 PRNG 本身了解的僅有運算的部分，對如何影響到結果的原因<s>不太了解</s>，其中牽涉到過多統計學的知識，<s>未來有機會會對這部分做更多的了解</s>。
:::danger
不懂就說不懂，誠實面對自己，沒有「不太懂」這回事。
現在就能做的事，不要拖到明天。
:::
參考來源: [yanjiew1](https://github.com/yanjiew1/lab0-c)
---
### 論文〈Dude, is my code constant time?〉
:::danger
什麼叫做「有一定的機率」，你知道機率是多少嗎？要知道明確數值，才會說「一定」。工程人員說話要精準。
:::
儘管目前在本地端看到的分數是 100 分，但其實只要再多執行幾次，就會<s>有一定的機率</s> 變成 95 分，trace-17 會無法正確通過。這就是因為在我們專案中的 dudect，裡面缺少了 percentile 的功能，因此會造成離群值被判定為結果，而使測驗沒能通過。我們要實作的目標就是透過閱讀 dedut 專案的原始碼以及論文，修改 lab0 的原始碼已通過測驗。
#### 閱讀論文
為甚麼 constant time 如此重要? 在資訊安全領域，有一種技術可以透過加密的執行時間來恢復加密的密鑰，也就是說若存在 time leakage 則有機會會被攻擊，因此論文中介紹了一種用於檢測一段代碼是否以恆定時間運行的工具 dudect。對執行時間進行 time leakage 的檢測。
首先測量兩個不同輸入數據類別的執行時間，然後檢查這兩個時間分佈是否在統計上有所不同。
也就是所謂的`fix-vs-random leakage detection`，`fix`指的是能夠觸發特定 corner case 的 processing。之後會進到 post-processing，對資料超出 threshold 的值剃除 (Cropping)，最後進行 Welch's t-test，其中這種統計分布的問題往往有分 one-tailed 和 two-tailed，two-tailed 的意思是當檢測的結果落在兩側的尾巴的範圍裡，則 alternative hypothesis 會被接受而不是 null hypothesis。
+ NULL hypothesis $H_0$（虛無假說）: 結果發生的機率相同，遵守 Uniform distribution
+ Alternative hypothesis $H_1$（對立假說）: 結果發生的機率至少有一個不同
來源: [作業說明](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d)
Welch’s t-test
- 計算出兩個 class (fix, random) 的平均值和變異數
- Welch's t-test defines the statistic t by the following formula:
- $t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{Var_0}{N_0} + \frac{Var_1}{N_1}}}$
- $t$ 越接近 0 代表兩組數據的差異越小
- lab0 實作上只有到這裡，然後直接檢查 $t$ 是否大於 `t_threshold_moderate`
- Cropping，替除掉離群值後再次計算出 $t$
- $t$ 再次與 `t_threshold_moderate`做比較
- approximate df (degree of freedom) using the [Welch–Satterthwaite equation](https://en.wikipedia.org/wiki/Welch%E2%80%93Satterthwaite_equation)
- 由 df 我們可以得到相應的 t-distribution 如上圖的鐘型曲線
- 圖上的藍白交界處分別為 +-t
- 把藍色部份積分起來可以得到 p value 若小於特定值 (通常 0.05 因為 95% 信心水準) ，我們可以說兩組數據有統計上的顯著差異
#### dudect 實作
專案中缺少的程式碼即為 cropping 的部分，下方程式碼為 dudect 專案中的原始碼，也是我們缺少的功能。因此只需針對 lab0 的資料型態定義改寫即可。其中 percentile 會將 `which` 也就是百分比，在已排列的串列 `a_sorted`找到對應的地址。
```c
static int64_t percentile(int64_t *a_sorted, double which, size_t size)
{
size_t array_position = (size_t) ((double) size * (double) which);
assert(array_position < size);
return a_sorted[array_position];
}
```
主要剔除極端值的部分是 `prepare_percentiles` 的部分，透過只取 $$1 - {0.5}^{10 \cdot \frac{i+1}{N}}$$ 以下的部份，以達到目的。
```c
static void prepare_percentiles(int64_t *exec_times, int64_t *percentiles)
{
qsort(exec_times, DUDECT_NUMBER_PERCENTILES, sizeof(int64_t),
(int (*)(const void *, const void *)) cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
percentiles[i] = percentile(
exec_times,
1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)),
DUDECT_NUMBER_PERCENTILES);
}
}
```
透過將 dudect 完整程式碼整合進 lab0 即可在 github 上面看到卡比。
```c
bool first_time = percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
if (first_time) {
prepare_percentiles(exec_times, percentiles);
} else {
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();
}
```
> commit [37fe649](37fe6495dba0dca82d290dd3f3f3e7368fa36194)
---
## Linux 核心的鏈結串列排序
1. Top-down mergesort
* 有最少的 average case、worst case 的 comparison 次數。
* 需要使用遞迴或是額外空間作為 user stack。
2. Bottom-up mergesort
* 需要最多的 comparison 次數。
3. Queue-mergesort
* 特別適合用於鏈結串列的排序。
* queue-mergesort comparison 的次數少於 bottom-up mergesort，略高於 top-down mergesort。
先前實作的 merge sort 是第一種 top-down 的方式，因為使用遞迴的方式，所以需要針對 partition 有額外的堆疊空間，而 list_sort 採用 Bottom-up mergesort。
透過在`q_test.c`新增`do_list_sort`整合進 list_sort。
```bash
l = [3 2 1]
cmd> list_sort
l = [1 2 3]
```
### list sort 原始碼筆記
`__attribute__((nonnull(2, 3, 4)))` 這一類的語法出現在 `list_sort.c`原始碼中，這使一種GNU C extension 所提供的的一個屬性，用於告訴編譯器函數的某些參數不能為空。
#### merge
註解可以得知，為了降低維護雙向串列的成本，list 在 function 中會變成 null-terminated, no reserved or sentinel head node, `prev` links not maintained。簡單來說就是讓雙向串列變成單向串列以為降低成本。
#### merge_final
從兩個已排序的列表 `a` 和 `b` 中，按照 `cmp` 的規則逐個選擇元素，將它們連接成一個新的有序列表。如果 `a` 和 `b` 中的某一個列表先<s>遍歷</s> 完畢，則將剩餘的元素直接連接到新列表的末尾。
最後，將剩餘的列表連接到新列表的末尾，並恢復雙向<s>鏈表</s> 的標準結構，使得新列表成為一個循環的雙向<s>鏈表</s> 。
:::danger
linked list 為「鏈結串列」，可簡稱為 list (串列)，但不可稱「链表 (鏈表)」，該資料結構不具備任何「表」的寓意，參見中華民國教育部重編國語辭典「[表](https://dict.revised.moe.edu.tw/dictView.jsp?ID=457)」，指「分格或分項以列記事物的文件」，而 linked list 作為資料結構，全然沒有「分格」和「分項」的意涵。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
#### list_sort
初始化過後，會將 head 轉換到 null-terminated singly-linked list以節省維護成本。
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
接下來會進到最主要的 merge 過程，使用 `tail` 來存取指向 `pending` 的指標。爾後會進入到 for loop，為下面 if statement 做位移的操作，也就是說透過這一個 for loop 我們可以知道當 `bits` 為 `xxxppp` 時不會做 merge 的動作，這邊 `xxx`為任意長度的`全 0 組合`，`ppp` 為任意長度`全 1 的組合`，也就是 2 的冪 - 1，有幾個 1 就會讓 `tail`往前幾次。
```c
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
以上是由 for loop 搭配 if statement 歸納出來的規則，我們可以透過更直觀的觀點詮釋，簡單來說，就是「進位幾次就要 merge 幾次」，最一開始的 `0000->0001`，目前 pending 的節點沒有東西，在 do-while 最後部分可以想成加了一個節點進來，因此下一次 pending 上的節點為 1，下一次不需要 merge，再來 `0001->0010` do-while 最後部分 pending 上的節點為 `1<-1`，因此下一次需要 merge。下一次的 `0010->0011`，這一部分因為目前 pending 節點為 `1<-1`，因此會 merge 變成 `2`，在 do-while 最後又會加節點進來變成`2<-1`，所以下一次不用 merge。`0011->0100`，這一次不用 merge 因此 pending 變成 `2<-1<-1`，又有兩個 1 所以下一次要 merge。`0100->0101` merge 會變成 `2<-2`，do-while 後面會加一個節進來變成`2<-2<-1`，所以下一次要 merge。透過以上例子講解，可以觀察到 merge 與否與進位的微妙關係，幫助消化吸收。
| count 變化 | count 二進位 | merge | pending 上的節點 |
| ----------- | ------------------- | ----------- | ----------------------------------------- |
| 0 $\to$ 1 | 0000 $\to$ 0001 | no（$2^0$） | 1 |
| 1 $\to$ 2 | 0001 $\to$ 0010 | no（$2^1$） | 1 $\gets$ 1 |
| 2 $\to$ 3 | 0010 $\to$ 001==1== | yes | (2) $\gets$ 1 |
| 3 $\to$ 4 | 0011 $\to$ 0100 | no（$2^2$） | 2 $\gets$ 1 $\gets$ 1 |
| 4 $\to$ 5 | 0100 $\to$ 010==1== | yes | 2 $\gets$ (2) $\gets$ 1 |
| 5 $\to$ 6 | 0101 $\to$ 01==1==0 | yes | (4) $\gets$ 1 $\gets$ 1 |
| 6 $\to$ 7 | 0110 $\to$ 011==1== | yes | 4 $\gets$ (2) $\gets$ 1 |
| 7 $\to$ 8 | 0111 $\to$ 1000 | no（$2^3$） | 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 |
| 8 $\to$ 9 | 1000 $\to$ 100==1== | yes | 4 $\gets$ 2 $\gets$ (2) $\gets$ 1 |
| 9 $\to$ 10 | 1001 $\to$ 10==1==0 | yes | 4 $\gets$ (4) $\gets$ 1 $\gets$ 1 |
| 10 $\to$ 11 | 1010 $\to$ 101==1== | yes | 4 $\gets$ 4 $\gets$ (2) $\gets$ 1 |
| 11 $\to$ 12 | 1011 $\to$ 1==1==00 | yes | (8) $\gets$ 2 $\gets$ 1 $\gets$ 1 |
| 12 $\to$ 13 | 1100 $\to$ 110==1== | yes | 8 $\gets$ 2 $\gets$ (2) $\gets$ 1 |
| 13 $\to$ 14 | 1101 $\to$ 11==1==0 | yes | 8 $\gets$ (4) $\gets$ 1 $\gets$ 1 |
| 14 $\to$ 15 | 1110 $\to$ 111==1== | yes | 8 $\gets$ 4 $\gets$ (2) $\gets$ 1 |
| 15 $\to$ 16 | 1111 $\to$ 10000 | no（$2^4$） | 8 $\gets$ 4 $\gets$ 2 $\gets$ 1 $\gets$ 1 |
看到下面的 for loop，這邊除了可以幫助判斷 bits 是否需要 merge 外，還有一個非常重要的功能，`串聯已 merge 過的串列`，一般來說，`tail` 會指向 `pending`，所以說要 merge 的時候，最初只會 merge `pending` 和 `pending 的前一個`，然而我們可以透過這個 for loop 來判斷先前有沒有 `已經 merge 過的串列`，並透過 `tail = &(*tail)->prev;` 來達成 merge 先前 merge 過的串列。
我們以圖解方式解釋，考慮原有串列`6 5 4 3 2 1`，如下圖。
```graphviz
digraph ele_list {
rankdir=LR
node[shape=record]
head [label="head|{<left>prev|<right>next}", style="bold"]
node6 [label="6|{<left>prev|<right>next}", style="bold"]
node5 [label="5|{<left>prev|<right>next}", style="bold"]
node4 [label="4|{<left>prev|<right>next}", style="bold"]
node3 [label="3|{<left>prev|<right>next}", style="bold"]
node2 [label="2|{<left>prev|<right>next}", style="bold"]
node1 [label="1|{<left>prev|<right>next}", style="bold"]
list [label="list", style="normal", color="white"]
head:right:e -> node6:w
node6:left:w -> head:e
node6:right:e -> node5:w
node5:left:w -> node6:e
node5:right:e -> node4:w
node4:left:w -> node5:e
node4:right:e -> node3:w
node3:left:w -> node4:e
node3:right:e -> node2:w
node2:left:w -> node3:e
node2:right:e -> node1:w
node1:left:w -> node2:e
list -> node6:n
}
```
當 `count = 0101`時，會長得像下面這張圖，其中 `3 4` `5 6` 已在先前 merge 好。
```graphviz
digraph G {
rankdir=LR;
node[shape=none]
pd [label=pending]
tl [label = "tail"]
subgraph n5 {
style=filled;
color=lightgrey;
node [shape=record color = blue];
hn5 [label="<head>5 | {<prev>prev | <next>next}"];
}
node [shape=record color = blue];
hn6 [label="<head>6 | {<prev>prev | <next>next}"];
subgraph n3 {
style=filled;
color=lightgrey;
node [shape=record color = red];
hn3 [label="<head>3 | {<prev>prev | <next>next}"];
}
subgraph n4 {
style=filled;
color=lightgrey;
node [shape=record color = red];
hn4 [label="<head>4 | {<prev>prev | <next>next}"];
}
subgraph n1 {
style=filled;
color=lightgrey;
node [shape=record color = black];
hn1 [label="<head>1 | {<prev>prev | <next>next}"];
}
subgraph n2 {
style=filled;
color=lightgrey;
node [shape=record color = black];
hn2 [label="<head>2 | {<prev>prev | <next>next}"];
}
hn5:next->hn6:head[color = blue]
hn3:prev->hn5:head[color = red]
hn3:next->hn4:head[color = red]
hn2:prev->hn3:head
hn1:prev->hn2:head
pd->hn2
tl->pd
}
```
為做圖方便，將整張圖左右反過來，這時我們需要進行 merge，經過 for loop 可以發現，要將`tail`往`prev`方向移動，一開始在看原始碼不懂這個的用意，畫圖之後發現原來就是為了處理大於 1 的串列，我們也可以透過上表得知目前是要從`1->2->2`合併成`1->4`，因此才須往 prev 方向移動，此時的 `a` 為 `3` ，`b` 為 `a->prev` `5`，如此一來就可以將 `1->2->2`合併成`1->4`。
```graphviz
digraph G {
rankdir=LR;
node[shape=none]
pd [label=pending]
tl [label = "*tail, a"]
b [label = "b"]
subgraph n5 {
style=filled;
color=lightgrey;
node [shape=record color = blue];
hn5 [label="<head>5 | {<prev>prev | <next>next}"];
}
node [shape=record color = blue];
hn6 [label="<head>6 | {<prev>prev | <next>next}"];
subgraph n3 {
style=filled;
color=lightgrey;
node [shape=record color = red];
hn3 [label="<head>3 | {<prev>prev | <next>next}"];
}
subgraph n4 {
style=filled;
color=lightgrey;
node [shape=record color = red];
hn4 [label="<head>4 | {<prev>prev | <next>next}"];
}
subgraph n1 {
style=filled;
color=lightgrey;
node [shape=record color = black];
hn1 [label="<head>1 | {<prev>prev | <next>next}"];
}
subgraph n2 {
style=filled;
color=lightgrey;
node [shape=record color = black];
hn2 [label="<head>2 | {<prev>prev | <next>next}"];
}
hn5:next->hn6:head[color = blue]
hn3:prev->hn5:head[color = red]
hn3:next->hn4:head[color = red]
hn2:prev->hn3:head
hn1:prev->hn2:head
pd->hn2
tl->hn3:n
b->hn5:n
}
```
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
下方的 if statement 可以透過對 `bits` 的檢查決定要不要做 merge，值得注意的是`likely()` 這一個 MACRO，`!!(x)` 是為了讓 value 只會有 1 或 0，`__builtin_expect()`則可以幫助 compiler 做 branch prediction 最佳化。
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
接下來看到 list_sort 的最後部分，在 `list` 為 `NULL` 時，會有各種不同的狀況，如上面表中的 pending 上的節點，因此我們需要再一次進行 merge，將剩餘的串列 merge 起來，但最後因為`next`會指向`list`的前兩個，因此最後還是會剩下一些還沒合併的串列，最後再使用 merge_final 合併完成排序。
```c
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
```
### 效能分析
#### Experiment Setup
在這個實驗中，我會對三種不同的排序方法對四種不同的資料作分析，每一個資料的 sample 皆為 10000 筆。
##### Data set
1. 隨機: 會在 0 - 9999 中的資料隨機產生亂數，有可能會有相同的數字。
3. 正序: 產生一個 0 - 9999 的資料。
4. 倒序: 產生一個 9999 - 0 的資料。
5. 部分排序: 會使用 0 - 9999 的資料作處理，產生部分排序的狀況。
部分排序我的靈感來自 shuffle，總共會有兩個隨機數，第一個決定從哪裡開始，第二個決定這個 run 有幾個，然後會有一個 flag 來決定 reverse 與否，如此可以造出有升序有降序，且各個 run 也是打亂的狀態，程式碼如下，這個資料集是為了 Timsort 所設計。
```c
int len = SAMPLES/100;
while(len > 0) {
int count = 0;
int k = rand() % SAMPLES;
struct list_head *old = head->next;
while (count < k ) {
old = old->next;
count++;
}
k = rand() % (SAMPLES/100);
count = 0;
struct list_head *safe = old->next;
struct list_head *tmp = head->prev;
while (count < k && safe != head && safe->prev != tmp) {
if(flag)
list_move_tail(safe->prev, head);
else
list_move(safe->prev, tmp);
count++;
safe = safe->next;
}
flag = !flag;
len--;
}
}
```
我會使用三種不同的演算法做分析，分別是 merge sort, list sort 和 Tim sort。
我會從三個不同面向分析效能，首先最直觀的 instructions 和 cycles，這兩個效能指標最直接影響到了速度，越多的 cycles 會造成更久的執行時間，我們也可以透過這兩個參數計算 CPI。此外會針對 cache 的訪問作分析，分析哪一種排序演算法會對 cache 最友善，和有最佳的 localibility。還會對 branch prediction 做分析，不同的演算法所編譯出的組語會不一樣，對效能也會有一定程度的影響。
##### list sort
| | 隨機 | 正序 | 倒序 | 部分排序 |
|:------------------- |:------------ |:----------- |:---------- |:------------ |
| Instructions | 5924775 | 4092835 | 4059298 | 6521430 |
| Cycles | 5079702 | 2049659 | 1984403 | 5750144 |
| Cache-refrence | 29991 | 25363 | 25483 | 29685 |
| Cache-misses | 6203(20.68%) | 4033(15.9%) | 4078(16%) | 6051(20.38%) |
| branch-instrucitons | 1414001 | 933682 | 880863 | 1542902 |
| branch-misses | 76199(5.39%) | 7943(0.87%) | 7887(0.9%) | 10750(0.7%) |
##### Tim sort
| | 隨機 | 正序 | 倒序 | 部分排序 |
|:------------------- |:------------ |:------------ |:------------ |:------------ |
| Instructions | 6301376 | 2312742 | 2340639 | 5129143 |
| Cycles | 5138024 | 1580590 | 1544651 | 5212319 |
| Cache-refrence | 30508 | 25426 | 25009 | 29634 |
| Cache-misses | 6521(21.37%) | 3681(14.48%) | 3885(15.53%) | 6385(21.55%) |
| branch-instrucitons | 1567024 | 452424 | 451975 | 1188166 |
| branch-misses | 77210(4.93%) | 6794(1.5%) | 6637(1.47%) | 8781(0.7%) |
##### merge sort
| | 隨機 | 正序 | 倒序 | 部分排序 |
|:------------------- |:------------ |:------------ |:------------ |:------------ |
| Instructions | 7544668 | 6919207 | 6912340 | 9038839 |
| Cycles | 4042914 | 3592088 | 3570198 | 7233763 |
| Cache-refrence | 28189 | 28403 | 26905 | 31130 |
| Cache-misses | 5530(19.62%) | 5308(18.68%) | 4961(18.44%) | 7399(23.77%) |
| branch-instrucitons | 1530398 | 1370039 | 1368813 | 1895667 |
| branch-misses | 9442(0.62%) | 9174(0.67%) | 8910(0.65%) | 9577(0.51%) |
先從 list sort 開始橫向比較不同資料集的狀況，於 cycle 方面，正序和倒序表現皆為最好，正序我能夠理解是 best case，但是倒序我覺得非常不合理，理論上來說倒序會比正序比較更多次進而造成效能較差。隨機排序出乎意料的不是最差的狀況，最差的情況是部分排序。
merge sort 的 cycle 結果也與 list sort 差不多，最差情況都是部分排序，而正序倒序表現差不多。
Timsort 的 cycle 結果同樣正序倒序差不多，但部分排序的表現跟隨機資料差不多，這是因為 Timsort 就是為了有 run 的情況設計，因此有因此有這種結果非常合理。
目前想到會造成部分牌序為最差情況我認為是因為在效能分析一起把建立資料也分析進來了，每一種情況在建立資料的時候所用到的函式都不進相同，跑的迴圈次數也不相同，因此我認為這是造成部分排序比隨機資料效能表現較差的原因。隨機資料僅僅用了一個 while 走訪整個串列，但部分牌序會依照骰到的隨機次數走訪。
接下來進行縱向比較，我們可以比較三種不同演算法在同一種狀況下的效能，以隨機資料來看 list sort 的表現最好，再來是 Tim sort，最後是 merge sort，merge sort 會先將串列拆開再組裝起來，因此會使效能最差。
以升序或降序來看，merge sort 由於是 top-down merge，因此效果最差，而 Timsort 表現最好，這是因為其實升序降序廣義上來講也符合 Timsort 的使用場景，可以把已排序好的當作 run 來看待。
部分排序就不用說了，Tim sort就是為了此而生，因此表現最好。
整體來說，實驗結果大致符合預期，然而有些疑點尚未釐清，像是正序表現以及倒序表現，還有部分排序是否真的是因為建立資料而造成效能最差，這些都值得在設計實驗分析。
:::danger
疑點: 正序表現與倒序差不多、最差情況為部分排序
:::
:::warning
TODO: 效能分析隔離建立資料並比較
:::
> commit [7233510](https://github.com/Shawn531/lab0-c/commit/7233510368f727b89303a475585876134eee46f2)
#### 疑難雜症
目前在 make 時沒有遇到問題，但在 git 的時候會遇到 Cppcheck 靜態檢查的錯誤，有查到 [jasperlin1996](https://hackmd.io/@jasperlin1996/linux2022-lab0) 也遇到這個問題，
> 因為 list.h 中 `container_of` 的實作中，有一行是 `__typeof__(((type *) 0)->member)` 而 `(type *) 0 `的確是 null pointer。不過這邊的用法是為了取得 member 的 type。
先前在實作 queue.c 也有使用到這個巨集，但並沒有問題，這部分尚未解決，先將內容註解推上 github。
```bash
sort_test.c:67:15: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
int res = list_entry(a, element_t, list)->val -
^
sort_test.c:68:15: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
list_entry(b, element_t, list)->val;
^
```
---
## 定點數
### fixed-point power int
#### fixed-point log2
〈[A Fast Binary Logarithm Algorithm [DSP Tips & Tricks]](https://ieeexplore.ieee.org/document/5562652)〉介紹了一種快速的 binary logarithm 演算法，特別適用於 fixed-point 的運算場景。
考慮
$\begin{gather*}
y = \log_2{x} \\
x=2^y
\end{gather*}$
首先假定 $1\leq x\leq 2$，因此 $0\leq y\leq 1$，我們可以將 $y$ 寫成二進位的表示方法:
$$
y = y_1\cdot 2^{-1} + y_2\cdot 2^{-2}+y_3\cdot 2^{-3}+y_4\cdot 2^{-4}+ \dots
$$
將式子整理一下
$$
y = 2^{-1}(y_1+2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+ \dots))))
$$
將 $y$ 帶入 $x=2^y$ 可以得到
$$
x = 2^{2^{-1}(y_1+2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+ \dots))))}
$$
這時將左右平方，接下來的流程有點類似於二分逼近法的概念。
$$
x^2 = 2^{y_1}\cdot2^{2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+ \dots)))}
$$
若 $y_1 = 1$，會造成 $x^2 \geq 2$，也就是說小數部位為 1，式子會像下面這樣。
$$
x^2 = 2^1\cdot2^{2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+ \dots)))}
$$
若 $y_1 = 0$，會造成 $x^2 < 2$，也就是說小數部位為 0，式子會像下面這樣。
$$
x^2 = 1\cdot2^{2^{-1}(y_2+2^{-1}(y_3+2^{-1}(y_4+ \dots)))}
$$
接下來我們可以對這一串式子繼續做運算，直到我們的精度，需要注意的是若是當次 $x^2 \geq 2$，那下一次我們需要將 `x_square = x_square >> 1`，再將 `x_square ^ 2` 然後繼續判斷。
可以觀察到運算所會用到的工具基本上就是 shift 和平方，shift 不用說了就是硬體開銷很小的一種運算，而這邊的平方可以採用 [M03: ttt](https://hackmd.io/@sysprog/linux2024-ttt) 中的定點數 power `fixed_power_int` 實作。
值得注意的是這個演算法的前提是將 $x$ 限制在 $1\leq x\leq 2$，這是因為我們可以很簡單的透過最高位的 1 來判斷 $y$ 的整數值為多少，舉例來說 $y = log_2(13)$:
$\begin{gather*}
(13)_{10}=(1101)_2 \\
13 = 1\cdot 2^3 \cdot 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0 \\
13 = 2^3 \cdot\frac{ 1\cdot 2^3 \cdot 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0}{2^3} \\
log_2(13) = log_2(2^3) + log(\frac{ 1\cdot 2^3 \cdot 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0}{2^3})
\end{gather*}$
可以發現 $x=\frac{ 1\cdot 2^3 \cdot 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0}{2^3}$ 這一項可以使用 shift 很輕鬆的達到 $1\leq x\leq 2$。
在這一個演算法中，我們可以指定 `precision`，精確度主要是差別在這一個參數。首先我們透過下方程式碼透過 shift 將範圍控制在 1 到 2 之間。
```c
while (x < 1U << precision) {
x <<= 1;
y -= 1U << precision;
}
while (x >= 2U << precision) {
x >>= 1;
y += 1U << precision;
}
```
之後就可以針對上述演算法做判斷。
```c
uint64_t z = x;
for (size_t i = 0; i < precision; i++) {
z = z * z >> precision;
if (z >= 2U << precision) {
z >>= 1;
y += b;
}
b >>= 1;
}
return y;
}
```
> commit [419c5fb](https://github.com/sysprog21/lab0-c/commit/419c5fb01460f07c69f25a4bb3984943f0247fbd)
#### Comparision
在這個實驗中，我會指定不同的 `precision`，並以 `math.h` 中的 `log2` 做基準比較。
##### 精確度
`precision = 8`
可以看到上圖，發現 `precision = 8` 的結果與 `log2()` 非常接近。
`precision = 4`
可以看到上圖，發現 `precision = 4` 的結果與 `log2()` 非常接近，但開始偏離了 `log2()` 的精度，有鋸齒狀產生，這是因為我們只做到小數點後 4 位，因此會有這個狀況發生。
`precision = 1`
`precision = 1` 的鋸齒狀又更明顯的，他的結果明顯是一階一階的，因為`precision = 1`，因此他的精度為 0.5。
##### 誤差
看到這個誤差分析又可以更明顯的看出 precision 越高誤差會越小。
| | float | p=16 | p=8 | p=4 | p=1 |
|:-------------- |:----------- |:------------ |:------------ |:------------ |:------------ |
| Instructions | 2293358 | 3612759 | 2728307 | 2452278 | 2273176 |
| Cycles | 1298533 | 3248741 | 1659413 | 1333207 | 1235387 |
| Cache-refrence | 18430 | 19685 | 18592 | 17958 | 1756 |
| Cache-misses | 1670(9.06%) | 3014(13.32%) | 2062(11.09%) | 1833(10.21%) | 17497(9.24%) |
使用 perf 統計完 `precision` 的數據大吃一驚，怎麼使用定點數運算的效能比使用 float 還差，預計將 `log2()` 的原始碼翻出來看並分析原因，評估我的定點數 log2 運算並修改。
> 定點數本來就不是為了超越浮點數運算速度而存在，本例的 log2 在 FPU 是一道指令，關鍵是你預期用多少位元來表達數值、有效資料範圍又如何。 :notes: jserv
:::warning
TODO: log2_lshift16、修改 log2 運算
:::
---
## Tic-Tac-Toe
### Monte Carlo Tree Search
蒙地卡羅搜尋是一種常用於人工智慧和計算機遊戲的搜尋演算法。該演算法的核心思想是通過大量的隨機模擬來評估每個可能的行動，從而選擇最佳的行動。它首先將問題轉換為一個狀態空間，然後通過模擬不同行動的結果來評估它們的價值。在每次模擬中，它隨機選擇行動，並根據結果對行動進行評估。最後它會根據這些評估結果來選擇最優的行動。這種方法的優點在於它的隨機性和探索能力，通過模擬大量的隨機樣本，它能夠有效地探索搜索空間，找到潛在的最佳解決方案。這使得它在許多領域都有廣泛的應用，如棋類遊戲、機器人路徑規劃等。
主要的步驟有三個，分別是 select, expand, rollout, backpropagate。簡單來說會透過分數指標去選擇節點，之後會根據選到的節點進行 expand，然後選擇一條隨機路徑進行 rollout，最終透過 backpropagate 來標記結果，最終我們就可以透過統計結果來做出正確的選擇。
- [ ] Select
在 select 步驟裡所謂的分數就是 Upper Confidence Bound(UCB)
$$
UCB = \frac{w_i}{n_i}\times C\sqrt{\frac{ln(N_i)}{n_i}}
$$
$w_i$ 是有經過此節點的勝利次數，$n_i$ 是選擇此節點的總數，$N_i$ 為該節點的 parent 被選擇的總次數。我們可以將這個式子拆成兩部分來看，$\frac{w_i}{n_i}$ 我們可以將他視為 `勝率取向`，我們可以將 $C\sqrt{\frac{ln(N_i)}{n_i}}$ 看作 `探索取向`。透過控制這兩項，我們可以在探索與勝利達到平衡。
可以看到下圖的 12/21，12 代表勝利次數，21 代表總次數。選取節點我們是透過 UCB 計算出。
```graphviz
digraph Tree {
node [shape=circle];
A [label="12/21"]
B [label="7/10"]
C [label="2/4"]
D [label="5/6"]
E [label="2/3"]
F [label="3/3"]
G [label="5/8"]
H [label="1/2"]
I [label="2/3"]
J [label="2/3"]
K [label="0/3"]
A -> B;
A -> G[dir=none];
A -> K[dir=none];
B -> C[dir=none];
B -> D;
D -> E[dir=none];
D -> F;
G -> H[dir=none];
G -> I[dir=none];
G -> J[dir=none];
}
```
- [ ] Expand
Expand 指的是從目前節點開始，生成該節點的所有可能的後繼節點。這意味著在搜索過程中，通過考慮目前節點的所有可能行動或狀態轉移，擴展搜索空間，以便在後續的搜索中繼續探索更多的解決方案。
```graphviz
digraph Tree {
node [shape=circle];
A [label="12/21"]
B [label="7/10"]
C [label="2/4"]
D [label="5/6"]
E [label="2/3"]
F [label="3/3"]
G [label="5/8"]
H [label="1/2"]
I [label="2/3"]
J [label="2/3"]
K [label="0/3"]
L [label="0/0"]
A -> B[dir=none];
A -> G[dir=none];
A -> K[dir=none];
B -> C[dir=none];
B -> D[dir=none];
D -> E[dir=none];
D -> F[dir=none];
G -> H[dir=none];
G -> I[dir=none];
G -> J[dir=none];
F -> L;
}
```
- [ ] Rollout
Rollout 則用於模擬從目前狀態開始的一系列隨機行動，以評估目前狀態的價值。這種模擬過程不考慮複雜的搜尋演算法或啟發式，而是簡單地執行隨機動作序列，並根據達到的終止狀態來評估目前狀態的優劣。上一步驟選擇新 expand 後，會隨機選擇一條路徑走到底。
```graphviz
digraph Tree {
node [shape=circle];
A [label="12/21"]
B [label="7/10"]
C [label="2/4"]
D [label="5/6"]
E [label="2/3"]
F [label="3/3"]
G [label="5/8"]
H [label="1/2"]
I [label="2/3"]
J [label="2/3"]
K [label="0/3"]
L [label="0/0"]
win [label="win" color=transparent]
A -> B[dir=none];
A -> G[dir=none];
A -> K[dir=none];
B -> C[dir=none];
B -> D[dir=none];
D -> E[dir=none];
D -> F[dir=none];
G -> H[dir=none];
G -> I[dir=none];
G -> J[dir=none];
F -> L[dir=none];
L -> win;
}
```
- [ ] Backpropagate
最後會透過得到的 leaf 來判斷結果是好是壞，將評估的結果回溯到初始狀態，並用於更新目前狀態在搜索樹中的價值估計。
```graphviz
digraph Tree {
node [shape=circle];
A [label="13/22"]
B [label="8/11"]
C [label="2/4"]
D [label="6/7"]
E [label="2/3"]
F [label="4/4"]
G [label="5/8"]
H [label="1/2"]
I [label="2/3"]
J [label="2/3"]
K [label="0/3"]
L [label="1/1"]
A -> B[dir=none color="white"];
B -> A;
A -> G[dir=none];
A -> K[dir=none];
B -> C[dir=none];
B -> D[dir=none color="white"];
D -> B;
D -> E[dir=none];
D -> F[dir=none color="white"];
F -> D;
G -> H[dir=none];
G -> I[dir=none];
G -> J[dir=none];
F -> L[dir=none color="white"];
L -> F;
}
```
:::warning
TODO: 整合進 lab0-c、改 fixed-point
:::
Sign in with Wallet
Connect another wallet