# 2021q1 Homework1 (quiz1)
contributed by < `Edwardz43` >
> [第一周測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)
## LLL = ?
```c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
LLL;
*left = right;
}
```
## AAA = ? BBB = ?
```c=
...
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 ? AAA : BBB, n);
}
quicksort(&left);
quicksort(&right);
...
```
## CCC = ?
```c=
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 *result = NULL;
list_concat(&result, left);
CCC;
*list = result;
}
```
---
## 原理
```graphviz
digraph g {
nodesep=.5
rankdir=LR;
node [shape = record,width=.5,height=.1];
store0 [label=" {<n>4 | <p>}"];
store1 [label=" {<n>2 | <p>}"];
store2 [label=" {<n>5 | <p>}"];
store3 [label=" {<n>3 | <p>}"];
store4 [label=" {<n>1 | <p>}"];
store5 [label=" {<n>7 | <p>}"];
store6 [label=" {<n>6 | <p>}"];
store0:p -> store1:n;
store1:p -> store2:n;
store2:p -> store3:n;
store3:p -> store4:n;
store4:p -> store5:n;
store5:p -> store6:n;
}
```
---
```graphviz
digraph g {
nodesep=.5
rankdir=LR;
node [shape = record,width=.5,height=.1];
pivot [label=" pivot | {<n> | <p>}"];
store0 [label=" {<n>4 | <p>}"];
store1 [label=" {<n>2 | <p>}"];
store2 [label=" {<n>5 | <p>}"];
store3 [label=" {<n>3 | <p>}"];
store4 [label=" {<n>1 | <p>}"];
store5 [label=" {<n>7 | <p>}"];
store6 [label=" {<n>6 | <p>}"];
store0:n -> pivot:n;
store0:p -> store1:n [style=dotted];
store1:p -> store2:n;
store2:p -> store3:n;
store3:p -> store4:n;
store4:p -> store5:n;
store5:p -> store6:n;
}
```
* 先以第一個 `node` 作為 `pivot`，將 list 拆成兩個部份
---
```graphviz
digraph g {
nodesep=.5
node [shape = record,width=.5,height=.1];
rankdir=LR;
pivot [label=" pivot |{<n>4 | <p>}"];
// left
left0 [label=" left | {<n> | <p>}"]
store1:n -> left0:n [style=bold, color=blue];
store1 [label=" {<n>2 | <p>}"];
store2 [label=" {<n>5 | <p>}"];
store3 [label=" {<n>3 | <p>}"];
store4 [label=" {<n>1 | <p>}"];
store5 [label=" {<n>7 | <p>}"];
store6 [label=" {<n>6 | <p>}"];
store1:p -> store2:n [style=dotted];
store2:p -> store3:n;
store3:p -> store4:n;
store4:p -> store5:n;
store5:p -> store6:n;
store1:n -> pivot:n [color=red, dir=both,label="compare", fontcolor=darkgreen];
}
```
* 因為 2 < 4 ， 所以將 2 放到 `left`
---
```graphviz
digraph g {
nodesep=.5
node [shape = record,width=.5,height=.1];
rankdir=LR;
pivot [label=" pivot | {<n>4 | <p>}"];
// left
left0 [label=" left | {<n>2 | <p>}"];
// right
right0 [label=" right | {<n> | <p>}"];
store2:n -> right0:n [style=bold, color=blue];
store2 [label=" {<n>5 | <p>}"];
store3 [label=" {<n>3 | <p>}"];
store4 [label=" {<n>1 | <p>}"];
store5 [label=" {<n>7 | <p>}"];
store6 [label=" {<n>6 | <p>}"];
store2:p -> store3:n [style=dotted];
store3:p -> store4:n;
store4:p -> store5:n;
store5:p -> store6:n;
store2:n -> pivot:n [color=red, dir=both, label="compare", fontcolor=darkgreen];
}
```
* 5 -> `right`
---
```graphviz
digraph g {
nodesep=.5
node [shape = record,width=.5,height=.1];
rankdir=LR;
pivot [label=" pivot | {<n>4 | <p>}"];
// left
left0 [label=" left | {<n>2 | <p>}"];
left1 [label=" {<n> | <p>}"];
left0:p -> left1:n;
store3:n -> left1:n [style=bold, color=blue];
// right
right0 [label=" right | {<n>5 | <p>}"];
store3 [label=" {<n>3 | <p>}"];
store4 [label=" {<n>1 | <p>}"];
store5 [label=" {<n>7 | <p>}"];
store6 [label=" {<n>6 | <p>}"];
store3:p -> store4:n[style=dotted];
store4:p -> store5:n;
store5:p -> store6:n;
store3:n -> pivot:n [color=red, dir=both, label="compare", fontcolor=darkgreen];
}
```
* 3 -> `left`
---
```graphviz
digraph g {
nodesep=.5
node [shape = record,width=.5,height=.1];
rankdir=LR;
pivot [label=" pivot | {<n>4 | <p>}"];
store4 [label=" {<n>1 | <p>}"];
store5 [label=" {<n>7 | <p>}"];
store6 [label=" {<n>6 | <p>}"];
// left
left0 [label=" left | {<n>2 | <p>}"];
left1 [label=" {<n>3 | <p>}"];
left2 [label=" {<n> | <p>}"];
left0:p -> left1:n;
left1:p -> left2:n;
store4:n -> left2:n [style=bold, color=blue];
// right
right0 [label=" right | {<n>5 | <p>}"];
store4:p -> store5:n [style=dotted];
store5:p -> store6:n;
store4:n -> pivot:n [color=red, dir=both, label="compare", fontcolor=darkgreen];
}
```
* 1 -> `left`
---
```graphviz
digraph g {
nodesep=.5
node [shape = record,width=.5,height=.1];
rankdir=LR;
pivot [label=" pivot | {<n>4 | <p>}"];
store5 [label=" {<n>7 | <p>}"];
store6 [label=" {<n>6 | <p>}"];
// left
left0 [label=" left | {<n>2 | <p>}"];
left1 [label=" {<n>3 | <p>}"];
left2 [label=" {<n>1 | <p>}"];
left0:p -> left1:n;
left1:p -> left2:n;
// right
right0 [label=" right | {<n>5 | <p>}"];
right1 [label="{<n> | <p>}"];
right0:p -> right1:n;
store5:n -> right1:n [style=bold, color=blue];
store5:p -> store6:n [style=dotted];
store5:n -> pivot:n [color=red, dir=both, label="compare", fontcolor=darkgreen];
// [arrowhead=vee, dir=both, tailclip=true, arrowsize=1]
}
```
* 7 -> `right`
---
```graphviz
digraph g {
nodesep=.5
node [shape = record,width=.5,height=.1];
rankdir=LR;
pivot [label=" pivot | {<n>4 | <p>}"];
store6 [label=" {<n>6 | <p>}"];
// left
left0 [label=" left | {<n>2 | <p>}"];
left1 [label=" {<n>3 | <p>}"];
left2 [label=" {<n>1 | <p>}"];
left0:p -> left1:n;
left1:p -> left2:n;
// right
right0 [label=" right | {<n>5 | <p>}"];
right1 [label=" {<n>7 | <p>}"];
right2 [label=" {<n> | <p>}"];
right0:p -> right1:n;
right1:p -> right2:n;
store6:n -> right2:n [style=bold, color=blue];
store6:n -> pivot:n [color=red, dir=both, label="compare", fontcolor=darkgreen];
}
```
* 6 -> `right`
---
```graphviz
digraph g {
nodesep=.5
node [shape = record,width=.5,height=.1];
rankdir=LR;
subgraph cluster0 {
style=filled;
color=lightgrey;
label = "right -> quicksort(right)";
// right
right0 [label=" right | {<n>5 | <p>}"];
right1 [label=" {<n>7 | <p>}"];
right2 [label=" {<n>6 | <p>}"];
right0:p -> right1:n;
right1:p -> right2:n;
}
pivot [label=" pivot | {<n>4 | <p>}"];
subgraph cluster1 {
style=filled;
color=lightgrey;
label = "left -> quicksort(left)";
left0 [label=" left | {<n>2 | <p>}"];
left1 [label=" {<n>3 | <p>}"];
left2 [label=" {<n>1 | <p>}"];
left0:p -> left1:n;
left1:p -> left2:n;
}
}
```
之後會透過遞迴，將得到的 `left` 與 `right` 再去執行 `quicksort`，直到排序結束，最後再將 `left` 、 `pivot` 、 `right` 經由 `list_concat` 合併
```graphviz
digraph g {
nodesep=.5
node [shape = record,width=.5,height=.1];
rankdir=LR;
left0 [label=" left | {<n>1 | <p>}"];
left1 [label=" {<n>2 | <p>}"];
left2 [label=" {<n>3 | <p>}"];
pivot [label=" pivot | {<n>4 | <p>}"];
right0 [label=" right | {<n>5 | <p>}"];
right1 [label=" {<n>6 | <p>}"];
right2 [label=" {<n>7 | <p>}"];
left0:p -> left1:n;
left1:p -> left2:n;
left2:p -> pivot:n [style=bild, color=blue,label="concat"];
pivot:p -> right0:n [style=bild, color=blue,label="concat"];
right0:p -> right1:n;
right1:p -> right2:n;
}
```
根據以上的流程， `list_add_node_t` 的功能就是將 `last element of left` 的 `next` 接到 `right` 的 `first element`，所以 `LLL` 的內容是將 pointer to pointer to `left` (==node_t ** left==) 指向到 last element
```c=
...
while (*left)
left = &((*left)->next);
...
```
因為題目的要求為遞增排序，所以當 `n->value` > value of `pivot` 時，要把 n 放到 `right`(AAA) ， 反之則是放到 `left`(BBB)
```c=
...
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? &right : &left, n);
}
...
```
最後透過 `list_concat` 合併時， 依序是 `left` -> `pivot` -> `right`
```c=
...
node_t *result = NULL;
list_concat(&result, left);
// CCC
list_concat(&result, pivot);
list_concat(&result, right);
*list = result;
...
```
---
## 修正隨機問題
根據 `man-pages` [rand(3)](https://man7.org/linux/man-pages/man3/rand.3.html) 的說明
>The rand() function returns a pseudo-random integer in the range
0 to RAND_MAX inclusive (i.e., the mathematical range[0, RAND_MAX]).
The srand() function sets its argument as the seed for a new
sequence of pseudo-random integers to be returned by rand().
These sequences are repeatable by calling srand() with the same
seed value.
If ==no seed== value is provided, the rand() function is
==automatically seeded with a value of 1==.
所以直接使用 rand() 會出現相同的結果
改進的辦法就是利用 `srand()` 餵給它不同的 `seed`
```c=
...
seed = atoi(argv[1]);
nloops = atoi(argv[2]);
srand(seed);
for (int j = 0; j < nloops; j++) {
r = rand();
printf("%d\n", r);
}
...
```
但是這邊又衍生了另一個問題：如何確保給定的 `seed` 是~~隨機~~不同的？查了一下比較常見的作法是利用 `time()` function 回傳的 timestamp 當作 `seed`
```c=
srand(time(NULL));
```
實際測試的結果，可以產出不同的隨機數列
```c=
srand(time(NULL));
for (int i = 0; i < 10; i++) {
printf("%d ", rand());
}
printf("\n");
```
```shell=
$ ./rand
2077753944 2041748551 282386150 900842139 643100466 2047655698 1595456208 76206106 1886978341 1804387094
$ ./rand
732364144 1383447097 1435339213 469217589 658707237 563652290 333147698 981652687 2055214820 1302689626
```
不過這邊又發現了一個問題：因為 `time()` 回傳的 timestamp 單位是秒(second)，所以如果在很短的時間內重複呼叫，會使得 `srand()` 吃到同樣的 seed 而導致產出一樣的隨機數列
比較簡易的解決方案就是提高 timestamp 的解析度：用 `microsecond` 取代 `second`
```c=
long long current_timestamp()
{
struct timeval tv;
// get current time
gettimeofday(&tv, NULL);
// calculate microseconds
long long microseconds =
tv.tv_sec * 1000000 + tv.tv_usec;
return microseconds;
}
```
```c=
struct timeval
{
__time_t tv_sec; /* Seconds. */
__suseconds_t tv_usec; /* Microseconds. */
};
```
`timevl` 包含了兩個 member : 當下時間的秒 (tv_sec) 與 微秒(tv_usec)，解析度可提高 $10^6$
> $1 second = 10^6 microseconds$
`gettimeofday()` 可以取得當下的 time value ，經過簡單的運算所取得的 timestamp，足以滿足目前的需求
```c=
int main(int argc, char **argv)
{
...
srand(current_timestamp());
while (count--)
list = list_make_node_t(list, rand() % 1024);
...
}
```
:::info
keyword: Address Space Layout Randomization
:::
### References
[Performance and Entropy of Various ASLR Implementations](http://pages.cs.wisc.edu/~riccardo/736finalpaper.pdf)
---
## Optimized QuickSort without recursion
> TODO
###### tags: `week1` `sysprog2021q1`
Sign in with Wallet
Connect another wallet