# 2025q1 Homework1 (lab0)
contributed by < `LinMarc1210` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ 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: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-1260P
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
Stepping: 3
CPU(s) scaling MHz: 21%
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 4992.00
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge m
ca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 s
s ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc
art arch_perfmon pebs bts rep_good nopl xtopology nons
top_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq
dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma c
x16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_de
adline_timer aes xsave avx f16c rdrand lahf_lm abm 3dn
owprefetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_e
nhanced tpr_shadow flexpriority ept vpid ept_ad fsgsba
se tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed
adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsav
ec xgetbv1 xsaves split_lock_detect user_shstk avx_vnn
i dtherm ida arat pln pts hwp hwp_notify hwp_act_windo
w hwp_epp hwp_pkg_req hfi vnmi umip pku ospke waitpkg
gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_c
lear serialize arch_lbr ibt flush_l1d arch_capabilitie
s
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 448 KiB (12 instances)
L1i: 640 KiB (12 instances)
L2: 9 MiB (6 instances)
L3: 18 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerabilities:
Gather data sampling: Not affected
Itlb multihit: Not affected
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Not affected
Reg file data sampling: Mitigation; Clear Register File
Retbleed: Not affected
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prct
l
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointe
r sanitization
Spectre v2: Mitigation; Enhanced / Automatic IBRS; IBPB conditiona
l; RSB filling; PBRSB-eIBRS SW sequence; BHI BHI_DIS_S
Srbds: Not affected
Tsx async abort: Not affected
```
## 動手前的學習
### 學習 list.h
- `struct list_head`: 定義雙向鏈結串列的結構，包含指向下一個節點的 `*next` 以及指向上一個節點的 `*prev`
- `container_of(ptr, type, member)`: 得到 `ptr` 在 `type` 這個結構裡面的記憶體位置
- `INIT_LIST_HEAD`: 初始化節點 `head` ， `next` 和 `prev` 皆指向自己
- `list_add`: 將給定的節點加到 `head` 的 `next`
- `list_add_tail`: 將給定的節點加到 `head` 的 `previous`
- `list_del`: 從鏈結串列中移除指定的節點
- `list_del_init`: 從鏈結串列中移除指定的節點，並且重新初始化成 `next` 和 `prev` 都指向自己的節點
- `list_empty`: 檢查 `head` 的 `next` 是否指向自己，如果是，則代表鏈結串列為空，即鏈結串列中除了 `head` 沒有其他節點
- `list_is_singular`: 檢查鏈結串列是否為空，且 `head->prev` 和 `head->next` 是否指向同一個節點，如果都是，則鏈結串列為 singular
- `list_splice`: 將給定的鏈結串列所有節點加到 `head` 的 `next` ， `head->next` 會指向新加入的鏈結串列的第一個節點， `head->prev` 則不變
- `list_splice_tail`: 將給定的鏈結串列所有節點加到 `head` 的 `prev` ， `head->prev` 會指向新加入的鏈結串列的最後一個節點， `head->next` 則不變
- `list_splice_init`: 做 `list_splice` 並且初始化 `list` 為自己指向自己的節點，避免 `list` 仍指向原本的鏈結串列
- `list_splice_tail_init`: 做 `list_splice_tail` 並且初始化 `list` 為自己指向自己的節點，避免 `list` 仍指向原本的鏈結串列
- `list_cut_position`: 將從 `head_from->next` 到包含 `node` 的所有節點都接給 `head_to` ， `head_to` 則不再指向原本 `head_to` 所指向的鏈結串列
- `list_move`: 用 `list_del` 移除指定節點後再加入 `head` 所指向的鏈結串列的頭
- `list_move_tail`: 用 `list_del` 移除指定節點後再加入 `head` 所指向的鏈結串列的尾
- `list_entry`: 定義為 `container_of(node, type, member)`
- `list_first_entry`: 定義為 `list_entry((head)->next, type, member)` ，得到 `head->next` ，即鏈結串列中第一個節點在 `type` 裡面的記憶體位置，回傳一個指向 `type` 結構的指標
- `list_last_entry`: 定義為 `list_entry((head)->next, type, member)` ，得到 `head->prev` ，即鏈結串列最後一個節點在 `type` 裡面的記憶體位置，回傳一個指向 `type` 結構的指標
- `list_for_each`: 從 `head->next` 開始走訪所有節點
- `list_for_each_entry`: 從包含 `head->next` 的結構開始走訪所有包含此鏈結串列的結構
- `list_for_each_safe`: 從 `head->next` 開始走訪所有節點，並且允許移除節點，因為會同時走訪當前節點與當前節點的 `next` 所指向的節點
- `list_for_each_entry_safe`: 從 `head->next` 開始走訪所有所有包含此鏈結串列的結構，並且允許移除結構，因為會同時走訪當前結夠與當前結構裡面節點的 `next` 所指向的結構
### 學習 queue.h
#### struct
- `element_t`: 佇列裡面的元素，結構包含字元指標 `value` 和 `"list.h"` 內建的 `list_head` ，即雙向鏈結串列的節點
- `queue_contex_t`: 包含指向佇列頭部的 `*q` ，用來將所有佇列的頭部接起來的 `chain` ，佇列長度 `size` 與佇列編號 `id`
#### 要實做的 function
- `q_new`: 建一個空佇列，指向頭部的 `head` 必須要 `prev` 和 `next` 都指向自己
- `q_free`: 清空佇列所有元素，包含指向頭部的 `head`
- `q_insert_head`: 分配記憶體給新插入在佇列頭部的元素，並且把 `*s` 的值存進新元素
- `q_insert_tail`: 分配記憶體給新插入在佇列尾端的元素，並且把 `*s` 的值存進新元素
- `q_remove_head`: 取消第一個元素與佇列的鏈結
- `q_remove_tail`: 取消最後一個元素與佇列的鏈結
- `q_release_element`: 釋放 `element_t` 元素的記憶體
- `q_size`: 回傳佇列長度
- `q_delete_mid`: 刪除中間元素，刪除是連這個元素的記憶體也要被釋放掉，而中間元素是佇列的 $⌊n / 2⌋^{th}$ 個
- `q_delete_dup`: 刪除所有 `*s` 相同的元素，只留一個
- `q_swap`: 每兩個相鄰的元素兩兩交換，若為奇數個元素則最後一個不用交換
- `q_reverse`: 將所有元素順序反轉，且不該額外分配或釋放記憶體
- `q_reverseK`: 將佇列中前 k 個元素順序反轉
- `q_sort`: 將佇列元素排成升序或降序，根據 `descend` 決定
- `q_ascend`: 將佇列中指定元素的後面所有比他小的元素，從佇列中移除，並且釋放被移除元素的記憶體
- `q_descend`: 將佇列中指定元素的後面所有比他大的元素，從佇列中移除，並且釋放被移除元素的記憶體
- `q_merge`: 將所有佇列合併成一個已排序的佇列，根據 `descend` 決定升序或降序
## 修改 queue.c
### q_new
首先要初始化一個空的佇列，而空的佇列需要有個指標指著它，即 `head` 。 `head` 是個指向 dummy node 的指標，用意在於讓佇列擁有起點，方便查找第一個元素和最後一個元素，而在佇列為空的時候， `head->next` 和 `head->prev` 都應該指向 `head` 自己。
### q_free
不需要再使用佇列時，要釋放所有已分配的記憶體，包含了佇列的 `head` 以及內部所有 `element_t` 結構的元素。
因此我一開始的想法是先使用 `list_del_init` 解除每個節點之間的鏈結，並且再分別釋放 `element_t` 結構內的 `list` 和 `value`，最後釋放 `element_t` 元素本人的記憶體，但這樣會遇到重複釋放已未被使用的記憶體空間而導致錯誤。因此我改使用 `"queue.h"` 裡面定義的 `q_release_element` ，可以直接處理好釋放單一 `element_t` 元素的記憶體。
```diff
list_for_each_safe (pos, next, head) {
element_t *entry = list_entry(pos, element_t, list);
- list_del_init(pos);
- free(pos);
- free(entry->value);
- free(entry);
+ q_release_element(entry);
}
free(head);
```
### q_insert_head, q_insert_tail
當我們已經有佇列時，即有 `head` 指標時， `q_insert_head` 可以把新的元素插入在第一個元素，也就是 `head->next` 所指位置， `q_insrt_tail` 大同小異，改成插入在最後一個位置。
首先應該要先分配一個 `element_t` 大小的記憶體空間給心元素用，並且將傳入的字元指標 `*s` 複製到新建的元素的 `value`，在此如果用 `strcpy` 在記憶體管理上不太安全，因為 `strcpy` 在目標指標所指向字串的緩衝區不足以容納來源字串的情況下，會產生未預期的結果，此外在使用前也需先手動分配記憶體給目標字串。因此，我改用 `strdup` 讓函式自動分配足夠大小的記憶體，避免區段錯誤。
```diff
- strcpy(new->value, s);
+ new->value = strdup(s);
```
另外在插入元素時要檢查記憶體分配是否成功，若失敗則應回傳 `false` ，如果是新分配元素 `new` 的 `value` 分配失敗了，必須要在 `return false` 之前將成功分配的 `new` 給釋放掉，避免佔用記憶體。
```c
if (!new->value) {
free(new);
return false;
}
```
而在實作這兩個函式的過程中僅差別在最後要將元素之間鏈結起來，必須透過 `element_t` 結構內嵌的 `struct list_head list` ，分別透過 `"list.h"` 定義好的 `list_add` 和 `list_add_tail` 進行插入。
```c
list_add(&new->list, head);
list_add_tail(&new->list, head);
```
### q_remove_head, q_remove_tail
實作移除元素時，只需取消節點與串列的鏈結，而不須釋放記憶體。除了移除元素外，我們還需將移除元素的 `value` 複製到 `sp` ，根據 `bufsize` 的大小複製。 `strncpy` 可以根據給定的 `bufsize` 來決定要從哪裡複製多長的字串，而且 `*sp` 是已經有非配記憶體的空間，只要 `sp` 不為 `NULL` ，我們即可將字串用 `strncpy` 複製到 `sp` 。
`strncpy` 並不會自動分配記憶體，也不會在目標字串後面補上 `\0` ，因此我們需自行補上：
```c
sp[bufsize - 1] = '\0';
```
而 `q_remove_head` 和 `q_remove_tail` 的差別只在於要移除第一個還是最後一個元素，因此可以分別用 `head->next` 和 `head->prev` 取得，再用 `list_entry` 得到他們 `element_t` 結構的元素，最後再用 `list_del` 移除即可。
### q_size
回傳佇列內有幾個元素，若傳進來的 `head` 為 `NULL` 或是佇列為空則回傳 0 。
```c
if (!head || list_empty(head)) {
return 0;
}
```
我們只需要用 `list_for_each` 就可以走訪所有佇列內元素並計數了。
```c
list_for_each (pos, head) {
size++;
}
```
### q_delete_mid
在刪除中間元素時，我使用一個整數 `index` 並且搭配 `list_for_each` 來紀錄目前走到哪裡，當 `index` 現在是 $⌊n / 2⌋^{th}$ 則讓 `pos` 指向該元素裡面的 `list`，並且再搭配 `list_del` 和 `q_release_element` 進行刪除。
```c
list_for_each (pos, head) {
if (index == q_size(head) / 2) {
break;
}
index++;
}
element_t *entry = list_entry(pos, element_t, list);
list_del(pos);
q_release_element(entry);
```
### q_delete_dup
考量到 `q_delete_dup` 傳進來的佇列是已排序的，我們只需要 $O(n)$ 的時間複雜度，即走訪所有元素一次即可完成重複值刪除，因為重複值都會被連續地排在一起，所以檢測到重複值時就一路刪除元素，直到出現不一樣的元素值。
我使用 `list_for_each_safe` ，避免當前元素被刪除後，找不到下一個元素，並且使用布林值 `duplicate` 紀錄現在的元素是重複的還是非重複的。此外在每次迭代取得 `next_entry` 時，要確保 `next != head` ，否則在使用 `list_entry` 時會因為 `head` 所指向的節點是 dummy node 而發生錯誤。
```diff
- const element_t *next_entry = list_entry(next, element_t, list);
+ const element_t *next_entry =
+ (next == head) ? NULL : list_entry(next, element_t, list);
```
而在比較兩者的 `value` 時，為什麼不能用 `==` 而是必須透過 `strcmp` ？根據 [C語言規格書](https://web.archive.org/web/20180127192726/http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 6.5.9 的 6. ：
> Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space.
代表 `==` 在兩邊運算元都是指標的情況下，會去比較的是指標所指向的記憶體位址，但 `pos_entry->value` 和 `next_entry->value` 兩者即使指向的字串相同，指標所指的記憶體位址也不同，因此直接使用 `==` 會誤判，若要單純比較字串是否相同或是大小就必須使用 `strcmp` 。
```diff!
- if (pos_entry->value == next_entry->value)
+ if (strcmp(pos_entry->value, next_entry->value) == 0)
```
### q_reverse
反轉所有元素時，也就是把當前節點 `pos` 的 `pos->prev` 和 `pos->next` 所指向的節點交換。此外，連 `head->prev` 和 `head->next` 所指向的節點也應該交換，才能確保仍然是雙向環狀鏈結串列。
> 想法：或許可以直接用 `list_move` 來做就好，不用再手動交換指標。
### q_reverseK
`q_reverseK` 使得每 K 個元素反轉一次，若不足 K 個元素則不反轉。首先判斷 `head` 為 `NULL` 或佇列只有 0 或 1 個元素，則直接回傳。在每次迭代都把一組元素反轉，因此每次會先找該組的開頭以及結尾。
```c
for (end = start->next; end != head && counter < k;
end = end->next, counter++)
;
```
讓 `start` 停在 K 個元素的前一個，而 `end` 停在 K 個元素的後一個。並且走訪中間的 K 個元素，依序將其 `next` 與 `prev` 指向的元素交換。中間我加了判斷目前是否為 K 個元素裡的第一個或最後一個，使得反轉完能維持雙向環狀鏈結串列。
```c
while (pos != end) {
struct list_head *tmp = pos->next;
if (pos->prev != start)
pos->next = pos->prev;
else
pos->next = end;
if (tmp != end)
pos->prev = tmp;
else
pos->prev = start;
pos = tmp;
}
```
最後再更新 `start` 和 `prev` 並且進行下一次迭代。
### q_sort
#### 想法
根據 `q_sort` 的要求，排序演算法應該要保持 Stable Sort ，因此我選擇使用 Merge Sort 來實作，在相同元素值被排序後仍可以保持原本的相對順序。
為什麼用 Merge Sort 而不是 Quick Sort ？首先我們需要找一個可以保持 Stable Sort 的演算法，而兩者皆可在實作上確保這一點，但在時間複雜度上， Merge Sort 不管在最佳或是最糟情況都是 $O(n\,log\,n)$ ，但是 Quick Sort 只在最佳情況是 $O(n\,log\,n)$ ，在最糟情況，也就是已排序的串列，會來到 $O(n^2)$ 。
| | Best|Average| Worst |
| -------- | -------- | -------- | -------- |
| Merge Sort | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ |
| Quick Sort | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ |
為什麼用 Merge Sort 而不是 Quick Sort ？首先我們需要找一個可以保持 Stable Sort 的演算法，而兩者皆可在實作上確保這一點，但在時間複雜度上， Merge Sort 不管在最佳或是最糟情況都是 $O(n\log n)$ ，但是 Quick Sort 只在最佳情況是 $O(n\log n)$ ，在最糟情況，即已排序的串列，會來到 $O(n^2)$ 。
```
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
```
#### 實作
一開始實作遞迴版 Quick Sort 雖然可正確排序，但在測試效能時會出現警告，分別是 Time Limit Exceed 和記憶體未被釋放的警告，實際上就是因為超過時間了，所以程式沒跑完，因此也沒釋放掉記憶體。
```diff
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 4000000 blocks are still allocated
--- trace-14-perf 0/6
```
由前面可知，遞迴版的 Quick Sort 時間複雜度上不可行，因此接下來改用 Merge Sort 。
遞迴版 Merge Sort 必須先將串列分成兩半，因此我們使用快慢指標的手法，使得 `slow` 每次走一步，而 `fast` 每次走兩步，讓 `slow` 在最後停在串列的中間元素。
```c
int count = q_size(head) / 2;
struct list_head *slow = head, *fast = head->next;
for (; count; slow = slow->next, fast = fast->next->next, count--)
;
```
接下來要將佇列分成兩半，因此需要兩個 dummy node ，分別代表兩半的串列，我們需要再另外創建一個 dummy node 來代表前半佇列。注意在這裡是宣告真實的 `list_head` 節點而不是指標，若宣告指標則會需要有實際的記憶體位址給指標指。切完後再遞迴呼叫，並且使用 `merge_two` 兩兩合併。
```c
LIST_HEAD(left);
list_cut_position(&left, head, slow);
```
- 那如果是 indirect pointer v.s. dummy node 呢？
> 即使是 indirect pointer ，最後還是需要另一個新的 dummy node 來指向另一半的佇列頭部。假如我們先借用既有的 dummy node：
> `struct list_head **left = &head;`
> 這樣的宣告方式會使得後續更改 `*left` 時，會連動更改了 head 所指向的地址。
### merge_two
`merge_two` 為輔助 `q_sort` 的函式，目的在合併兩個給定的佇列並用 `head` 當作佇列的 dummy node 指標。若我們直接針對給定的 `head` 和 `target` 做移動元素，會在用迴圈走訪的時候導致走訪順序亂掉，因此我們另外宣告實際的 `list_head` 節點 `pos` 作為 dummy node，在稍後依序存放已排序的節點。
而在迴圈內我們改用 `list_first_entry` 取代 `list_entry` ，因為每次都是拿 `target` 和 `head` 串列的剩餘第一個元素來比較值，並且放到 `&pos` 串列，因此用 `list_first_entry` ，這樣的好處是不用再另外開兩個 `struct list_head *` 來分別走訪兩個串列，每次取得元素只需要拿 `target` 和 `head` 就好。
```diff
- struct list_head *l = target->next;
- struct list_head *r = head->next;
while (!list_empty(head) && !list_empty(target)) {
- element_t *l_entry = list_entry(l, element_t, list);
- element_t *r_entry = list_entry(r, element_t, list);
+ element_t *l_entry = list_first_entry(target, element_t, list);
+ element_t *r_entry = list_first_entry(head, element_t, list);
...
}
```
此外我們將剩餘部份也用 `list_splice_tail_init` 來貼至 `&pos` ，注意這邊不能用 `list_splice_tail` ，這樣在 `head` 串列沒有節點之後，`head` 仍會指向已被貼過去的節點，導致最後使用 `list_splice(&pos, head)` 時，`head->next` 並沒有指向正確的節點而發生 dereference a NULL pointer。
另外最後不能直接更改 `head` 為 `pos` ，而是使用 `list_splice` 才對，因為 `head = &pos` 只是改變 `head` 指向 `pos` 而已，使得 `head` 無法實際透過 `next` 和 `prev` 走訪我們已排序完的元素。
```diff
- head = &pos;
+ list_splice(&pos, head);
```
#### 問題
- 延伸：如果 head 是 null 可是 target 不是呢？
> 實際上不會發生，因為 target 和 head 是透過快慢指標決定切在哪的，當總長是偶數，兩者一樣長，而當總長是奇數時，後半部會比前半部多一個元素，即 `head` 會比 `target` 多一個。
- 延伸：能不能優化 `q_sort` ？
> 根據[Merge Sort 與它的變化](https://hackmd.io/@lambert-wu/list-merge-sort)裡面迭代版與遞迴版的效能分析，首先可將迭代版的 Merge Sort 分成兩階段：分割出好幾個串列，以及合併這些串列。可以得知在 Divide 函式選擇用分割出排序好的串列， Merge 函式選擇用分治法的情況下，在順序打亂、排序好、順序相反的情況下，迭代版 Merge Sort 都比一般遞迴版更快，或許可以改用迭代版本的 Merge Sort 實作 `q_sort` 。
### q_ascend, q_descend
`q_ascend` 和 `q_descend` 分別是檢查當前節點的所有後面元素，是否有 `value` 比他小 / 比他大的，若有則刪除當前節點 `pos_entry` 。這邊講的是刪除，因此除了取消鏈結外，還要釋放記憶體。
我的想法是使用 `list_for_each_safe` ，這樣可以確保刪除當前節點 `pos` 後，還是能存取下一個元素，而 `pos` 內嵌在 `pos_entry` 裡面的 `list_head` 結構。此外在檢查當前節點時，另外宣告一個 `right` 指標指向 `&pos->next` ，用 `right` 來走訪後面所有元素，並且在下一次 `list_for_each_safe` 的迭代重置 `right` 指向的元素。
```c=
list_for_each_safe (pos, pos_safe, head) {
struct list_head *right = pos->next;
element_t *pos_entry = list_entry(pos, element_t, list);
while (right != head) {
const element_t *right_entry = list_entry(right, element_t, list);
if (strcmp(pos_entry->value, right_entry->value) > 0) {
list_del(pos);
q_release_element(pos_entry);
break;
}
right = right->next;
}
}
```
需要注意的是，我們需要先取消 `pos` 與其他節點的鏈結，才可以釋放整個 `pos_entry` 的記憶體，避免 `pos` 仍存在於鏈結串列中。
```c
list_del(pos);
q_release_element(pos_entry);
```
`q_ascend` 和 `q_descend` 只差別在於內部 if 的條件判斷。
```c
if (strcmp(pos_entry->value, right_entry->value) > 0) // q_ascend
if (strcmp(pos_entry->value, right_entry->value) < 0) // q_descend
```
### q_merge
`q_merge` 要將所有的佇列合併成一個佇列並排序，並且是合併到第一個佇列的 `head` 。這邊傳進來的 `head` 並不是用來存取一個 `element_t` 佇列的，而是存取整個 `queue_contex_t` 的鏈結串列，可以想像成單一個佇列裡面是由 `element_t` 作為元素，而所有佇列合起來又是一個大型鏈結串列，其中每個元素為 `queue_contex_t` 結構，代表一個佇列。
我首先透過 `list_first_entry` 來取得第一個佇列，並且用 `list_for_each_entry_safe` 走訪所有 `entry` ，在這裡每個 `entry` 不是一個元素，而是一整個佇列，因此在迴圈內就依序將走訪到的佇列之所有元素移至 `target` 指向的佇列，最後再呼叫 `q_sort` 將所有元素進行排序。
在將佇列合併的過程中，必須將被合併的佇列之 dummy node 使用 `INIT_LIST_HEAD` 重新初始化 `entry->q` ，避免仍指到已經被合併的節點。
```c
if (entry != target && entry->q && !list_empty(entry->q)) {
list_splice_tail(entry->q, target->q);
INIT_LIST_HEAD(entry->q);
}
```
- 延伸：先合併再排序，還是邊合併邊排序比較好？
## Valgrind + 自動測試程式
### 透過 Massif 視覺化 simulation 過程中的記憶體使用量
先透過 valgrind 來查看 `"queue.c"` 的實作狀況，觀察在測資 17 跑的狀況：
```shell
$ valgrind --tool=massif ./qtest -f ./traces/trace-17-complexity.cmd
```
```shell
$ massif-visualizer massif.out.<pid>
```
實作 percentile 處理前：
原程式透過 `malloc_or_fail` 和 `test_malloc` 去分配記憶體，分別在 `"report.c"` 和 `"harness.c"` ，用來測試程式是否分配記憶體成功。
實作 percentile 處理後：
`doit` 在實作後突然就佔用了很多的記憶體，可能是程式裡有未被釋放的記憶體，因此檢查一下可發現我有在 `doit` 新增 `percentile` ，也要有相對應的釋放。
```diff
free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
+ free(percentile);
```
重測一次之後 `doit` 的記憶體用量就下降到低比例了。
## 亂數
### 訊息熵 (Entropy)
> [由大數法則理解訊息熵 (entropy) 的數學意義](https://hackmd.io/@8dSak6oVTweMeAe9fXWCPA/ryoegPgw_)
熵是訊息本身不確定性的量度，對於一個離散型隨機變數 $X$ ，熵的定義如下：
$H(X) = \mathsf E_{x \sim X} \left[-\log \mathsf P_X(x) \right] = \sum_{x}- \mathsf P_X \log \mathsf P_X (x)$
作者在解釋熵之前先用資料壓縮舉例，並說明我們給定一個 $\epsilon$ ，透過演算法生出的 decoder 解碼錯誤機率應該低於這個數值，並且根據不同的 $n$ 值探討不同的 encoder 和 decoder 來解釋。一個降低錯誤率至 $n$ 以下的方法是不斷收集長度不同的序列至集合 $S^n$ ，直到這些序列出現的總機率超過 $1-\epsilon$ 。
> 給定 $\epsilon \in (0,1)$ 且 $n \in \Bbb N$ ，稱集合 $\mathcal{B} (n, \epsilon) \subseteq \mathcal{S}^n$ 為一個 $\epsilon$-high probability set 若且唯若
>
> $\mathsf{Pr} \{ s^n \in \mathcal B (n, \epsilon) \}
> \overset{(2)}
> = \sum_{s^n \in \mathcal B(n, \epsilon)}
> \left(
> \prod_{i = 1}^n \mathsf P_S(s_i)
> \right)
> \ge 1 - \epsilon$
>
> 為了達到error probability小於 $\epsilon$ ，我們只需要 $\left| \mathcal B(n, \epsilon) \right|$ 個獨一無二的二進制編碼即可，也就是說，我們一旦找到最小的 $k$ 使得 $2^k \ge \left| \mathcal B(n, \epsilon) \right|$ ，即可用 $k$ 個位元的代價完成一個 error probability 在 $\epsilon$ 之下的訊息壓縮。
然而筆者提到這樣的方法難以捕捉隨著 $n$ 變大可達到的壓縮比變化趨勢為何，因此改用大數法則分析。
筆者用丟骰子的粒子很簡單舉例了如果我們丟很多次公正骰子，那將所有點數相加並除以 6 ，其結果剛好會是期望值 3.5 的機率趨近為 1 。套用回壓縮訊息，當 $n$ 夠大則序列中每個字母出現次數的平均，再與 $f$ 的期望值相減不超過 $\delta$ 的機率趨近於 1 。為了讓原本 $s_n$ 的機率連乘改成機率相加，在等式兩邊取對數即可，因此推導出 Shannon Entropy 的函數，即對於任意 $n$ 都足夠小的 $\left| \mathcal B(n, \epsilon) \right|$ ，完成錯誤機率在 $\epsilon$ 底下的訊息壓縮。因此 entropy 是我們可以達到的最好壓縮比，若 entropy 越大，則越難進行壓縮，也就是所需的資訊量越大，因此可應證「資訊與熵互補，資訊就是負熵」。
### 觀察 qtest 的 entropy
```shell
cmd> option entropy 1
cmd> ih RAND 10
l = [gzbrgpjhi(35.94%) psxzoa(29.69%) aqzce(26.56%) yyznkg(26.56%) imqkzw(29.69%) hvghnlr(29.69%) egoxpo(26.56%) ftxutyyh(29.69%) bgxpn(26.56%) xmbykcfz(35.94%)]
```
觀察每個字串的 entropy 可以發現影響字串的熵的因素是字串內出現過多少個字母，比如 `ridykbl` 和 `uynbglfg` 雖然長度不同，但都出現 7 個字母，因此其 entropy 是相同的。其計算方式是根據程式內的 `shannon_entropy` 進行計算。
```c
for (uint32_t i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i]) {
uint64_t p = bucket[i];
p *= LOG2_ARG_SHIFT / count;
entropy_sum += -p * log2_lshift16(p);
}
}
```
### 實作新的命令切換不同的 PRNG
追蹤程式發現 `ih RAND 10` 會將 `need_rand` 設置為 `true` 並呼叫 `fill_rand_string` ，並且使用內建的 `rand` 和 `randombytes` 決定字串長度和填充不同字母。
```c
while (len < MIN_RANDSTR_LEN)
len = rand() % buf_size;
...
randombytes((uint8_t *) randstr_buf_64, len * sizeof(uint64_t));
for (size_t n = 0; n < len; n++)
buf[n] = charset[randstr_buf_64[n] % (sizeof(charset) - 1)];
```
我在這邊做了一些小更動，改成用 if 來決定要用 Xorshift 還是用內建的亂數產生器來做隨機字串的產生，參考 [Xorshift](https://en.wikipedia.org/wiki/Xorshift) 發現 xorshift 是透過位移和 XOR 運算取得序列中的下一個數字，因此我另外開了一個 `"xorshift.h"` 和 `"xorshift.c"` ，在裡面實作使用時間作為種子並且套用 xorshift 的方法產生亂數序列。
```c
static uint64_t xorshift64_state = 0;
void xorshift64_init(uint64_t seed) {
if (seed == 0) seed = (uint64_t)time(NULL);;
xorshift64_state = seed;
}
uint64_t xorshift64_rand(void) {
xorshift64_state ^= xorshift64_state << 13;
xorshift64_state ^= xorshift64_state >> 7;
xorshift64_state ^= xorshift64_state << 17;
return xorshift64_state;
}
```
並且改一下 Makefile 讓 `"qtest.c"` 和 `"xorshift.c"` 可以連結在一起，此外在 `"console.c"` 加入 `option prng` ，這個命令可以改變 `change_prng` 的值，因此可以用 `change_prng` 來區分現在用的是內建還是 Xorshift 的 PRNG。
- 內建 PRNG
```shell
cmd> option entropy 1
cmd> new
l = []
cmd> ih RAND 10
l = [yomqwi(29.69%) fhyxui(29.69%) etupzn(29.69%) kubgrpjum(35.94%) cyzedyt(29.69%) wrcvn(26.56%) tphts(21.88%) bfkfevea(29.69%) jeidxh(29.69%) tubvjx(29.69%)]
```
- Xorshift PRNG
```shell
cmd> option prng 1
PRNG switched to Xorshift
cmd> new
l = []
cmd> ih RAND 10
l = [ufvldhtg(35.94%) jqrbqwse(32.81%) wwgwxgn(21.88%) pzwtxrgcq(37.50%) pbyuk(26.56%) bzcsxlyr(35.94%) uxghilvxv(32.81%) ombtojz(29.69%) gxjofkb(32.81%) qwwuanzg(32.81%)]
```
### 透過統計分析 Xorshift 和內建 PRNG 比較
### 在 qtest 提供新的命令 `shuffle`
首先在 queue.c 實作 shuffle 的過程，因此我們需要先寫一個函式 `q_shuffle` ，並且使用 [Fisher-Yates Shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法的步驟來實作。按照作業說明，演算法有以下三步：
1. 先用 `q_size` 取得 queue 的大小 `len`。
2. 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 `random` 個節點，`new` 會指向最後一個未被抽到的節點，將 `old` 和 `new` 指向的節點的值交換，再將 len - 1。
3. 隨著 `len` 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，`shuffle` 就結束。
因此我根據上述步驟在 `queue.[ch]` 實作 `q_shuffle` 的宣告與定義，並且在交換兩節點的步驟使用 `list_move` 來讓程式碼看起來更精簡。
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
int len = q_size(head) - 1;
struct list_head *tail = head->prev;
for (int j = len; j > 0; j--) {
int random = rand() % (j + 1);
struct list_head *pos = NULL;
for (pos = head; random >= 0; random--)
pos = pos->next;
if (pos == tail)
continue;
struct list_head *tmp = pos->prev;
list_move(pos, tail);
list_move(tail, tmp);
tail = pos;
}
}
```
在做完 `q_shuffle` 之後，要到 `"qtest.c"` 新增命令，讓使用者可以輸入 `shuffle` 以對佇列元素進行重新排列，並且透過 `do_shuffle` 呼叫 `q_shuffle` 實際進行洗牌，這樣使用者就可以將輸入的命令和洗牌的動作連結起來了。 `do_shuffle` 的實作方法參考 `do_swap` ，因為都只吃一個參數、禁止分配額外記憶體、並直接呼叫在 `queue.c` 裡面的相關函式。
```diff!
+ ADD_COMMAND(shuffle, "Shuffle nodes in queue randomly", "");
```
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q) {
report(3, "Warning: Calling shuffle on null queue");
return false;
}
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
q_show(3);
return !error_check();
}
```
這樣就完成了在 qtest 新增 `shuffle` 命令，但由於不可更改 `"queue.h"` ，因此將 qtest 裡的相關變更註解掉，避免發生錯誤。
### 統計方法驗證 `shuffle`
使用 lab0(D) 的 Python 測試程式，並且將洗牌次數調整為 100000 ，觀察每種排列出現的次數，會得到以下結果：
```
Expectation: 4166
Observation: {'1234': 4214, '1243': 4225, '1324': 4085, '1342': 4170, '1423': 4162, '1432': 4141, '2134': 4320, '2143': 4186, '2314': 4182, '2341': 4164, '2413': 4137, '2431': 4158, '3124': 4037, '3142': 4144, '3214': 4191, '3241': 4181, '3412': 4154, '3421': 4040, '4123': 4096, '4132': 4331, '4213': 4190, '4231': 4101, '4312': 4192, '4321': 4199}
chi square sum: 26.63706192990879
```
根據圖解，排列的出現次數呈現 uniform distribution。此外根據我們排列有 24 種，可得到自由度為 23，而我們的 chi-square sum ($\chi^2$) 為 26.64 ，查卡方分佈表可知 p-value 介於 0.1~0.9 ，因為 P value（0.1~0.9）> alpha（0.05），統計檢定的結果不拒絕虛無假說 ($H_0$) ，也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻。
## 研讀論文〈 Dude, is my code constant time? 〉
在 Introduction 中，作者先介紹了 Timing attacks 的興起，攻擊者通過測量加密算法運算時所需的執行時間，從中推測出密鑰或其他機密數據。之後，許多非常數時間的實作就被成功攻擊，而 Timing Attack 的優勢在於只需要測量執行時間變化即可，甚至可以遠端進行。
傳統上，要檢查一段程式碼是否以常數時間運行，需要手動檢查組合語言層面的代碼，觀察是否有基於秘密數據而改變執行路徑的指令（例如分支或記憶體存取），而這樣的手動檢查很耗時間。雖然已有其他工具幫助檢查，但這些方法需要建立硬體模型來預測 CPU 的行為，而實際上 CPU 製造商通常不會公開詳細的內部工作機制，甚至受到微程式更新等影響，使得準確建模變得非常困難。因此作者提出 dudect 工具，以 leakage detection tests 的觀念和對執行時間的統計分析，實作出方法簡單且可以規避如何模擬硬體問題的工具。
### Timing Leakage Detection 的方法
基本概念是檢查在不同輸入條件下，執行同一加密函數所耗費的時間分布是否存在統計上的差異，若有顯著不同，則可能存在依賴數據的 Timing Leakage，因此做法在論文中為以下三步：
1. Measure execution time : 通過對兩種不同類型輸入（固定與隨機）的大量執行時間測量，來分析並檢測是否存在統計上顯著的差異
2. Apply post-processing : 對測量數據進行後處理，過濾掉一些 outlier ，並進行一些數據轉換提高統計檢測的靈敏度
3. Apply statistical test : 利用 t-test 來判斷兩組執行時間數據分布是否存在顯著差異，也就是檢測是否存在 timing leakage，並且推翻虛無假說：兩組執行時間分佈是相等的。
### 程式碼的 simulation 模式與 Student's t-distribution
> 參考 [salmoniscute](https://hackmd.io/@salmonii/linux2025-homework1#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89)
lab0-c 的測資 17 檢查程式是否運行在常數時間，打開第 17 筆測資發現第一行為 `option simulation 1` ，接著檢查 `"qtest.c"` 發現 `simulation` 為 1 時會呼叫 `is_insert_tail_const`, `is_insert_head_const`, `is_remove_tail_const`, `is_remove_tail_const` ，而在 `"fixture.c"` 則有定義如下，當我們執行這四個函式，會去呼叫 `test_const` 測試他們是否為常數時間。
```c
#define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) { return test_const(#op, DUT(op)); }
```
而 `test_const` 最多會測試 `TEST_TRIES` 次，每次呼叫 `doit` 來測試是否為常數時間， `doit` 會呼叫 `maesure` 做執行時間的計算，並且再呼叫 `update_statistics` 來執行 `t_push` ，也就是做一次 t-test。
```c
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();
```
Student's t-distribution 通常用於樣本數小且母體標準差未知的情況下的一種連續機率分佈，用於 Student's t-test 進行顯著性測試的基礎，而在 Student's t-test 則有幾個應用，其中的雙樣本 t-test 則是我們會用來檢驗常數時間的檢定，其假說檢定如下，虛無假說為兩母體的變異數相等，當我們拒絕虛無假說時，可說明兩母體之間可能有顯著差異。
- $H_0$ ：$\sigma_1^2 = \sigma_2^2$
- $H_0$ ：$\sigma_1^2 \ne \sigma_2^2$
而 `"ttest.c"` 所實作的是 Welch's t-test，其放寬母體的條件為母體標準差不一定要相等，並將假說檢定更改如下，而這樣子的檢定更適合對程式執行時間進行統計分析，因為現實情況的執行時間往往受到軟硬體干擾，如論文所述。
- $H_0$ ：$\mu_1 = \mu_2$
- $H_0$ ：$\mu_1 \ne \mu_2$
`"ttest.c"` 的三個函式說明如下：
- `t_push`：用 Welford Method 更新平均值和累計平方差
- `t_compute`：計算 t 值作為檢定的統計量
$$
t = \frac{\bar{x}_1 - \bar{x}_2}{\sqrt{\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2}}}
$$
- `t_init`：重置計算 t 值所需要的變數
### Percentile 的處理
Percentile 的設定是為了達成論文中提及的 Cropping ，即刪除一些導致分佈呈現右偏態的值，這些值通常是受到做作業系統或其他條件影響導致時間變長。在 [`oreparaz/dutect`](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中，作者使用以下公式，可以根據樣本的分佈決定閾值要設定多少，再根據閾值進行 Cropping ，此公式隨著 `i` 增加，值的變化從 0 到 1，再經由 `percentile` 函式計算該閾值樣本的位置。
```c
1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)
```
最後回到 `update_statistics` ，只有在 `difference` 不超過閾值的樣本才會被加到 t-test 進行檢定。
```c
// t-test on cropped execution times, for several cropping thresholds.
for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
if (difference < ctx->percentiles[crop_index]) {
t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
}
}
```
### 幫 lab0-c 加上 Percentile 處理
根據 [`oreparaz/dutect`](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) ，我們在 `"fixture.c"` 加入新的函式為 `percentile`, `prepare_percentile`, `cmp` ，並且更新 `update_statistics` 和 `doit` ，加上檢查閾值。
- `doit`
```diff!
+ int64_t *percentile = calloc(N_MEASURES, sizeof(int64_t));
...
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
+ prepare_percentiles(exec_times, percentile);
update_statistics(exec_times, percentile, classes);
ret &= report();
```
- `update_statistics`
```diff
- if (difference <= 0)
+ if (difference >= percentiles[i])
continue;
```
完成更新並 push 之後就有看到星之卡比了。
## Linux 核心的鏈結串列排序
> 參考 [EricccTaiwan](https://hackmd.io/@ericisgood/linux2025-homework1#Linux%E6%A0%B8%E5%BF%83-liblist_sortc)
### 相關論文
- [Bottom-up Mergesort: A Detailed Analysis](https://doi.org/10.1007/BF01294131)
- [The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules](https://doi.org/10.1006/jagm.1998.0986)
- [Queue-mergesort](https://www.sciencedirect.com/science/article/abs/pii/002001909390088Q?via%3Dihub)
### 研讀並引入 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
`"list_sort.c"` 採用 bottom-up 合併排序的策略，但是改用深度優先取代廣度優先的順序，並且維持 2:1 的合併。其規定是若現在有兩個待合併且長度為 $2^k$ ，他們會等到又有 $2^k$ 個元素待合併的時候才會將前兩個串列合併成長度為 $2^{k+1}$ 的串列。參考 [Linux 核心專題：改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh) 的解說錄影，才知道這樣做的原因是避免頻繁發生 cache miss，若我們使用如 Linux 核心的合併排序，這樣可確保元素剛被存取過，仍在 cache 的上方時就進行合併，而且每次存取與合併都是 $3\cdot 2^k$ 元素，也不超過快取大小。
接下來觀察 `list_sort` 函式的程式碼，其使用 `pending` 指標紀錄剛剛所說的待合併串列，並且用 `count` 紀錄合併的時機。核心程式碼的註解有提到 `count` 所控制的六種狀態，其中 merge 發生在 state 的變化為 2->3 和 4->5 ，我們可以各得到一個長度為 $2^k$ 的串列，並且在 state 從 5->2 時合併。
> There are six states we distinguish. "x" represents some arbitrary
> bits, and "y" represents some arbitrary non-zero bits:
> 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
> 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
> 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
> 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
> 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
> 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
> (merge and loop back to state 2)
以下則用表格呈現若我們有 7 個元素要排的時候，會分別是什麼樣的狀態：
- `pending`：比如結構為 4 $\leftarrow$ 2 $\leftarrow$ 1 ，代表分別有長度為 4, 2, 1 的子串列。
- `count`：在 `pending` 裡的節點總數
- `state`：檢查目前 `pending` 的狀態，在程式碼裡為 `bits`
- ==螢光筆==：代表在**下一步要合併**時，`tail` 和 `tail->prev` 分別指向的位置。
| `count` | 檢查是否 merge | 對應的 state | `pending` 上面的結構 |
| ------- | -------------- | ------ | -------------------- |
| 0000 | no | 00x | NULL |
| 0001 | no | 01x | 1 |
| 0010 | no | x10x | ==1 $\leftarrow$ 1==|
| 0011 | yes (state: 2 $\to$ 3) | x11x | 2 $\leftarrow$ 1|
| 0100 | no | y00x | 2 $\leftarrow$ ==1 $\leftarrow$ 1==|
| 0101 | yes (state: 4 $\to$ 5) | y01x | ==2 $\leftarrow$ 2== $\leftarrow$ 1|
| 0110 | yes (state: 5 $\to$ 2) | x10x | 4 $\leftarrow$ ==1 $\leftarrow$ 1==|
| 0111 | yes (state: 2 $\to$ 3) | x11x | 4 $\leftarrow$ 2 $\leftarrow$ 1|
程式碼則是用以下方式來檢查現在的 state ，尋找 bits 的最低 0 位元，決定接下來是否需要合併，並且更新 `tail` 的位置來決定要合併 `pending` 裡面的哪兩個串列。
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
if (likely(bits)) {
// ... do merge
}
```
在 `list` 的所有節點都被加到 `pending` 之後，會將所有節點合併起來，此時子串列才有可能出現長度不是 2 的冪，另外由於前面的 do-while 迴圈中都是以單向鏈結串列做合併的，因此在最後要將 `pending` 整個結構合併起來，並復原成雙向環狀鏈結串列。
```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);
```
### 效能分析
接下來我們將 list_sort.c 的程式碼也引入到 qtest.c ，新增函式為 `q_list_sort`，並且在 qtest 新增命令 `listsort` 來執行 Linux 核心的排序。由於在核心內有 comparator 作為 function pointer 傳入，我們也自行針對作業比較字串的規定寫了一個，並且使用 `strcmp` 的結果當作回傳值。
```c
int compare(void *priv, struct list_head *q1, struct list_head *q2)
{
if (q1 == q2)
return 0;
element_t *e1 = list_entry(q1, element_t, list);
element_t *e2 = list_entry(q2, element_t, list);
return strcmp(e1->value, e2->value);
}
```
在 [Bottom-up Mergesort: A Detailed Analysis](https://doi.org/10.1007/BF01294131) 有提到對於 Best-case, Worst-case, Average-case 的比較次數是根據單一次 merge 的劃分來做區隔的，論文隨後提供了一個公式說明比較次數 $c_{n,m}$ 的上下界：
> The cost measures $C_{b,bu}(N)$, $C_{w,bu}(N)$, and $C_{a,bu}(N)$ are, of course, ultimately based on the quantities $c_{n,m}$ ,denoting the number of comparisons in the single (n, m) merge processes.
$$
\min \{n,m\} \leq c_{n,m} \leq n+m-1
$$
這樣的公式是因為 `merge` 最差情況是兩個子串列元素的值完美交錯
使得每個元素都需要比較，直到只剩一個。而最好情況則是比較時都是較短的子串列被 merge ，那較長的子串列就直接加到後面即可。
- [1,2,3] [4,5,6] 只需 3 次比較即可完成：(1,4), (2,4), (3,4)
- [1,3,5] [2,4,6] 需要 5 次比較才可完成：(1,2), (3,2), (3,4), (5,4), (5,6)
Sign in with Wallet
Connect another wallet