# 2021q1 Homework1 (quiz1)
contributed by < `wiasliaw` >
###### tags: `sysprog2021`
## 進度
- [x] 重新回答並解釋運作原理
- [ ] 測試程式使用到 random，請修正「輸出結果相仿」
- [ ] 參考 Optimized QuickSort，並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
- [ ] 請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
- [ ] 研讀 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法並落實於上述 (3) 的程式碼中
## 隨堂測驗
### list_concat
```c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
left = &((*left)->next);
*left = right;
}
```
:::info
* 作答
* 從 while 迴圈和函式命名可以知道要讓 left 指向到 list 的最末端，所以選 `left = &((*left)->next)`
:::
將兩個 linked list 串接起來
* 首先看一下原本的 left 跟 right
```graphviz
digraph list_concat {
rankdir=LR;
node [shape=record];
l0 [label="{<data>L0|<ref>}"];
l1 [label="{<data>L1|<ref>}"];
l2 [label="{<data>L2|<ref>}"];
lNULL [label="NULL",shape=plaintext];
left [label="left",shape=plaintext];
r0 [label="{<data>L0|<ref>}"];
r1 [label="{<data>L1|<ref>}"];
r2 [label="{<data>L2|<ref>}"];
rNULL [label="NULL",shape=plaintext];
right [label="right",shape=plaintext];
left->l0;
l0:ref:to -> l1:data [arrowtail=dot, dir=both, tailclip=false];
l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
l2:ref:to -> lNULL [arrowtail=dot, dir=both, tailclip=false];
right->r0;
r0:ref:to -> r1:data [arrowtail=dot, dir=both, tailclip=false];
r1:ref:to -> r2:data [arrowtail=dot, dir=both, tailclip=false];
r2:ref:to -> rNULL [arrowtail=dot, dir=both, tailclip=false];
}
```
* 第 2 到 3 行: 將 left 指向到 linked list 的尾端
```graphviz
digraph list_concat {
rankdir=LR;
node [shape=record];
l0 [label="{<data>L0|<ref>}"];
l1 [label="{<data>L1|<ref>}"];
l2 [label="{<data>L2|<ref>}"];
lNULL [label="NULL",shape=plaintext];
left [label="left",shape=plaintext];
r0 [label="{<data>L0|<ref>}"];
r1 [label="{<data>L1|<ref>}"];
r2 [label="{<data>L2|<ref>}"];
rNULL [label="NULL",shape=plaintext];
right [label="right",shape=plaintext];
left->lNULL;
l0:ref:to -> l1:data [arrowtail=dot, dir=both, tailclip=false];
l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
l2:ref:to -> lNULL [arrowtail=dot, dir=both, tailclip=false];
right->r0;
r0:ref:to -> r1:data [arrowtail=dot, dir=both, tailclip=false];
r1:ref:to -> r2:data [arrowtail=dot, dir=both, tailclip=false];
r2:ref:to -> rNULL [arrowtail=dot, dir=both, tailclip=false];
}
```
* 第 4 行: 將 right 接在 left 的末端
```graphviz
digraph list_concat {
rankdir=LR;
node [shape=record];
l0 [label="{<data>L0|<ref>}"];
l1 [label="{<data>L1|<ref>}"];
l2 [label="{<data>L2|<ref>}"];
left [label="left",shape=plaintext];
r0 [label="{<data>L0|<ref>}"];
r1 [label="{<data>L1|<ref>}"];
r2 [label="{<data>L2|<ref>}"];
rNULL [label="NULL",shape=plaintext];
right [label="right",shape=plaintext];
left->r0;
l0:ref:to -> l1:data [arrowtail=dot, dir=both, tailclip=false];
l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
l2:ref:to -> r0 [arrowtail=dot, dir=both, tailclip=false];
right->r0;
r0:ref:to -> r1:data [arrowtail=dot, dir=both, tailclip=false];
r1:ref:to -> r2:data [arrowtail=dot, dir=both, tailclip=false];
r2:ref:to -> rNULL [arrowtail=dot, dir=both, tailclip=false];
}
```
### quicksort
```cpp=
void quicksort(node_t **list)
{
if (!*list)
return;
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? &right : &left, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
list_concat(&result, pivot);
list_concat(&result, right);
*list = result;
}
```
:::info
* 作答
* 從三元運算子可知比 pivot 大的要放進 AAA; 小的要放進 BBB，但是從第 22 行可以知道 left 是接在 list 前面，所以要放比 pivot 小的 node，所以 BBB 應為 `&left`，AAA 應為 `&right`。
* 串接完 left 後，再來需要先接上 pivot，最後才接 right，故選 `list_concat(&result, pivot);list_concat(&result, right)`
:::
:::danger
不要用「選擇」的思維作答，選擇題只是便於授課教師批改，你應該設想「如果要我憑空撰寫程式，該怎麼做？」
:notes: jserv
:::
實作 quick sort 演算法將 linked list 排序
1. 第 3 行: 確保 list 不是 NULL，假設原本的 list 如下
```graphviz
digraph quicksort {
rankdir=LR;
node [shape=record];
list [label="list",shape=plaintext];
l0 [label="{<data>3|<ref>}"];
l1 [label="{<data>1|<ref>}"];
l2 [label="{<data>5|<ref>}"];
l3 [label="{<data>2|<ref>}"];
l4 [label="{<data>4|<ref>}"];
list->l0
l0:ref:to -> l1:data [arrowtail=dot, dir=both, tailclip=false];
l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
l2:ref:to -> l3:data [arrowtail=dot, dir=both, tailclip=false];
l3:ref:to -> l4:data [arrowtail=dot, dir=both, tailclip=false];
}
```
2. 第 6 到 10 行:
* 取出 list 中第一個節點作為 pivot
* 剩下的 list 存於變數 `p`
```graphviz
digraph quicksort {
rankdir=LR;
node [shape=record];
list [label="p",shape=plaintext];
l0 [label="{<data>3|<ref>}"];
l1 [label="{<data>1|<ref>}"];
l2 [label="{<data>5|<ref>}"];
l3 [label="{<data>2|<ref>}"];
l4 [label="{<data>4|<ref>}"];
pivot [label="pivot",shape=plaintext];
pivot -> l0;
list->l1
l1:ref:to -> l2:data [arrowtail=dot, dir=both, tailclip=false];
l2:ref:to -> l3:data [arrowtail=dot, dir=both, tailclip=false];
l3:ref:to -> l4:data [arrowtail=dot, dir=both, tailclip=false];
}
```
3. 第 11 行: 建立兩個 linked list，用於儲存與 pivot 的值比較後的結果
```graphviz
digraph quicksort {
rankdir=LR;
node [shape=record];
left[label="left", shape=plaintext];
right[label="right", shape=plaintext];
lNULL[label="NULL",shape=plaintext];
rNULL[label="NULL",shape=plaintext];
left -> lNULL;
right -> rNULL;
}
```
4. 第 12 到 16 行:
* 依序取出 list `p` 的 node，並和 pivot 比較
* 較大的放入 right，較小的放入 left
```graphviz
digraph quicksort {
rankdir=LR;
node [shape=record];
pivot[label="pivot", shape=plaintext];
left[label="left", shape=plaintext];
right[label="right", shape=plaintext];
l0 [label="{<data>3|<ref>}"];
l1 [label="{<data>1|<ref>}"];
l2 [label="{<data>5|<ref>}"];
l3 [label="{<data>2|<ref>}"];
l4 [label="{<data>4|<ref>}"];
pivot->l0;
left->l1;
right->l2;
l1->l3[arrowtail=dot, dir=both, tailclip=false]
l2->l4[arrowtail=dot, dir=both, tailclip=false];
}
```
5. 第 18 到 19 行:
* 將已經拆開的 left 和 right 也執行 `quicksort`
* 以 right 為例重複步驟 1-4，left 以此類推
```graphviz
digraph quicksort {
label="Right'";
labelloc="t";
rankdir=LR;
node [shape=record];
pivot[label="pivot'", shape=plaintext];
left[label="left'", shape=plaintext];
right[label="right'", shape=plaintext];
l2 [label="{<data>5|<ref>}"];
l4 [label="{<data>4|<ref>}"];
NULL[label="NULL",shape=plaintext];
pivot->l2;
left->l4;
right->NULL;
}
```
6. 第 21 到 24 行: 將執行完 quicksort 的 left 和 right 與 pivot 串接起來
先執行 Right'，會得到新的 right
```graphviz
digraph quicksort {
rankdir=LR;
node [shape=record];
pivot[label="pivot", shape=plaintext];
left[label="left", shape=plaintext];
right[label="right", shape=plaintext];
l0 [label="{<data>3|<ref>}"];
l1 [label="{<data>1|<ref>}"];
l2 [label="{<data>5|<ref>}"];
l3 [label="{<data>2|<ref>}"];
l4 [label="{<data>4|<ref>}"];
pivot->l0;
left->l1;
right->l4;
l1->l3[arrowtail=dot, dir=both, tailclip=false]
l4->l2[arrowtail=dot, dir=both, tailclip=false];
}
```
再來將 left, pivot 和 right 串接起來
```graphviz
digraph quicksort {
rankdir=LR;
node [shape=record];
pivot[label="pivot", shape=plaintext];
left[label="left", shape=plaintext];
right[label="right", shape=plaintext];
l0 [label="{<data>3|<ref>}"];
l1 [label="{<data>1|<ref>}"];
l2 [label="{<data>5|<ref>}"];
l3 [label="{<data>2|<ref>}"];
l4 [label="{<data>4|<ref>}"];
pivot->l0;
left->l1;
right->l4;
l1->l3[arrowtail=dot, dir=both, tailclip=false];
l4->l2[arrowtail=dot, dir=both, tailclip=false];
l3->l0[arrowtail=dot, dir=both, tailclip=false];
l0->l4[arrowtail=dot, dir=both, tailclip=false];
}
```
7. 第 25 行: 更新 list
```graphviz
digraph quicksort {
rankdir=LR;
node [shape=record];
left[label="list", shape=plaintext];
l0 [label="{<data>3|<ref>}"];
l1 [label="{<data>1|<ref>}"];
l2 [label="{<data>5|<ref>}"];
l3 [label="{<data>2|<ref>}"];
l4 [label="{<data>4|<ref>}"];
left->l1;
l1->l3[arrowtail=dot, dir=both, tailclip=false];
l4->l2[arrowtail=dot, dir=both, tailclip=false];
l3->l0[arrowtail=dot, dir=both, tailclip=false];
l0->l4[arrowtail=dot, dir=both, tailclip=false];
}
```
---
## random
* 從 [random](https://linux.die.net/man/3/random) 的文件可以得知，如果沒有提供 seed，會自動設定 seed 為 1。
> These sequences are repeatable by calling srandom() with the same seed value. If no seed value is provided, the random() function is automatically seeded with a value of 1.
* 可以用 `srandom(time(NULL))` 提供 seed，但是 `time()` 回傳的是從 1970 年 1 月 1 號到現在的秒數，所以如果在同一秒執行多次的話還是會發現相同的輸出結果。
* [time() Reference](https://en.cppreference.com/w/c/chrono/time)
* [time_t reference](https://en.cppreference.com/w/c/chrono/time_t)
:::warning
為何是 1970 年呢？能否從歷史淵源探討這數值的設定？
:notes: jserv
:::
:::info
在 [Wikipedia](https://en.wikipedia.org/wiki/Unix_time#History) 上由提及最初的定義是從第一版「Unix Programmer's Manual」中，將 Unix 時間定義為「自 1971 年 1 月 1 日起，以六十分之一秒為單位」。這樣設計是為了符合當時 Unix 系統上的 clock rate。但是這樣設計 32 bit 的有號整數只能表示約 2.5 年。
\
${\frac{2^{32}}{60*60*60*24*365}\approx 2.25...}$
\
由於範圍有限，Unix 時間重新定義為「以一秒為一單位，並設定 1970 年 1 月 1 日為 0」。
:warning: 除了只從 Wikipedia 擷取字面描述，你嘗試研讀當時硬體規格和推測 clock rate 行為嗎？任何人 (扣除中國人) 都可查閱 Wikipedia 並複製貼上，高等教育不能只做到這樣。追根究底！
:notes: jserv
:::
* 為了修正這個問題，可以用 [entropy](https://en.wikipedia.org/wiki/Entropy_(computing)) 作為 seed。如何產生一個 entropy，我找到 `getentropy()` 或是 `getrandom()`，可以跟 Linux kernel 取得亂數。
* [初探 Linux kernel 亂數產生器](https://szlin.me/2016/10/05/%E5%88%9D%E6%8E%A2-linux-kernel-%E4%BA%82%E6%95%B8%E7%94%A2%E7%94%9F%E5%99%A8-random-generator/)
* [getrandom(2) — Linux manual page
](https://man7.org/linux/man-pages/man2/getrandom.2.html)
* [getentropy(3) — Linux manual page](https://man7.org/linux/man-pages/man3/getentropy.3.html)
:::warning
請問教授，我知道 `random` 是根據 LCG 實作，「引入其他 Pseudorandom number generator」，是指實作其他的 PRNG 演算法嗎？例如：[The Rust Rand Book](https://rust-random.github.io/book/guide-rngs.html) 上面列出的。
> 是，若能進行數學分析更好
> :notes: jserv
:::
---
## Optimized QuickSort
下方[程式碼](https://alienryderflex.com/quicksort/)出處
```cpp=
bool quickSort(int *arr, int elements)
{
#define MAX_LEVELS 1000
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R;
beg[0] = 0;
end[0] = elements;
while (i >= 0) {
L = beg[i];
R = end[i] - 1;
if (L < R) {
piv = arr[L];
if (i == MAX_LEVELS - 1)
return false;
while (L < R) {
while (arr[R] >= piv && L < R)
R--;
if (L < R)
arr[L++] = arr[R];
while (arr[L] <= piv && L < R)
L++;
if (L < R)
arr[R--] = arr[L];
}
arr[L] = piv;
beg[i + 1] = L + 1;
end[i + 1] = end[i];
end[i++] = L;
} else {
i--;
}
}
return true;
}
```
:::warning
提及上方程式碼的出處，及其目標
:notes: jserv
:::
為了了解程式運作，我在 `quickSort` 裡面值入 `printf` 以得到值會迴圈後對 arr 的改變。以下為程式碼，以及其對應輸出。
```c=
void print_arr(int *arr, int elements, char c)
{
printf("Arr(%c): ", c);
for (int i = 0; i < elements; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
bool quickSort(int *arr, int elements)
{
#define MAX_LEVELS 1000
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i = 0, L, R;
beg[0] = 0;
end[0] = elements;
while (i >= 0) {
L = beg[i];
R = end[i] - 1;
if (L < R) {
piv = arr[L];
if (i == MAX_LEVELS - 1)
return false;
printf("P:%d L:%d R:%d\n", piv, L, R);
print_arr(arr, elements, 'I');
while (L < R) {
while (arr[R] >= piv && L < R)
R--;
if (L < R)
arr[L++] = arr[R];
print_arr(arr, elements, 'R');
while (arr[L] <= piv && L < R)
L++;
if (L < R)
arr[R--] = arr[L];
print_arr(arr, elements, 'L');
}
arr[L] = piv;
beg[i + 1] = L + 1;
end[i + 1] = end[i];
end[i++] = L;
print_arr(arr, elements, 'F');
} else {
i--;
}
}
return true;
}
int main(int argc, char const *argv[])
{
int arr[] = {4, 5, 2, 1, 3};
int n = 5;
quickSort(arr, n);
return 0;
}
```
```=
P:4 L:0 R:4
Arr(I): 4 5 2 1 3
Arr(R): 3 5 2 1 3
Arr(L): 3 5 2 1 5
Arr(R): 3 1 2 1 5
Arr(L): 3 1 2 1 5
Arr(F): 3 1 2 4 5
P:3 L:0 R:2
Arr(I): 3 1 2 4 5
Arr(R): 2 1 2 4 5
Arr(L): 2 1 2 4 5
Arr(F): 2 1 3 4 5
P:2 L:0 R:1
Arr(I): 2 1 3 4 5
Arr(R): 1 1 3 4 5
Arr(L): 1 1 3 4 5
Arr(F): 1 2 3 4 5
```
根據輸出以及[網站](https://alienryderflex.com/quicksort/)，可以得知
* 第 27 行的 while 迴圈作用在調整陣列，將陣列分成比 pivot 大與比 pivot 小兩個部份。
* `beg` 和 `end` 兩個陣列紀錄了下一次調整陣列的範圍
* pivot 則是取在 `beg` 和 `end` 間的第一個
:::warning
TODO:
* graphviz 代補
* rewrite quicksort
:::
Sign in with Wallet
Connect another wallet