# 2019q3 Homework4 (quiz4)
contributed by < `kaeteyaruyo` >
## 測驗 `1`
考慮一個單向 linked list:
```cpp
typedef struct __list {
int data;
struct __list *next;
} list;
```
在不存在環狀結構的狀況下，以下函式能夠對 linked list 元素從小到大排序:
```cpp
list *sort(list *start) {
if (!start || !start->next)
return start;
list *left = start;
list *right = left->next;
LL0;
left = sort(left);
right = sort(right);
for (list *merge = NULL; left || right; ) {
if (!right || (left && left->data < right->data)) {
if (!merge) {
LL1;
} else {
LL2;
merge = merge->next;
}
LL3;
} else {
if (!merge) {
LL4;
} else {
LL5;
merge = merge->next;
}
LL6;
}
}
return start;
}
```
請補完程式碼。
:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 指出程式改進空間，特別是考慮到 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort);
3. 將上述 singly-linked list 擴充為 circular doubly-linked list 並重新實作對應的 `sort`;
4. 依循 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 程式碼的方式，改寫上述排序程式;
5. 嘗試將原本遞迴的程式改寫為 iterative 版本;
6. 將 [2019q1 第 3 週測驗題 (下)](https://hackmd.io/@sysprog/SkrVSKiU4) 提及的 XOR linked list 列入考量，也實作對應的排序程式，並比較效能和記憶體開銷;
7. 比照 [List Sort](https://arxiv.org/pdf/1310.7890.pdf) 的手法來分析前述程式 (含擴充版本) 的效能表現;
:::
### 解題
（請配合[此處](https://github.com/kaeteyaruyo/linked-list/blob/master/sort-singly.c)程式碼閱讀以下說明）
```cpp
list *sort(list *start) {
// 如果沒有 node 或只有一個 node，不必排序、直接回傳
if (!start || !start->next)
return start;
// 把 list 的第一個 node 存在 left（只有這個 node 而已)，
// 剩下的 list 存在 right
// 雖然也會動到 start，不過之後會被覆蓋，沒關係
list *left = start;
list *right = left->next;
left->next = NULL;
// 因為 left 一定只有一顆，所以進 sort 出來之後還是自己
left = sort(left);
// 遞迴一直切 right，直到某一層 left 和 right 都只剩一顆
// 就會開始排序，因此 right 會是 sort 好的尾巴部份
right = sort(right);
// merge sort，首先初始化一個 merge 儲存排序結果
// 此迴圈在 left 或 right 還有東西時會不斷執行
for (list *merge = NULL; left || right; ) {
// 如果右邊沒東西了，
// 或是兩邊都有東西但左邊比較小
// 那就把左邊存進 merge
if (!right || (left && left->data < right->data)) {
// 第一次進來的時候 merge 沒東西
// 直接以 left 取代
// 並且因為最後要回傳的是 start
// （因為 merge 的生命週期只在 for loop 以內）
// 所以也要把 start 指向 merge
// 把頭拎著，之後才可以整串回傳
if (!merge) {
start = merge = left;
} else {
// 如果不是開頭，那就把結果存在目前
// merge 的 下一位，並且往下走一步
merge->next = left;
merge = merge->next;
}
// 消耗掉了 left 的一個元素，往下走
left = left->next;
} else {
// 如果左右兩邊都有東西，而且右邊比較大
// 或是只有右邊有東西
// 那就把右邊放進 merge
// 註解類似上方，不贅述
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge = merge->next;
}
right = right->next;
}
}
// 剛剛把 merge 的頭拎著，現在可以把排好的結果回傳了
return start;
}
```
### 延伸問題
1. 解釋上述程式運作原理
原理已在上方註解中解釋。簡單來說，這是一個總是只切一個 node 下來（而不是切對半）的 merge sort。
2. 指出程式改進空間，特別是考慮到 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)
* 降低運算時間複雜度
簡單計算這個版本的時間複雜度： 若 list 有 n 個 node，因為每遞迴一次只會拆一個 node 下來，所以最深的 call stack 會高達 n 層。從最上面的 stack 往下看，每一層 stack 的排序部份總共需要進行 1, 2, 3, ... n 次的疊代，因此要排序完長度為 n 的 list，共至少需要 $1 + 2 + 3 + \text{...} + n = \frac {n(1 + n)}{2}$ 次的操作（不含前幾行常數時間的 assign 操作），複雜度為$O(n^2)$。
就這個演算法的行為來看，每一層的合併在做的動作，其實都是在幫 left 裡的唯一一個 node 找適當的位子放，其排序法本質為 [insertion sort](https://en.wikipedia.org/wiki/Insertion_sort)。
Merge sort 的精神在於 divide and conquer，每次的 divide 都應該將子問題切成平均的大小，才能最有效減少遞迴的深度，也避免不必要的重複比較子序列。
以下改良版在每次的遞迴都將 list 拆成等長的兩半，實現了運算時間複雜度為 $O(nlogn)$ 版本的 merge sort。
```cpp
list *sort(list *start)
{
if (!start || !start->next)
return start;
list *left, *right, *tmp;
left = right = tmp = start;
while (right && right->next) {
right = right->next->next;
tmp = tmp->next;
}
right = tmp->next;
tmp->next = NULL;
left = sort(left);
right = sort(right);
for (list *merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
if (!merge) {
start = merge = left;
} else {
merge->next = left;
merge = merge->next;
}
left = left->next;
} else {
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge = merge->next;
}
right = right->next;
}
}
return start;
}
```
:::warning
能否縮減第一次出現的 for 迴圈呢？
:notes: jserv
:::
:::info
我將其從 for 迴圈修改為 while 迴圈，並修改尋找 middle node 的演算法使其可以擺脫對 size 變數的依賴。但是就步數來說都是 $\frac{size}{2}$ ，並沒有明顯變快。不知這樣能否稱作縮減？
:::
將原始版本與改良版本用於排序 1000 個亂數 100 次，實測運算時間，原始版本的平均值為 2.61345 ms，改良版本為 0.17024 ms （僅記錄排序所花費的時間），的確有差了一個數量級的效能差異。
:::info
我之所以測這麼多次取平均是因為我發現每次測得的時長都不太一樣，用 shell script 跑 100 次測試時，其結果有特別的現象：
```
Elapsed time: 8.393 ms
Elapsed time: 8.548 ms
Elapsed time: 5.003 ms
Elapsed time: 3.586 ms
Elapsed time: 3.746 ms
Elapsed time: 2.689 ms
Elapsed time: 2.719 ms
Elapsed time: 2.667 ms
Elapsed time: 2.681 ms
Elapsed time: 2.557 ms
...
```
前五次總是會特別久，接下來就會跑差不多的時長，但我不清楚是為什麼...
:::
:::warning
跟 locality 有關，你可以嘗試在排序之前，從頭走訪所有的節點重複幾次，然後才真正排序
:notes: jserv
:::
* 提高存取局部性 (Locality of reference)
根據題目所提供的 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort) 當中的說法：
> For example, the tiled merge sort algorithm stops partitioning subarrays when subarrays of size S are reached, where S is the number of data items fitting into a CPU's cache. Each of these subarrays is sorted with an in-place sorting algorithm such as insertion sort, to discourage memory swaps, and normal merge sort is then completed in the standard recursive fashion.
簡單翻譯如下：
> 例如， tiled merge sort 演算法在子序列大小達到 S 時就不再繼續分割，此時這個 S 為可以完整放進 memory cache 中的元素數量。每一個大小為 S 的子序列都以在小規模時效率較好的原地排序演算法（如插入排序或是泡沫排序）進行排序，以減少 memory swap 的次數。在小型子序列排序完畢後，再以普通的遞迴型 merge sort 的方式排序完剩下的部份。
若可以找到一個恰當的 S， 便能有效的同時利用到插入排序和合併排序的優點，並且減少原始的合併排序當中 locality 不好的影響。
為了找到這個恰當的 S， 先查看一下電腦的 cache size 大概是多少
```shell
kinoe@:~$ getconf -a | grep CACHE_SIZE
LEVEL1_ICACHE_SIZE 32768
LEVEL1_DCACHE_SIZE 32768
LEVEL2_CACHE_SIZE 262144
LEVEL3_CACHE_SIZE 6291456
LEVEL4_CACHE_SIZE 0
```
level1 cache 的大小為 32K， 而此版本定義的 list 結構為
```cpp
struct __list {
int data;
struct __list *next;
};
```
大小為 16， 32768 / 16 = 2048， 因此我選擇在 1 ~ 2048 這個區間之內選擇一個最好的 S。
:::warning
但是因為 2048 次真的跑太久了...所以暫時先跑了 1024 次的版本，目前這樣已經可以看的出趨勢，有時間時會補上 2048 次的版本。
:::
以上方的版本（時間複雜度為 $O(nlogn)$ ）為基礎，加入子序列長度的檢查，一旦子序列長度小於 `MIN_SIZE`， 就直接使用原始的插入排序法（底下第五題的實作）進行排序，小的子序列排完之後，才使用合併排序法進行合併。
完整實作請參考[此處程式碼]()。
```cpp
list *sort_small(list *start){
list *curr = start->next;
start->next = NULL;
while (curr) {
list *next = curr->next;
list *pos = start, *prev = NULL;
while (pos && pos->data < curr->data) {
prev = pos;
pos = pos->next;
}
if (prev)
prev->next = curr;
else
start = curr;
curr->next = pos;
curr = next;
}
return start;
}
list *sort(list *start)
{
if (!start || !start->next)
return start;
if(list_size / subseq_num <= MIN_SIZE)
return sort_small(start);
list *left, *right, *tmp;
left = right = tmp = start;
while (right && right->next) {
right = right->next->next;
tmp = tmp->next;
}
right = tmp->next;
tmp->next = NULL;
subseq_num *= 2;
left = sort(left);
right = sort(right);
subseq_num /= 2;
for (list *merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
if (!merge) {
start = merge = left;
} else {
merge->next = left;
merge = merge->next;
}
left = left->next;
} else {
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge = merge->next;
}
right = right->next;
}
}
return start;
}
```
將上述程式碼配合此測試檔進行測試（`./rand` 為額外實作的亂數產生器）:
```bash
rm -f data.txt
touch data.txt
for i in {1..1024};
do
gcc -D MIN_SIZE=$i -o sort-optimize sort-list.c sort-optimize.c
sum=0
for j in {1..10};
do
./rand 1024 > random.txt
res=$(./sort-optimize < random.txt)
sum=`echo $sum + $res | bc`
done
avg=`echo $sum / 10 | bc -l`
printf '%d %0.3f\n' "$i" "$avg" >> data.txt
done
```
可得 `MIN_SIZE` （也就是 S ）與平均執行時間關係圖：
:::info
這個版本記錄的是排序 10 次的平均值。在上面 1024 次版本的圖中可以觀察到每隔一定的數字，執行時間就會變得異常的久。我如果使用排序 100 次的平均值的話，離群值發生的次數就會更密集，但我不知道原因是什麼...
如果是特定的 S 注定會造成離群值的話，那 10 次平均還是 100 次平均看到的結果應該會差不多才對，因此可以排除這個原因。
我猜想可能是進行測試時每隔一段時間就發生了什麼事，導致該次測試的執行時間特別久？可是也不知道能做什麼實驗來觀察Q
:::
從上面兩張圖（由於在 S < 256 處落差較緊湊，故放大顯示）可以看的出來，若撇除掉離群值，在 S > 32 之後，每當 S 翻倍，平均執行時間就會增加大約 80% 。大落差處都恰好是落在 2 的冪次的地方。
然而在 S < 16 的地方可以看的出來並不符合上述的趨勢，因為在 S 接近 1 時，實際上做的就是普通的合併排序，在 locality 上並沒有較好的表現，且比原本的合併排序多了一些 function call 的 overhead，因此執行時間反而被拖的比較長。
綜合以上實驗數據，在我的電腦上，我會選擇以 32 作為 S 的最佳解。
3. 將上述 singly-linked list 擴充為 circular doubly-linked list 並重新實作對應的 `sort`
```cpp
struct __list {
int data;
struct __list *prev, *next;
};
list *sort(list *start)
{
if (!start || start->next == start->prev)
return start;
list *left = start;
list *right = left->next;
right->prev = left->prev;
right->prev->next = right;
left->prev = left;
left->next = left;
left = sort(left);
right = sort(right);
left->prev->next = NULL;
right->prev->next = NULL;
list *merge;
for (merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
if (!merge) {
start = merge = left;
} else {
merge->next = left;
merge->next->prev = merge;
merge = merge->next;
}
left = left->next;
} else {
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge->next->prev = merge;
merge = merge->next;
}
right = right->next;
}
}
merge->next = start;
start->prev = merge;
return start;
}
```
4. 依循 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 程式碼的方式，改寫上述排序程式
由於 `list.h` 屬於 kernel space 的函式庫， user space 無法直接引用，因此我以 [G04：list](https://hackmd.io/@sysprog/rJMNq4zuH) 作業中改寫的 [list.h](https://github.com/sysprog21/linux-list/blob/master/include/list.h) 替代。
```cpp
struct __list {
int data;
struct list_head link;
};
list *sort(list *start)
{
if (!start || list_empty(&start->link) || list_is_singular(&start->link))
return start;
LIST_HEAD(left);
// To avoid unnecessary nodes duplication or movement,
// just use start as right
list_move((start->link).next, &left);
left = sort(list_entry(&left, list, link))->link;
start->link = sort(start)->link;
LIST_HEAD(merge);
while (!(list_empty(&left) && list_empty(&start->link))) {
if (list_empty(&start->link) ||
(!list_empty(&left) &&
list_entry(left.next, list, link)->data <
list_entry(start->link.next, list, link)->data)) {
list_move_tail(left.next, &merge);
} else {
list_move_tail(start->link.next, &merge);
}
}
list_splice(&merge, &start->link);
return start;
}
```
5. 嘗試將原本遞迴的程式改寫為 iterative 版本
那就是普通的 insertion sort 了。
```cpp
struct __list {
int data;
struct __list *next;
};
list *sort(list *start)
{
if (!start)
return NULL;
// Start from second node if the list has more than one node
list *curr = start->next;
// Store sorted result in *start
// At the beginning, there is one node in *start
start->next = NULL;
// Walk through the list, start from second node
while (curr) {
// Record next step
list *next = curr->next;
// Find position to insert
// We will insert curr to the middle of pos and prev
list *pos = start, *prev = NULL;
while (pos && pos->data < curr->data) {
prev = pos;
pos = pos->next;
}
// If prev is not null, which means
// the position is not at the start of the list,
// then update prev's next
if (prev) {
prev->next = curr;
}
// Else, which means the position is at the start of the list,
// then we need to update start
else {
start = curr;
}
curr->next = pos;
// Go to next node
curr = next;
}
// Return sorted result
return start;
}
```
6. 將 [2019q1 第 3 週測驗題 (下)](https://hackmd.io/@sysprog/SkrVSKiU4) 提及的 XOR linked list 列入考量，也實作對應的排序程式，並比較效能和記憶體開銷
```cpp
#define XOR(a, b) ((list *) ((unsigned long) (a) ^ (unsigned long) (b)))
struct __list {
int data;
struct __list *addr;
};
list *sort(list *start)
{
if (!start || !start->addr)
return start;
list *left = start;
list *right = start->addr;
left->addr = NULL;
right->addr = XOR(right->addr, left);
left = sort(left);
right = sort(right);
for (list *merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
list *next = XOR(NULL, left->addr);
if (next) {
next->addr = XOR(left, next->addr);
}
if (!merge) {
start = merge = left;
merge->addr = NULL;
} else {
merge->addr = XOR(XOR(merge->addr, NULL), left);
left->addr = XOR(merge, NULL);
merge = left;
}
left = next;
} else {
list *next = XOR(NULL, right->addr);
if (next) {
next->addr = XOR(right, next->addr);
}
if (!merge) {
start = merge = right;
merge->addr = NULL;
} else {
merge->addr = XOR(XOR(merge->addr, NULL), right);
right->addr = XOR(merge, NULL);
merge = right;
}
right = next;
}
}
return start;
}
```
時間效能部份統一在第七題進行比較。
而空間複雜度來說，以排序不同數量的亂數來比較：
可以發現在 xor doubly linked list 的空間使用量較小，並且隨著排序的數字數量增加，其與普通作法花費的空間比值會愈來愈趨近 67% 。這是因為他們的節點結構：
```cpp
// default doubly linked list
// sizeof(list) = 24
typedef struct __list {
int data;
struct __list *prev, *next;
} list;
// xor doubly linked list
// sizeof(list) = 16
typedef struct __list {
int data;
struct __list *addr;
} list;
```
大小正好是 $3:2$ ，因此當使用的節點愈多時，其耗費的記憶體比值應該要愈來愈接近 $\frac{2}{3}$。
7. 比照 [List Sort](https://arxiv.org/pdf/1310.7890.pdf) 的手法來分析前述程式 (含擴充版本) 的效能表現
本篇論文摘要：
* 簡述排序演算法。
* 排序演算法可大致分為比較排序演算法（如泡沫排序、插入排序和快速排序）和非比較排序演算法（如桶排序和計數排序），接著簡單比較了幾種較著名的比較排序演算法的時間複雜度。
* 本篇論文主要介紹的是一種針對 linked list 優化的比較排序演算法。其演算法有兩個部份： 插入 (insertion) 和合併 (merging)。 其中插入的運算有進行比較的動作，以線性時間來維護一個有序的 list。 而合併是針對多個 list 的動作，當元素全部插入完畢後 (原文：When we reach at the maximum limit of the number of elements， 不是很理解是指所有元素插入完畢還是說抵達一個 list 的大小上限)，會針對多個 list 進行合併，若每個 list 都已經排序好的狀態，那麼合併的速度會非常快。
* 此演算法的時間複雜度比基本的比較排序法（如泡沫排序和選擇排序）還要快上許多，並且幾乎快要達到快速排序和合併排序的速度）。
* 簡述並分析幾款較知名的排序演算法
* 泡沫排序
* 比較相鄰的兩個元素，有需要就交換。如此不斷重複比較過整個 list， 直到某一次的疊代沒有做任何的交換為止
* 在資料量很少的時候很有效率
* 最佳時間複雜度為 $O(n)$ ，發生在整個序列已排序完成時
* 平均時間複雜度為 $O(n^2)$
* 選擇排序
* 在整個未排序序列中挑最大（小）的，把他放在已排序序列的尾端，重複至未排序序列為空為止
* 在資料量大時效率很差
* 平均時間複雜度為 $O(n^2)$
* 插入排序
* 從未排序序列中一次挑選一筆資料，在整個已排序序列當中尋找他應該被擺放的位置，重複至未排序序列為空為止
* 在資料量很少的時候很有效率
* 最佳時間複雜度為 $O(n)$ ，發生在整個序列已排序完成時
* 平均時間複雜度為 $O(n^2)$
* 快速排序
* 使用 divide and conquer 的策略，在序列中選擇一個樞紐 (pivot)， 將所有比樞紐大的元素放在它一邊，比樞紐小的放在另外一邊。將此步驟重複套用在樞紐兩側的子序列中，直到兩側子序列大小皆為 1 為止。樞紐的選擇會大幅影響排序的效能
* 大多數快速排序法及其變種皆為不穩定排序
* 平均時間複雜度為 $O(nlogn)$ ，發生在元素大小呈隨機分佈時
* 最差時間複雜度為 $O（n^2）$ ，發生在序列已完全排序時
* 合併排序
* 使用 divide and conquer 的策略，將序列平均分為左右兩側等長的子序列，一直平分直到子序列長度為 1 時，再將兩兩分割的子序列依大小順序合併成一個，直到所有子序列都合併完畢為止
* 無論是最佳、平均，還是最差時間複雜度都是 $O(nlogn)$
* 介紹 list sort 演算法
* `list(n)`
* 根據總共有幾個元素 (n) 來決定總共要有幾個 list（記為 L）
* `insert(data)`
* 創一個資料是 data 的節點出來
* 從第一個 list 開始看，如果該 list 為空，就將此節點放進去，並返回
* 否則如果此節點比該 list 的頭小，就將此節點插入為新的頭，並返回
* 否則如果此節點比該 list 的尾還要大，就將此結點插入為新的尾，並返回
* 否則如果 list 的數量已經是 L 個，就將所有的 list 合併成一個
* 否則，創建一個新的 list 再把資料插進去
* `merge(current_list)`
* 從最後一個 list 開始，將當前的 list 和他前面那一個合併在一起，以遞迴的方式不斷合併到所有 list 變成一個為止
```
Example data: 8, 52, 85, 81, 18, 19, 15, 22, 28, 39
list(10) = 15
insert(8)
8
insert(52)
8 -> 52
insert(85)
8 -> 52 -> 85
insert(81)
8 -> 52 -> 85
81
insert(18)
8 -> 52 -> 85
18 -> 81
insert(19)
8 -> 52 -> 85
18 -> 81
19
insert(15)
8 -> 52 -> 85
15 -> 18 -> 81
19
insert(22)
8 -> 52 -> 85
15 -> 18 -> 81
19 -> 22
insert(28)
8 -> 52 -> 85
15 -> 18 -> 81
19 -> 22 -> 28
insert(39)
8 -> 52 -> 85
15 -> 18 -> 81
19 -> 22 -> 28 -> 39
merge()
8 -> 52 -> 85
15 -> 18 -> 81
19 -> 22 -> 28 -> 39
8 -> 52 -> 85
15 -> 18 -> 19 -> 81
22 -> 28 -> 39
8 -> 52 -> 85
15 -> 18 -> 19 -> 22 -> 81
28 -> 39
8 -> 52 -> 85
15 -> 18 -> 19 -> 22 -> 28 -> 81
39
8 -> 52 -> 85
15 -> 18 -> 19 -> 22 -> 28 -> 39 -> 81
merge()
8 -> 52 -> 85
15 -> 18 -> 19 -> 22 -> 28 -> 39 -> 81
8 -> 15 -> 52 -> 85
18 -> 19 -> 22 -> 28 -> 39 -> 81
8 -> 15 -> 18 -> 52 -> 85
19 -> 22 -> 28 -> 39 -> 81
8 -> 15 -> 18 -> 19 -> 52 -> 85
22 -> 28 -> 39 -> 81
8 -> 15 -> 18 -> 19 -> 22 -> 52 -> 85
28 -> 39 -> 81
8 -> 15 -> 18 -> 19 -> 22 -> 28 -> 52 -> 85
39 -> 81
8 -> 15 -> 18 -> 19 -> 22 -> 28 -> 39 -> 52 -> 85
81
8 -> 15 -> 18 -> 19 -> 22 -> 28 -> 39 -> 52 -> 81 -> 85
```
* 時間複雜度分析（略）
* 實驗數據
（完整測試檔請見[此處](https://github.com/kaeteyaruyo/linked-list)）
首先以排序不同數量的資料所需的時間來做圖，可以看出這些演算法大略的時間複雜度。令 dataset 大小為 1000 ~ 30000 （每次多 1000 筆資料），分別作 10 次排序並記錄平均時間，結果如下圖：
* 最快的是 `sort-optimize`。 只有此版本從演算法層面上改善了效能到 $O(nlogn)$ 的 scale， 因此可以大幅快於其它 $O(n^2)$ 的版本
* 第二快的是 `sort-iterative`， 但是已經可以稍微看的出來其執行時間是以指數速度在成長。 此版本是以疊代方式實做的插入排序法，跟其它同樣 $O(n^2)$ 的演算法相比，僅僅是少了 function call 的 overhead， 效能上就已經是遞迴版本的兩倍
* 第三快的是本題提供的原始程式碼 `sort-singly`。 從此圖也可以證實上方提到的「此實作本質其實是插入排序」的論點，其效能是以指數速度在成長的，並且因為遞迴的作法多了 function call 的成本，速度遠不如以疊代方式實作的版本
* 第四快與第五快的分別是 `sort-circular-doubly` 與 `sort-xor`，在效能上與 `sort-singly` 沒有太大差別。因為大部分的程式碼其實都差不多，唯一的差別在於切斷連結與接起連結的時候， doubly 需要做的步驟比 singly 還要多一些，而 xor doubly 又比普通的 doubly 還要更多一些（在切斷與接起連結的行為一模一樣的情況下， xor 版本需要做 xor 運算，原生版是直接賦值，所以會更慢），所以才會有些微的效能差異
* 最慢的是 `sort-linux`。 儘管這個版本的可讀性最高，程式碼最短，但也因為此版本將所有動作都包裝成 function， 所以也造成了最多的 overhead。 值得注意的是，此版本的 function 其實是static void function， 也就是說，在有進行最佳化的情況下，函式主體應該會被內嵌進 call 它的地方。因此我們改用 `-O3` 的最佳化等級來編譯看看，結果如下：
可以看到最佳化之後， `sort-linux` 的效能其實與 `sort-singly` 已經沒有太大差別。
:::warning
TODO: 參照 [kdb](https://github.com/hoang-khoi/kdb) 的實作手法，允許對不同的資料結構 (或變種) 進行大範圍的資料測試，從而理解整體的效能分佈，例如裡頭 `Linked-list as a "lookup table"`
:notes: jserv
:::
## 參考資料
* [How to measure time in milliseconds using ANSI C? - Stack Overflow](https://stackoverflow.com/questions/361363/how-to-measure-time-in-milliseconds-using-ansi-c)
* [Insertion sort - Wikipedia](https://en.wikipedia.org/wiki/Insertion_sort)
* [XOR linked list - Wikipedia](https://en.wikipedia.org/wiki/XOR_linked_list)
* [Makefile: Same Rule for multiple Targets - Stack Overflow](https://stackoverflow.com/questions/19259108/makefile-same-rule-for-multiple-targets)
* [gettimeofday returns a negative value - Stack Overflow](https://stackoverflow.com/questions/10301106/gettimeofday-returns-a-negative-value)
* [gunplot語法解說和範例 - Hackmd](https://hackmd.io/@sysprog/Skwp-alOg?type=view)
Sign in with Wallet
Connect another wallet