# 2024q1 Homework2 (quiz1+2)
contributed by < `fennecJ` >
## 第一週測驗題
### 測驗一
#### 程式運作原理
程式參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 的作法，將給定的 list 分為 pivot, 比 pivot 小的 left list 以及比 pivot 大的 right list 。假設我們有一個 list 如下：
```graphviz
digraph G {
node[shape=plaintext];
pivot;
L;
R;
p;
node[shape=box];
ele1[label=2];
ele2[label=6];
ele3[label=4];
ele4[label=7];
ele5[label=1];
{
rank="same"
ele1->ele2->ele3->ele4->ele5;
}
pivot->ele1;
L->ele1
p->ele2;
R->ele5
}
```
經過第一次 partition 後，原本的 list 被分成三個 sub list：
```graphviz
digraph G {
node[shape=plaintext];
L;
pivot;
R;
node[shape=box];
ele1[label=2];
ele2[label=6];
ele3[label=4];
ele4[label=7];
ele5[label=1];
L->ele5
pivot->ele1;
R->ele4->ele3->ele2
}
```
再來將 L, pivot, R 三個 list 的 begin 和 end 分別存入 begin[i~i+2], end[i~i+2] ，然後更新 L, R 到 begin[i+2], end[i+2] 為新的 sublist （在此為 R 這個 sublist）。對每個 sublist 用同樣的作法進行切分，直到 L = R，表示這是處理好的 list ，將其加入 result 。最後直到 i = 0 ，表示所有 sublist 都被處理完畢，離開迴圈即完成整個 list 的 sorting 。
#### 改善實作
##### 節省記憶體開銷
由於我們可以透過 list_tail() 從 begin 走到 end，因此我們不需要 end[] 陣列，從而免去 `node_t` 指標陣列的使用：
> commit [f335fa](https://github.com/fennecJ/linux2024-quiz/commit/f335fadb2e780025bb666208da79bd58b5972ed2)
```diff!
- node_t *L = begin[i], *R = end[i];
+ node_t *L = begin[i], *R = list_tail(&begin[i]);
```
如此可大幅降低記憶體開銷。
### 以 linux 核心風格之 API 進行改寫
> commit [688f9f](https://github.com/fennecJ/linux2024-quiz/commit/688f9f568a23f6631b3d64cfa2e397cd7ed0ec6f)
將原本的 `node_t` structure 改寫為：
```c
typedef struct __node {
long value;
struct list_head list;
} node_t;
```
並透過 `list_entry` 存取 `node_t` 的內容。
### 使 tail access 時間降低為 O(1)
> commit [369848](https://github.com/fennecJ/linux2024-quiz/commit/369848d5bf9a25fce6f2820bf0311767797c1e11)
在研讀第一週測驗題之 Timsort 時，發現該題用了一個小技巧：
在建立 run 的同時計算 run_size 並將 run_size 存在 `head->next->prev`，由於目前實作的 quick sort 不會需要用到 prev link ，因此我們可以在建立 R/L sublist 時將其對應的 tail 存在 list 的 `head->prev`，如此只要透過 begin[i]->prev 即可得到 sublist 的 tail ：
```diff
...
+ begin[0]->prev = list->prev; // set a link to tail
while (i >= 0) {
- struct list_head *L = begin[i], *R = list_tail(begin[i]);
+ struct list_head *L = begin[i], *R = L ? L->prev : NULL;
if (L != R) {
...
+ struct list_head *rtail = NULL, *ltail = NULL;
...
if(n_value > value) {
+ if(!rtail)
+ rtail = n;
n->next = right;
right = n;
} else {
+ if(!ltail)
+ ltail = n;
n->next = left;
left = n;
}
}
+ if(right)
+ right->prev = rtail;
+ if(left)
+ left->prev = ltail;
+ pivot->prev = pivot;
```
不過要留意有時候 right/left 本身可能會是 NULL ，因此在存取 `right->prev`, `left->prev`, `R->prev` 時需要先確認指標本身不是 NULL 以免遇到 segmentation fault
比較改進前後的時間差距：
> commit [706b3a](https://github.com/fennecJ/linux2024-quiz/commit/706b3a5285af447fd698ba120e9e1fa03e91dff4)
比較對長度為 100000 的 list 進行 40 次排序的時間差距：
```bash!
# ./a.out
Sort w/o tail: 0.590435
Sort w/ tail: 0.881182
```
可以看到有 $\dfrac{0.881182-0.590435}{0.881182} = 33 \%$ 的時間改進。
我也比較了長度為 10 的陣列的所有排列 （詳見文末 Misc） ：
```c
permutation statistics with arr len = 10:
...
Sort w/o tail: 0.894046
...
Sort w/ tail: 1.002126
```
有 $\dfrac{1.002126-0.894046}{1.002126} = 10 \%$ 的時間改進。
### 測驗二
#### 程式運作原理
Timsort 可視為 merge sort 的改進。
#### 改善實作
### Adaptive ShiversSort
> commit [19897f](https://github.com/fennecJ/linux2024-quiz/commit/19897fd54bf651fade3cc847242beef9a9078eda)
研讀 Timsort 的運作原理時，發現了 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-timsort) 的實作，裡面提到了 Timsort 的額外兩個變體： [Adaptive Shivers Sort](https://arxiv.org/abs/1809.08411) 以及 [powersort](https://arxiv.org/abs/1805.04154)
Adaptive Shivers Sort 改良了 Timsort 的合併策略：假設 X, Y, Z 為目前堆疊上的 Runs ，Z 為堆疊頂部 ，若 $\lfloor \log_2 X \rfloor \le \lfloor \log_2 (\max(Y, Z)) \rfloor$ ，則將 X, Y 合併。
我們可以透過 `__built_in_clz()` 快速計算 log2:
```c
static inline size_t ilog2(size_t x)
{
return 31 - __builtin_clzl(x);
}
```
修改原本的 merge_collapse 並藉由 ilog2 實作出 adaptive ShiversSort 的合併策略：
```diff!
- if ((n >= 3 &&
- run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
- (n >= 4 && run_size(tp->prev->prev->prev) <=
- run_size(tp->prev->prev) + run_size(tp->prev))) {
- if (run_size(tp->prev->prev) < run_size(tp)) {
- tp->prev = merge_at(priv, cmp, tp->prev);
- } else {
- tp = merge_at(priv, cmp, tp);
- }
+ if (n >= 3 &&
+ ilog2(run_size(tp->prev->prev)) <= ilog2(run_size_max(tp->prev, tp))) {
+ tp->prev = merge_at(priv, cmp, tp->prev);
} else if (run_size(tp->prev) <= run_size(tp)) {
size_t max_run = run_size(tp);
if(priv && ((stat_t*)priv)->max_run < max_run)
((stat_t*)priv)->max_run = max_run;
tp = merge_at(priv, cmp, tp);
}
```
### PowerSort
> [Implement of powerSort](https://github.com/fennecJ/linux2024-quiz/commit/527edb2c6db8257167e8e44501fac85465257129)
PowerSort 是另一種 Timsort 的改良，其主要概念為想像一個平衡的 binary tree 每個節點構成的 subtree 含有多少數量的節點，之後計算出目前要排序的 2 個 run 的中點連線後包含在此區間內的最小節點深度為何，在論文中將 2 個 run 對應的節點深度稱為 power，並根據後者決定是否要合併 。
留意以下說明中起點 index 設為 0，但我後來檢視其實作將起點設為 1 較合理：論文中的實作有 `- (left << 1)`，若 left 為 1 的話恰好和虛擬碼計算除法時上下同乘 2 吻合（詳見文後的 [虛擬碼和參考實作](#%E8%99%9B%E6%93%AC%E7%A2%BC%E5%92%8C%E5%8F%83%E8%80%83%E5%AF%A6%E4%BD%9C) ）
假設我們現在有長度為 28 的 list 需要排序，我們先想像其對應的 binary tree 為何：
$$
\lfloor log_2{28} \rfloor = 4
$$
因此我們可以想像一個深度為 4 的 binary tree ，分別有 power 1, 2, 3, 4
假設我們有 6 個 run {a, b, c, d, e, f}，每個 run_size 分別為：
5, 3, 3, 14, 1, 2
則我們可以開始想像他們合併後的 power 為何，首先看前兩個 run {a, b} 合併後的 power。
第一個 run {a} 的 index 為 0, 1, 2, 3, 4
第二個 run {b} 的 index 為 5, 6, 7
計算中點的公式為：
$$
begin + \lfloor \dfrac{end - begin + 1}{2} \rfloor
$$
這兩個 run 的中點分別為：
$0 + \lfloor \dfrac{4-0+1}{2} \rfloor = 2$
$5 + \lfloor \dfrac{7 - 5 + 1}{2} \rfloor = 6$
而這兩點的連線則為 (2, 6] 的區間，留意左側是開區間，不包含 2 ；而右側是閉區間，包含 6 。我們現在依序由淺到深檢視。
不同深度的 node 可表示為：
$$
nodes\_of\_depth(k)=
\begin{cases}
(\dfrac{n}{2}), & k = 1 \\
nodes\_of\_depth(k-1) \pm (\dfrac{n}{2^k}), &k > 1
\end{cases}
$$
其中 n 為 list 總長度，在這裡 n 為 28
- [ ] 深度為 1
$\dfrac{28}{2} = 14$ ，index 14 並未包含在 (2, 6] 的區間。
- [ ] 深度為 2
在 binary tree 中，有兩個深度為二的節點：
$\dfrac{28}{2} ± \dfrac{28}{2^2}$
分別是 index 7 和 index 21
index 7 和 21 皆並未包含在 (2, 6] 的區間。
- [ ] 深度為 3
$\dfrac{28}{2^3} = 3.5$ ，深度為三的 index 有：
7 - 3.5 = 3.5
7 + 3.5 = 10.5
21 - 3.5 = 17.5
21 + 3.5 = 24.5
其中 index 3.5 被包含在 (2, 6] 的區間。
因此 run {a, b} 之間的 power 就是 3 。
接下來看 run {b, c} 之間的 power 。
c 的座標為 8~10
根據前述計算， run {b} 的中點為 6 ， run{c} 的中點為：
$8 + \lfloor \dfrac{10 - 8 + 1}{2} \rfloor = 9$
而這兩點的連線則為 (6, 9] 的區間。包含深度為 2 的 index 7 ，可知其 power 為 2 。
之後依序計算出每個 run 的中點：
$mid(run_d) = 18$
$mid(run_e) = 25$
$mid(run_f) = 27$
因此
$power(run_c, run_d) = 1$, ( 9, 18] 涵蓋 14
$power(run_d, run_e) = 3$, (18, 25] 涵蓋 24.5
$power(run_e, run_f) = 4$, (25, 27] 不在深度 1 ~ 3 的範圍內，因此為最大深度 4 。
影片 [COMP526 (Fall 2023) 3-6 §3.6 Python's sorting method & Powersort](https://www.youtube.com/watch?v=exbuZQpWkQ0) 的後半部分以視覺化的方式呈現前述運算。
### 虛擬碼和參考實作
現在我們檢視 PowerSort 對應的虛擬碼:
```java!
procedure Powersort(A[0..n)){
i := 0;
runs := new Stack();
j := ExtendRunRight(A, i);
runs.push((i, j), 0);
i := j;
while(i < n){
j := ExtendRunRight(A, i);
p := power(runs.top(), (i, j), n);
while(p <= runs.top().power){
merge topmost 2 runs
}
runs.push((i, j), p);
i := j;
}
while (runs.size() >= 2)
merge topmost 2 runs
}
```
```java!
procedure power((i1, j1), (i2, j2), n){
n1 := j1 - i1
n2 := j2 - i2
// interval of (a, b]):
(float) a := (i1 + n1/2 - 1) / n;
(float) b := (i2 + n2/2 - 1) / n;
p := 0
while(1){
(int) c := round(a * pow(2, p))
(int) d := round(b * pow(2, p))
if(c != d)
return p;
p := p + 1
}
}
```
〈[Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs](https://arxiv.org/abs/1805.04154)〉提出能透過 bitwise 運算用 O(1) 時間計算出 power 的作法：
```java!
static int nodePower(int left, int right, int startA , int startB , int endB) {
int twoN = (right - left + 1) << 1; // 2*n
long l = startA + startB - (left << 1);
long r = startB + endB + 1 - (left << 1);
int a = (int) ((l << 31) / twoN);
int b = (int) ((r << 31) / twoN);
return Integer.numberOfLeadingZeros(a ^ b);
}
```
其中 left 和 right 表示要排序的起點和終點，用來計算這次排序的長度為何用以推估 binary tree 的深度 。而我們的排序固定是整個 list ，因此可以將 left, right 用一個變數 len 取代，到時候只要傳入 list 的長度即可。
以下解釋這個程式碼為何和虛擬碼等效，檢視前述虛擬碼，可以看到 a, b 的計算公式為：
```
a := (i1 + n1/2 - 1) / n;
b := (i2 + n2/2 - 1) / n;
```
其中 i1, i2 為 list1, list2 的起點，也就是 `start_A` 和 `start_B` ； n1, n2 為 list1, list2 的長度； n 為整個要排序的 list 的長度。
我們將計算 a, b 的公式上下同乘 2 ：
```
a := (2 * i1 + n1 - 2) / 2n;
b := (2 * i2 + n2 - 2) / 2n;
```
而 a, b 可對應論文實作中的 l, r
注意到 `start_B = start_A + run_size(h1) = start_A + n1`
則 `l = start_A + start_B - (left << 1)` 可寫作 `l = 2 * start_A + n1 - (left << 1)`
留意前面計算中點時假設起點 index 為 0 ，但我後來檢視其實作似乎應該將起點設為 1 較符合其 pseudo code
若 list 起點 index 為 1，則傳入 function 的 left 會是 1 ，所以 l 的計算會變成 `l = 2 * start_A + n1 - 2` ，若將其除上 (2*n) 則和虛擬碼中的 a 相等 (倒數第三行) 。
同理， r 的計算結果也和 b 相等，唯注意計算 r 的時候會多一個 +1 ：
```
r = startB + endB + 1 - (left << 1);
^^^
```
之所以會多這個 `+1` 是因為我們在檢視兩中點連線時其區間為 $(l, r]$ ，右側為閉區間， r 要被包含在區間內，而原本的虛擬碼中的 a, b 是浮點數，但 r 是整數，因此這裡要 `+1` 確保 ｒ 有被包含在區間內。
而原本虛擬碼的最後面其運算為：
$while (\lfloor a * 2 ^ p \rfloor == \lfloor b * 2 ^ p \rfloor)$
$\ \ \ \ \ p = p+1$
原本的 a 的計算為 `(2 * i1 + n1 - 2) / 2n` ，我們現在用 a' 表達 `(2 * i1 + n1 - 2)` ， b' 表達 `(2 * i2 + n2 - 2)` 。 則我們要計算的目標為
$min(p) \ s.t.$
$(a' * 2^p \ge 2n) \ or \ (b' * 2^p \ge 2n)$
或者可以說
$min(p) \ s.t.$
$\dfrac{a' * 2^p}{2n} \ge 1 \ or \ \dfrac{b' * 2^p}{2n} \ge 1$
而在計算 $\dfrac{a' * 2^p}{2n}$ 時可以視為 $\dfrac{a' * 2^p}{2n} * \dfrac{2^{31}}{2^{31}} =a' * 2^p * \dfrac{2^{31}}{2n} \div 2^{31}$
而我們的目標是找到最小的 p 值使 $2^p * \dfrac{a' * 2^{31}}{2n} \ge 2^{31}$ ，即使 `((a' << 31) / 2n) & 0x8000_0000 = true` 而 p 就可以透過 `__built_in_clz((a' << 31) / 2n)` 計算得出。 其中 `(a' << 31) / 2n` 可對照論文實作的 `int a = (int) ((l << 31) / twoN)`
而之所以最後在 clz 前要讓 `(a ^ b)`，是因為這樣得到可以找到最小的 p 。
參考論文實作出計算 `nodePower` 的函式：
```c!
static inline size_t nodePower(struct list_head *h1, struct list_head *h2,
size_t start_A, size_t len)
{
if(!h1 || !h2){
return 0;
}
size_t len_2 = len << 1;
size_t start_B = start_A + run_size(h1);
size_t end_B = start_B + run_size(h2);
size_t l = start_A + start_B;
size_t r = start_B + end_B + 1;
int a = (int)((l << 31) / len_2);
int b = (int)((r << 31) / len_2);
return __builtin_clz(a ^ b);
}
```
其中 start_A 表示在該 run 之前 stack 中的 run 總共有多長，也就是該 run 的起始 index 為何。
power sort 使用一個 stack 紀錄待合併的 run 以及這些 run 之間的 power 。 (i.e. `stack[top].power = nodePower(stack[top].run, stack[top - 1].run`)
當要進入 stack 的 run r_new 和原本 stack top 中的 run_top 計算出來的 power_new 小於目前 stack[top].power 則將 stack 中最上面兩個 run 合併，直到 stack 中的 power 小於 power_new ，將 r_new 和 power_new 推入 stack 中：
```c!
power_new = nodePower(run_top, r_new)
while (power < stack[top].power)
merge(stack[top].run, stack[top-1].run)
stack[top].run = r_new, stack[top].power = power_new;
```
之所以要確保新進來的 power 小於原本紀錄的 power ，是因為這樣能盡可能的讓串列的長度平衡。
以前述的 run a~f 為例，其 power 依序為
$power(run_a, run_b) = 3$
$power(run_b, run_c) = 2$
$power(run_c, run_d) = 1$
$power(run_d, run_e) = 3$
$power(run_e, run_f) = 4$
接著依序將 run 放入 stack 中：
將 $run_a$ 放入 stack 中， power 設為 0 ，top 更新為 $run_a$ 。
```graphviz
digraph structs {
node[shape = record]
Stack[label="{<f0>a-0}"]
top[label="top"shape=plaintext]
top->Stack:f0
}
```
嘗試放入 $run_b$ ，power 為 3 > 0 ，將 $run_b$ 放入 stack ，top 更新為 $run_b$ 。
```graphviz
digraph structs {
node[shape = record]
Stack[label="{a-0}"]
top[label="top", shape=plaintext]
tmp[label="{try_run: b-3}"]
tmp->Stack
top->Stack
}
```
```graphviz
digraph structs {
node[shape = record]
Stack[label="{b-3|a-0}"]
top[label="top", shape=plaintext]
top->Stack
}
```
嘗試放入 $run_c$ ，發現 $power(run_b, run_c) = 2 < 3$ ， power 變小表示待處理 run 的數量足以構成一個 sub tree ，有機會使 list 更加平衡，將其合併。
```graphviz
digraph structs {
node[shape = record]
Stack[label="{b-3|a-0}"]
top[label="top", shape=plaintext]
tmp[label="{try_run: c-2}"]
tmp->Stack
top->Stack
}
```
合併 stack 最靠近 top 的兩個 run ： $merge(run_a,\ run_b)$ ，更新 top 指向 power = 0 。 $run_{ab} \ 長度為 8$
```graphviz
digraph structs {
node[shape = record]
Stack[label="{ab-0}"]
top[label="top", shape=plaintext]
tmp[label="{try_run: c-2}"]
tmp->Stack
top->Stack
}
```
目前 stack 中 power = 0 < 2 ，放入 $run_c$ ，更新 top 的 power 為 2 。
```graphviz
digraph structs {
node[shape = record]
Stack[label="{c-2|ab-0}"]
top[label="top", shape=plaintext]
top->Stack
}
```
嘗試放入 $run_d$ ，其 power 為 1 < 2
```graphviz
digraph structs {
node[shape = record]
Stack[label="{c-2|ab-0}"]
top[label="top", shape=plaintext]
tmp[label="{try_run: d-1}"]
tmp->Stack
top->Stack
}
```
合併 $(run_{ab}, run_c)$ ， 更新 top ，指向 power = 0 。 $run_{abc} \ 長度為 11$
```graphviz
digraph structs {
node[shape = record]
Stack[label="{abc-0}"]
top[label="top", shape=plaintext]
tmp[label="{try_run: d-1}"]
tmp->Stack
top->Stack
}
```
目前 `stack[top].power = 0` < 1，將 $run_d$ 放入 stack ，更新 top 的 power 為 1
```graphviz
digraph structs {
node[shape = record]
Stack[label="{d-1|abc-0}"]
top[label="top", shape=plaintext]
top->Stack
}
```
嘗試放入 $run_e$，power = 3 > 1 ，直接放入並更新 power
```graphviz
digraph structs {
node[shape = record]
Stack[label="{d-1|abc-0}"]
top[label="top", shape=plaintext]
tmp[label="{try_run: e-3}"]
tmp->Stack
top->Stack
}
```
```graphviz
digraph structs {
node[shape = record]
Stack[label="{e-3|d-1|abc-0}"]
top[label="top", shape=plaintext]
top->Stack
}
```
嘗試放入 $run_f$ ， power = 4 > 3 ，直接放入並更新 power
```graphviz
digraph structs {
node[shape = record]
Stack[label="{e-3|d-1|abc-0}"]
top[label="top", shape=plaintext]
tmp[label="{try_run: f-4}"]
tmp->Stack
top->Stack
}
```
```graphviz
digraph structs {
node[shape = record]
Stack[label="{f-4|e-3|d-1|abc-0}"]
top[label="top", shape=plaintext]
top->Stack
}
```
已無其他待放入 stack 的 run ，從 top 開始往前合併：
合併 $run_e, run_f$ ， $run_{ef}$ 長度為 $1+2=3$
```graphviz
digraph structs {
node[shape = record]
Stack[label="{ef-3|d-1|abc-0}"]
top[label="top", shape=plaintext]
top->Stack
}
```
合併 $run_{ef}, run_d$ ， $run_{def}$ 長度為 $14+3=17$
```graphviz
digraph structs {
node[shape = record]
Stack[label="{def-1|abc-0}"]
top[label="top", shape=plaintext]
top->Stack
}
```
合併 $run_{def}, run_{abc}$ ， $run_{abcdef}$ 長度為 $11+17=28$
```graphviz
digraph structs {
node[shape = record]
Stack[label="{abcdef-0}"]
top[label="top", shape=plaintext]
top->Stack
}
```
至此便完成了 PowerSort 的排序。
以上合併過程的示意圖如下：
可以看到合併的過程接近一顆 binary tree，如此確保了 balance。
為了實作出 PowerSort，我指定新的 stack 用來紀錄不同 run 間的 power 以及對應的 `start_A`（紀錄 run 開頭的 index ）：
```c!
static size_t pow_stack[100][2] = {0};
// pow_stack[][0] store power
// pow_stack[][1] store start_A
```
同時對 Timsort 做了以下修改：
```diff!
stk_size = 0;
+ size_t start_A = 0;
struct list_head *list = head->next, *tp = NULL;
if (head == head->prev)
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
do {
+ start_A += run_size(tp);
/* Find next run */
struct pair result = find_run(priv, list, cmp);
result.head->prev = tp;
tp = result.head;
list = result.next;
- tp = merge_collapse(priv, cmp, tp);
+ pow_stack[stk_size][1] = start_A;
+ if(stk_size) {
+ size_t tp_power = nodePower(tp->prev,
+ tp, pow_stack[stk_size-1][1], SAMPLES);
+ tp = merge_collapse_power(priv, cmp, tp, tp_power);
+ }
stk_size++;
```
而 `merge_collapse_power` 的實作如下：
```c!
static struct list_head *merge_collapse_power(void *priv,
list_cmp_func_t cmp,
struct list_head *tp,
size_t tp_power)
{
while (pow_stack[stk_size-1][0] > tp_power) {
tp->prev = merge_at(priv, cmp, tp->prev);
}
pow_stack[stk_size][0] = tp_power;
return tp;
}
```
#### 比較三種作法
> commit [cb20658](https://github.com/fennecJ/linux2024-quiz/commit/cb2065802db67d2fef44b81b71f34bf41910b2af)
為了方便進行三種排序策略的比較，我寫了一個簡單的腳本用以作圖，
，會將「比較次數」、「合併時遇到的 max_run」，和「執行時間」予以製圖。
使用命令 `make compare` 即可自動做出上述圖片，而樣本數量和實驗次數可以修改 `def.h` 中的 `SAMPLE` 和 `EXP_CNT` 這兩個巨集。
統計比較次數：
* 黑色 `△` 為 power sort
* 土黃色 `x` 為 adaptive_ShiverSort
* 紅色 `+` 為 Timsort
以下依序比較資料大小為 `12k` `15k` `18k` `21k`
`32768 * 0.75` `32768` `32768 * 1.25` 的結果，每組結果的縱軸依序為「比較次數」、「合併時遇到的 max_run」，和「執行時間」
- [ ] 12k
- [ ] 15k
- [ ] 18k
- [ ] 21k
- [ ] $32768 \times 0.75$
- [ ] 32768
- [ ] $32768 \times 1.25$
若單以比較次數檢視，可以看到 PowerSort 和 Adaptive Shivers sort 擅長的資料大小不同，而 Adaptive Shivers sort 有一個很好的性質：他的表現很穩定，不會有突然比較很多次或很少次的情形發生；
相較之下 PowerSort 偶有需要特別多次比較的情形，目前尚未知道確切原因。
後來檢視論文實作，發現我實作的 Adaptive Shivers sort 相較論文多做了以下條件
```c!
else if (run_size(tp->prev) <= run_size(tp)) {
tp = merge_at(priv, cmp, tp);
}
```
原本的 Adaptive Shivers sort 的條件如下：
假設 X, Y, Z 為目前堆疊上的 Runs ，Z 為堆疊頂部 ，若 $\lfloor \log_2 X \rfloor \le \lfloor \log_2 (\max(Y, Z)) \rfloor$ ，則將 X, Y 合併。然而我的實作除了以上狀況會進行合併外，若 Y 的長度小於等於 Z 的長度也會進行 Y, Z 的合併，即：
```java!
if (ilog2(X) <= max(ilog2(Y), ilog2(Z))
merge(X, Y)
else if(len(Y) <= len(Z))
merge(Y, Z)
```
### 參考 [cpython](https://github.com/python/cpython/blob/main/Objects/listsort.txt?fbclid=IwAR166x-DHzj1fyNVg1j16sY5u8vi0FhFGBrEvIiA9xjhkgY2jDx4q2MLX64) 準備資料集進行實驗
> [Implement several sample generators](https://github.com/fennecJ/linux2024-quiz/commit/4aeaad0b0cd30bf372d1cf0ef71add29a00e2e07)
我參考了 cpython 中測試資料集，並實作了以下的資料集：
* sample_rnd - 產生隨機資料集
* sample_descend_strict - 產生嚴格遞減的資料集
* sample_descend - 產生遞減的資料集（允許重複的數值，如 3, 2, 2, 1 ）
* sample_ascend_strict - 產生嚴格遞增的資料集
* sample_ascend - 產生遞增的資料集（允許重複的數值，如 1, 2, 2, 3 ）
* sample_rnd3 - 產生遞增的資料集，並以三個為一組打亂順序
* sample_ascend_10 - 產生遞增資料集，並在最後 10 個插入隨機數值
* sample_rnd_1_percent - 產生遞增資料集，隨機選出 1 ％的資料將其設為隨機數值
* sample_dup - 重複產生無數個 [1, 2, 3, 4] 的資料集
* sample_same - 產生的資料集中每個數字都相同。
* sample_worst - 產生出 merge 時需要比較最多次的資料集，其實作主要參考 [When will the worst case of merge sort occur](https://stackoverflow.com/questions/24594112/when-will-the-worst-case-of-merge-sort-occur) 這篇討論。之所以以這篇作為 worst case 的實作，是因為程式 Timsort 在 merge 時的行為和 merge sort 一樣，因此我推測使用這個方法產生的資料集可以使三種演算法比較最多次數。不過根據實驗結果該假設不成立，以 $32768 \times 0.75$ 為例， worst 這個資料集的最大 comparison cnt 約為 352000 ，但 rnd 的最大 comparison cnt 約為 390000 。
此外，我在 commit [048f7f](https://github.com/fennecJ/linux2024-quiz/commit/048f7f4d1cf600114b8bcf9316835dfc1bc8913d) 中加入了 list_sort 一併進行比較，並將 list_sort 的結果以藍色的 o 表示。原本由於 ascend_strict 和 descend_strict 以及 same 在 find_run 時便會排序好而從實驗排除的三種 samples 也因為 list_sort 的引入被加回來進行實驗。
另外為了能進一步看出潛在的規律，我嘗試將每個 data_set 的 y 方向的最大值設為相同的固定值，詳細可見 commit [e607fb](https://github.com/fennecJ/linux2024-quiz/commit/e607fb45c1c8502693ab25906f90ccb628532476)
- [ ] $32768*0.75$
`Comparison cnt`
| ascend_10 | ascend |
| --------- | ---------- |
| | |
| descend | duplicate |
| ||
| rnd_3 | rnd_1% |
|||
| rnd | worst |
| ||
`Max len`
由於 list_sort 演算法本身並未涉及計算 list 長度的程式碼，但若加上計算 list 長度的邏輯於 list_sort 中會使測得的時間和比較次數不夠準確，因此 list_sort 演算法的 Max_len 在每種 sample 下皆為 0 。
| ascend_10 | ascend |
| --------- | ---------- |
| | |
| descend | duplicate |
| ||
| rnd_3 | rnd_1% |
|||
| rnd | worst |
|||
`Time`
| ascend_10 | ascend |
| --------- | ---------- |
|||
| descend | duplicate |
|||
| rnd_3 | rnd_1% |
|||
| rnd | worst |
|||
- [ ] 32768
`Comparison cnt`
| ascend_10 | ascend |
| --------- | ---------- |
|  | |
| descend | duplicate |
|  | |
| rnd_3 | rnd_1% |
| | |
| rnd | worst |
| |  |
`Max run`
| ascend_10 | ascend |
| --------- | ---------- |
| | |
| descend | duplicate |
| | |
| rnd_3 | rnd_1% |
| | |
| rnd | worst |
| | |
`Time`
| ascend_10 | ascend |
| --------- | ---------- |
| ||
| descend | duplicate |
|||
| rnd_3 | rnd_1% |
|||
| rnd | worst |
|||
- [ ] $32768*1.25$
`Comparison cnt`
| ascend_10 | ascend |
| --------- | ---------- |
| | |
| descend | duplicate |
| | |
| rnd_3 | rnd_1% |
| | |
| rnd | worst |
| ||
`Max run`
| ascend_10 | ascend |
| --------- | ---------- |
| | |
| descend | duplicate |
| | |
| rnd_3 | rnd_1% |
| | |
| rnd | worst |
|||
`Time`
| ascend_10 | ascend |
| --------- | ---------- |
|||
| descend | duplicate |
|||
| rnd_3 | rnd_1% |
|| |
| rnd | worst |
|||
:::warning
> [name=Willsonbo]
> 想請問是否有嘗試過將樣本點的數據標準化或是取標準差與峰態是否能觀察出其他性質呢？
>> [name=fennecJ]
>> 謝謝你的建議，我嘗試了你提到的數據標準化、取標準差與峰態等方法進行統計，目前沒能觀察出其它明顯的性質，因此這裡就沒有把統計結果放上來。
:::
| ascend_10 | ascend |
| --------- | ---------- |
| | |
| descend | duplicate |
| | |
| rnd_3 | rnd_1% |
| | |
| rnd | worst |
| | |
---
## 第二週測驗題
### Misc
##### TODO
- [x] 參考 [sortperf.py](https://github.com/python/cpython/blob/0c7dc494f2a32494f8971a236ba59c0c35f48d94/Tools/scripts/sortperf.py#L10) 實作對應的測試資料集並進行實驗。
- [x] 研讀 Adaptive Shivers sort 之對應論文
- 目前我的實作和 c-Adaptive Shivers sort 中將 c 設為 1 幾乎相同，唯若 Y 的長度小於等於 Z 的長度也會進行 Y, Z 的合併 （假設堆疊中最高依序為 X Y Z ，若不滿足 log(X) < max(log(Y), log(Z)) 則會根據 Y Z 的長度合併 Y Z ）
- [ ] 引入 `list_sort.c` 進行比較。
- [ ] 印出 Timsort 的 worst case，嘗試觀察其有無特定規律。
- [ ] 將圖表的最大最小值固定後畫圖看能否發現其他規律？
參考 [simplest tool to measure C program cache hit/miss and cpu time in linux?](https://stackoverflow.com/questions/10082517/simplest-tool-to-measure-c-program-cache-hit-miss-and-cpu-time-in-linux) 計算 Timsort 及其衍生的 cache miss 加以比較，看看能否透過 cache miss 解釋時間差異的原因。
實驗看看 PowerSort 的計算有無可以加速的地方，例如用 `- (1 + ilog(len)) `取代 `/ (2 * len)` ？
考量到 cache size 的限制，若在 sort 時用某種方法確保 list 合併的時的 run_size 大多低於某長度（i.e. 16KB) 可否讓比較時間減少？
為何選 16 KB ？假設一 64 位元硬體, L1 cache 大小為 512 KiB, list 中每個 node 有 2 個 4 byte 的 int (seq/val) 和 2 個 8 byte 的指標 (`next`, `prev`) ，共 24 bytes 。 512KiB/24 = 21.33 Kbytes 。16 KB 為 < 21.33 KB 中最接近的 2 的冪。（留意以上分析方式非常粗淺且可能不符真實情況）
由於看到 [vax_r](https://hackmd.io/@vax-r/linux2024-homework2#%E6%94%B9%E9%80%B2%E6%96%B9%E6%B3%95) 設計實驗檢視隨機情形下會佔用的最大深度為何並用實驗結果說明可以如何減少最大深度的佔用。但我認為該實驗方法不夠嚴謹，可能遺漏部份極端狀況。為了檢視測驗一有沒有機會進一步降低記憶體使用量，我撰寫 [permuteAndSort](https://github.com/fennecJ/linux2024-quiz/blob/6abddc780f42f44eaaf8c7bf8a5a96c44b9e4dfd/w1/q1.c#L151C6-L151C20)，作用是針對給定的陣列長度，產生所有可能的排列組合並傳入 `quick_sort` 函式確保考慮到所有情況，同時紀錄不同 max_depth 出現的次數並計算對應機率，可以透過外部傳參數給陣列長度，例如 `./a.out 3` ，就會把陣列 `[1, 2, 3]` 的所有排列組合都傳進 `quick_sort` 中，並紀錄每次進 `quick_sort` 後 begin 最大深度出現的頻率。
```bash!
# ./a.out 3
2 depth prob: 0.666667 = 4 / 6
4 depth prob: 0.333333 = 2 / 6
# ./a.out 4
2 depth prob: 0.416667 = 10 / 24
4 depth prob: 0.500000 = 12 / 24
6 depth prob: 0.083333 = 2 / 24
# ./a.out 5
2 depth prob: 0.216667 = 26 / 120
4 depth prob: 0.583333 = 70 / 120
6 depth prob: 0.183333 = 22 / 120
8 depth prob: 0.016667 = 2 / 120
# ./a.out 6
2 depth prob: 0.105556 = 76 / 720
4 depth prob: 0.563889 = 406 / 720
6 depth prob: 0.280556 = 202 / 720
8 depth prob: 0.047222 = 34 / 720
10 depth prob: 0.002778 = 2 / 720
# ./a.out 7
2 depth prob: 0.046032 = 232 / 5040
4 depth prob: 0.495635 = 2498 / 5040
6 depth prob: 0.361111 = 1820 / 5040
8 depth prob: 0.087302 = 440 / 5040
10 depth prob: 0.009524 = 48 / 5040
12 depth prob: 0.000397 = 2 / 5040
```
我嘗試將對應的機率以數學形式表達，唯目前未能體會出明顯的規律，僅能看出最大深度雖機率很低，但仍有可能發生。
Sign in with Wallet
Connect another wallet