---
tags: 進階電腦系統理論與實作
---
# 2020q3 Homework1 (quiz1)
contributed by < `RinHizakura` >
[2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
[GitHub](https://github.com/RinHizakura/linked-list)
## 程式運作原理
:::warning
注意圖中的所有 `head` 是以 main(caller) 裡的 `head` pointer 的角度，而不是做為參數的 pointer to pointer 的 `head`
:::
### `add_entry`
```cpp
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = malloc(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
assert(new_node);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
}
```
把一個 node 加到 linked list 的尾端:
* 這裡使用到了 pointer to pointer 的技巧，indirect 是指向 head pointer 的 pointer
* 首先，透過 malloc 建立一個新的 node 空間，填入 value 欄位後將其指向 NULL(因為 new_node 會放在尾端)
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=new_node]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
indirect[shape=plaintext,fontcolor=blue]
indirect->head->A
}
A->B->C->NULL1
D->NULL2
}
```
* 透過 assert 去檢查 new_node 是否為 NULL(malloc 是否失敗)，因此 `AA1` = `assert(new_node)`
* 我認為這個 `assert` 的位置需要調整！詳細請閱讀往下的 **Issue 1: where to use assert**
* indirect 如果指向的位置上不是 NULL，就往指向位置存放的 node 的下一個 node 指去，直到指到的位置上是放 NULL
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue];
n[label="(addr of C's next)",shape=plaintext]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=new_node]
NULL1[label=NULL,shape=plaintext]
NULL2[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
indirect->n->NULL1
}
A->B->C->NULL1
D->NULL2
}
```
* 這個位置就是 new_node 要放的地方，所以 `AA2` = `*indirect = new_node`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue];
n[label="(addr of C's next)",shape=plaintext]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=new_node]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
indirect->n->D
}
A->B->C->D->NULL1
}
```
#### Issue 1: where to use assert
為了模擬 malloc 出 NULL 的情境，設計了一個總是回傳 NULL 的 MALLOC，假裝配置記憶體失敗。
```cpp=
static inline node_t *MALLOC(size_t size){
return NULL;
}
void add_entry(node_t **head, int new_value)
{
node_t **indirect = head;
node_t *new_node = MALLOC(sizeof(node_t));
new_node->value = new_value;
new_node->next = NULL;
assert(new_node);
while (*indirect)
indirect = &(*indirect)->next;
*indirect = new_node;
}
```
意料之中，上面 `add_entry` 的寫法在 `assert` 前就有透過 `new_node->value = new_value` 去存取 new_node，因此會產生 Segmentation fault。
> Segmentation fault (core dumped)
從 valgrind 偵測的結果來看，問題也確實是如此 (linked_list.c:16 等同上面程式的第 11 行)。
```
==108297== Invalid write of size 4
==108297== at 0x1092C4: add_entry (linked_list.c:16)
==108297== by 0x1090F7: main (main.c:10)
==108297== Address 0x0 is not stack'd, malloc'd or (recently) free'd
```
至於如果改成把 `assert` 接續在 `malloc` 之後，測試後會得到以下結果。
```
exec: linked_list.c:16: add_entry: Assertion `new_node' failed.
Aborted (core dumped)
```
從兩個結果的差異來思考。首先，如果我們的目的只是希望整個 linked list 的操作符合預期，並且在發生錯誤時 shut down，那麼是不是放不放 `assert` 都沒關係呢？(反正 dereference pointer 會發生 exception?)
為此我們需要了解 NULL pointer 的一些細節，在 C 語言規格書中對 NULL pointer 的定義是：
> **6.3.2.3 Pointers:**
> An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.
因此，`int* ptr = (int *)0;` 或者 `int* ptr = (int *)(void *)0` 都同等於是 NULL pointer。而規格書裡也有提到：
> Conversion of a null pointer to another pointer type yields a null pointer of that type.
Any two null pointers shall compare equal.
所以下面的程式會印出 `equal!!`。
```c=
int main()
{
int* ptr = (int *)0;
int* ptr2 = (int *)(void *)0;
if(ptr == ptr2)
printf("equal!!\n");
return 0;
}
```
而 dereference 的操作，在規格書裡如是說：
> **6.5.3.2 Address and indirection operators**
> If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined
Deference NULL pointer 是 undefined behavior。在 [Null pointer](https://en.wikipedia.org/wiki/Null_pointer#cite_note-2) 中也提到，在某些系統上 dereference NULL pointer 是可能會繼續執行然而導致非預期的結果的。所以如果想要即時的掌握錯誤，`assert` 應該接續在 malloc 之後，才能保證即時的檢查到錯誤。
#### Issue 2: when to use assert?
我們在 [lab0](https://hackmd.io/SIIKhe9FT-S1fFVV_7Kg5g) 的時候，以類似的插入節點的 function `q_insert_head` 為例，對 malloc 的檢查是用 `if` 分支，雖然也對 malloc 的失敗做了處理，但與 `assert` 程式會保持 linked list 的原始模樣但程式不會直接 crash。
```c=
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
```
那麼在真實的應用上，在甚麼情境下使用哪個方法可能會比較好呢？
assert 的中文是**斷言**，因此，程式碼的 assert 就像是在對閱讀程式碼的人說 「這一行 statement 必定是這種情況」，當出現程式撰寫者預期外的情況，則必須要回頭來檢查錯誤。因此，assert 基本就是一個比較粗糙、但方便的 debug 工具，我們可以在編譯中加上 `-DNDEBUG` 將其變成 no operation。
使用 if 檢查的情況，則比較像是我們預期使用程式的人可能誤用(錯誤的參數等)，程式可以容忍使用者犯傻，告訴他 「這個操作不合法喔」，然後維持正確的狀態讓程式往下執行。
(議題細節待詳細補充)
#### My conclusion
因此，結論來說，以上面的程式而言，如果我們的目的只是希望在發生錯誤時 shut down，考慮到 dereference 也有可能不會發生 exception，所以 `assert` 的存在仍然是必要的，至於 `assert` 該放在原本的位置或者接續在 `malloc` 之後，以此為目的的話都可以。但是如果我們想要在出錯時可以直接抓到錯誤之處，因為 Segmentation fault 並不會直接反映出錯的地方，或者考慮到使用 `assert` 的邏輯的話，我會認為接續在 `malloc` 之後才是正確的。
### `find_entry`
```cpp
node_t *find_entry(node_t *head, int value)
{
node_t *current = head;
for (; current && current->value != value; current = current->next)
/* interate */;
return current;
}
```
從 head 開始，逐步尋找符合儲存的值為 `value` 的 node。
### `remove_entry`
```cpp
void remove_entry(node_t **head, node_t *entry)
{
node_t **indirect = head;
while ((*indirect) != entry)
indirect = &(*indirect)->next;
*indirect = entry->next;
free(entry);
}
```
移除目標的 entry。pointer to pointer 的使用手法類似前面，假設初始為下圖，而 `head` 是 A，`entry` 是 C。
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue];
n[shape=plaintext,label="entry"]
m[shape=plaintext,label="(addr of B's next)"]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=D]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
indirect->head->A
}
{
rank="same";
m->C
}
n->C
A->B->C->D->NULL1
}
```
* 一直前進，直到找到 `entry`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue];
n[shape=plaintext,label="entry"]
m[shape=plaintext,label="(addr of B's next)"]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=D]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
indirect->m->C
}
n->C
A->B->C->D->NULL1
}
```
* 把 `B->next` 下的節點換成 D，於是就變成了
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
indirect[shape=plaintext,fontcolor=blue];
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
C[label=C]
D[label=D]
NULL1[label=NULL,shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
n[shape=plaintext,label="entry"]
m[shape=plaintext,label="(addr of B's next)"]
n->C
indirect->m->D
}
A->B->D->NULL1
}
```
* 最後再把 `entry` 指向的節點 C 釋放掉，大功告成
### `swap_pair`
```cpp
node_t *swap_pair(node_t *head)
{
for (node_t **node = &head; *node && (*node)->next; node = &((*node)->next->next)) {
node_t *tmp = *node;
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
}
return head;
}
```
將節點兩兩交換(第 0 個跟第 1 個交換、第 2 個跟第 3 個......)。下面以前兩個 node 的操作來解釋 swap。
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
n[shape=plaintext,label="node"]
n->head->A
}
A->B->C->NULL1
}
```
* 首先 `node_t *tmp = *node`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red,label="head(tmp)"]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
n[shape=plaintext,label="node"]
n->head->A
}
A->B->C->NULL1
}
```
* 然後，把 node 指到的地址換成下一個節點的地址。因此 `BB2` 會是 `*node = (*node)->next;` 。注意到因為交換的是節點的位址，因此第一個 iteration 的這一步會把 head 的位址變成 B 的位址，也就是讓 head 指向變成開頭的 B。
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext]
n[shape=plaintext,label="node"]
m[shape=plaintext,label="head\n(original addr of A's next)",fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
tmp->A
}
{
rank="same";
n->m->B
}
A->B->C->NULL1
}
```
* 再來是 `tmp->next = (*node)->next`
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext,label="tmp"]
n[shape=plaintext,label="node"]
m[shape=plaintext,label="head\n(original addr of A's next)",fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
tmp->A
}
{
rank="same";
n->m->B
}
B->C
A->C->NULL1
}
```
* 最後是 `(*node)->next = tmp`。
```graphviz
digraph graphname{
node[shape=box]
tmp[shape=plaintext,label="tmp"]
n[shape=plaintext,label="node"]
m[shape=plaintext,label="head\n(original addr of A's next)",fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
tmp->A
}
{
rank="same";
n->m->B
}
B->A->C->NULL1
}
```
* 把 A、B 處理完後，要把 node 指向的位址換到 C 去。所以 `BB1` 的答案是 `node = &((*node)->next->next)`，選項裡好像沒有正確答案?
```graphviz
digraph graphname{
node[shape=box]
n[shape=plaintext,label="node"]
m[shape=plaintext,label="head",fontcolor=red]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
m->B
}
{
rank="same";
n->C
}
B->A->C->NULL1
}
```
:::warning
原有選項 `node = &(*node)->next->next` 不能執行嗎？
:notes: jserv
:::
> 可以！ 當初可能弄錯了以為沒有正確答案 XD
>
> 事實上根據 C 語言規格書
> `&` (address of) 是屬於 6.5.3 Unary operators
> `->` 則是屬於 6.5.2 Postfix operators
>
> 又在規格書第 76 頁中有提到：
> The syntax specifies the precedence of operators in the evaluation of an expression, which is the same as the order of the major subclauses of this subclause, highest precedence first.
>
> The exceptions are cast expressions (6.5.4) as operands of unary operators
> (6.5.3), and an operand contained between any of the following pairs of operators: grouping parentheses () (6.5.1), subscripting brackets [] (6.5.2.1), function-call parentheses () (6.5.2.2), and the conditional operator ? : (6.5.15).
>
> 因此在章節比較前面的 `->` 優先權會大於 `&`，所以 `&((*node)->next->next)` 和 `node = &(*node)->next->next` 是等價的，所以答案是選項 ( e ) !
>
> 也可以透過下面的程式來驗證這點。
```c=
void test(node_t *head)
{
node_t **node = &head;
node = &(*node)->next->next;
printf("test: %ld, value: %d\n", (unsigned long)node, (*node)->value);
}
void test_2(node_t *head)
{
node_t **node = &head;
node = &((*node)->next->next);
printf("test_2: %ld, value: %d\n", (unsigned long)node, (*node)->value);
}
int main ()
{
node_t *head = NULL;
add_entry(&head, 1);
add_entry(&head, 2);
add_entry(&head, 3);
test(head);
test_2(head);
}
```
> 得到結果：
```
test: 94834115597000, value: 3
test_2: 94834115597000, value: 3
```
### `reverse`
```c=
node_t *reverse(node_t *head)
{
node_t *cursor = NULL;
while (head) {
node_t *next = head->next;
head->next = cursor; cursor = head;
head = next;
}
return cursor;
}
```
將 linked list 倒置。一開始 linked list 大概如下圖：
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
NULL[shape=plaintext] cursor[shape=plaintext,label="cursor"]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
head->A
}
cursor->NULL
A->B->C->NULL1
}
```
* 首先 ` node_t *next = head->next;`
```graphviz
digraph graphname{
node[shape=box]
head[shape=plaintext,fontcolor=red]
cursor[shape=plaintext,label="cursor"]
NULL[shape=plaintext]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
head->A
}
{
rank="same";
next[shape=plaintext]
next->B
}
cursor->NULL
A->B->C->NULL1
}
```
* cursor 就是回頭的節點，因此 `CCC` 應該為 `head->next = cursor; cursor = head`
```graphviz
digraph graphname{
node[shape=box]
cursor[shape=plaintext,label="cursor(head)",fontcolor=red]
NULL[shape=plaintext]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
cursor->A
}
{
rank="same";
next[shape=plaintext]
next->B
}
A->NULL
A->B->C->NULL1
}
```
* 最後是 `head = next;`。後面就重覆前面的步驟，把 linked list 所指的方向逆轉。最後 cursor 會指向原本 linked list 的最尾端，也就是新的 `head`，return 之。
```graphviz
digraph graphname{
node[shape=box]
cursor[shape=plaintext,label="cursor"]
NULL[shape=plaintext]
rankdir=LR
{
rankdir = LR
A[label=A]
B[label=B]
NULL1[label="...",shape=plaintext]
}
{
rank="same";
cursor->A
}
{
rank="same";
next[shape=plaintext,label="head(next)",fontcolor=red]
next->B
}
A->NULL
A->B->C->NULL1
}
```
## 改寫為 pointer to pointer
### Bonus: `delete_list`
為了方便做實驗時更新 linked list 且避免 memory leak，實作一個釋放 linked list 上所有節點的 function。
```cpp
void delete_list(node_t **head) {
while (*head) {
node_t *next = (*head)->next;
free(*head);
*head = next;
}
}
```
### `swap_pair`
由於原本的 `node` 已經是在對 pointer to pointer 做操作，所以可以簡單的改寫 `swap_pair` 成：
```cpp
void swap_pair(node_t **head)
{
for (; *head && (*head)->next;
head = &((*head)->next->next)) {
node_t *tmp = *head;
*head = (*head)->next;
tmp->next = (*head)->next;
(*head)->next = tmp;
}
}
```
考慮到我們的 linked list 結構比較簡單，node 裡只有下一個的位置和儲存的數值，這裡有另外一個也可以做到結果相同的 swap 方法。我們可以只是把節點中的 `value` 做交換。
```cpp
#define XORSWAP_UNSAFE(a, b) \
((a) ^= (b), (b) ^= (a), \
(a) ^= (b)) /* Doesn't work when a and b are the same object - assigns zero \
(0) to the object in that case */
#define XORSWAP(a, b) \
((&(a) == &(b)) ? (a) /* Check for distinct addresses */ \
: XORSWAP_UNSAFE(a, b))
void swap_pair_by_value(node_t **head)
{
for (; *head && (*head)->next;
head = &((*head)->next->next)) {
XORSWAP((*head)->value, (*head)->next->value);
}
}
```
#### Bonus: 兩個方法的執行時間差異
我想要知道哪個方法可能運行的比較快，所以設計了一段測試程式。考慮到 cache 可能的影響，所以每次 swap 的都是一個新的 linked list，並且透過 `taskset` 指令僅在單核上運作。
```c=
for (int num = 10; num < 2000; num++){
for (int i=0; i<num; i++){
add_entry(&head, (rand() % 1000));
}
struct timespec tt1, tt2;
clock_gettime(CLOCK_MONOTONIC, &tt1);
swap_pair(&head);
clock_gettime(CLOCK_MONOTONIC, &tt2);
long long time = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
(long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);
delete_list(&head);
for (int i=0; i<num; i++){
add_entry(&head, (rand() % 1000));
}
clock_gettime(CLOCK_MONOTONIC, &tt1);
swap_pair_by_value(&head);
clock_gettime(CLOCK_MONOTONIC, &tt2);
long long time2 = (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
(long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);
printf("%d, %lld, %lld\n", num, time, time2);
delete_list(&head);
}
```
考慮到可能的誤差，因此我通過簡單的統計方法 [standard deviation around the mean](https://en.wikipedia.org/wiki/Standard_deviation) 來分析運行時間(詳細參閱 [GitHub](https://github.com/RinHizakura/linked-list/blob/master/scripts/perf.py))。得到如下的圖：
原本我預期交換數值的方法會比較快，畢竟不用調整 next 指去哪，又可以通過 bitwise 運算提升交換的效率。然而在圖中驚訝的發現，兩個方法的快慢其實沒有顯著的差異。
初步猜測是 XOR 裡的 branch 判斷導致。因為可以確認自己對 XOR 的使用是對於兩個相異的 object(粗淺的說，不同的變數)，因此我們把程式調整為沒有分支的 `XORSWAP_UNSAFE`，然後得到的結果是：
感覺好像真的是 branch 產生影響？於是我試圖用 perf 去觀察使用 `XORSWAP_UNSAFE` 和 `XOR` 的在 node 數量 2000 時的 branch misses，
* `XORSWAP`
```
sudo perf stat -e branch-misses:u,branches:u ./exec
Performance counter stats for './exec':
5,668 branch-misses:u # 0.26% of all branches
2,214,808 branches:u
0.005515600 seconds time elapsed
0.005551000 seconds user
0.000000000 seconds sys
```
* `XORSWAP_UNSAFE`
```
sudo perf stat -e branch-misses:u,branches:u ./exec
Performance counter stats for './exec':
5,656 branch-misses:u # 0.26% of all branches
2,213,809 branches:u
0.007371779 seconds time elapsed
0.007382000 seconds user
0.000000000 seconds sys
```
從結果來看，`XORSWAP_UNSAFE` 的 branch miss 雖然看似少一些，但兩者的差異並不大。雖然也有可能是因為圖中的時間是用 ns 等級，所以看起來會差距比較明顯，但是如此接近的 branch miss 不該是導致如此差距的原因。為了可以得知更多的細節，我嘗試使用 [Cachegrind](https://www.valgrind.org/docs/manual/cg-manual.html) 檢查記憶體的實際情況：
```
$ valgrind --tool=cachegrind ./exec
$ cg_annotate <file>
$ cg_diff <file1> <file2>
```
* `XORSWAP`
```
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
--------------------------------------------------------------------------------
17,116,037 1,050 1,029 8,303,820 755,543 2,081 2,131,776 4,773 1,596 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function
--------------------------------------------------------------------------------
55,014 4 4 41,005 1,002 0 4,003 0 0 /home/rin/Github/linked-list/linked_list.c:swap_pair_by_value
```
* `XORSWAP_UNSAFE`
```
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
--------------------------------------------------------------------------------
17,109,037 1,047 1,027 8,298,820 755,543 2,081 2,131,776 4,773 1,596 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function
--------------------------------------------------------------------------------
48,014 3 3 36,005 1,002 0 4,003 0 0 /home/rin/Github/linked-list/linked_list.c:swap_pair_by_value
```
觀察一下兩者的差異：
* Ir(執行的總指令數)總體的差距為 `17,116,037 - 17,109,037 = 7000` 與 `swap_pair_by_value` 的 `55,014-48014 = 7000` 相等
* Dr(memory 的讀取次數)總體的差距為 `8,303,820 - 8,298,820 = 5000` 與 `swap_pair_by_value` 的 `41,005 - 36,005 = 5000` 相等
仔細一想，就發現其實自己把問題複雜化了，因為 `XORSWAP_UNSAFE` 的指令會比 `XORSWAP` 少，不需要讀取記憶體位址檢查是否相同，所以可以執行的快一些原本就十分合理。而當節點變多，指令的差異量就會表現在時間上。
:::warning
設計實驗時，應考慮 linked list 節點結構中的資料可能很多項，成員可能還指向其他記憶體空間。
:notes: jserv
:::
### `reverse`
概念和原本的 `reverse` 並無太大差異，只是為了確保 `head` 最後會是指到原本 linked list 的尾端，把 while 迴圈中的判斷條件條件調整成判斷下一個是否為 NULL。
```c=
void reverse(node_t **head) {
node_t *prev = NULL;
node_t *next = (*head)->next;
(*head)->next = prev;
while(next){
prev = (*head);
*head = next;
next = next->next;
(*head)->next = prev;
}
}
```
## 遞迴版本的 `reverse`
整體的概念和前面的 reverse 相同： 首先改變現在的 node 的指向，把它往前指。如果下一個要被調整的 node 為 NULL，表示已經找到原本 linked list 的尾端，因此要把 head 更新到該位置上並且 return。否則就繼續往下 recursive。
```c=
void recursive_rev(node_t **head)
{
if (!head)
return;
recursive_rev_step(*head, NULL, head);
}
void recursive_rev_step(node_t *curr, node_t *prev, node_t **head)
{
node_t *next = curr->next;
curr->next = prev;
if (!next) {
*head = curr;
return;
}
recursive_rev_step(next, curr, head);
}
```
## Fisher–Yates shuffle
[Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 是用來將一段有限的數列做隨機排序(排列的結果是等概率的)的演算法。
### Pencil-and-paper method
最原始的方法是由 [Ronald Fisher](https://en.wikipedia.org/wiki/Ronald_Fisher) 和 [Frank Yates](https://en.wikipedia.org/wiki/Frank_Yates) 手寫的，大致的概念如下：
* 假設初始的序列如下:
| 隨機數範圍 | 選擇隨機數 | 原始序列 | 產生序列 |
| ---------- | ---------- |:--------- | -------- |
| | | 1 2 3 4 5 | |
* 5 個數字的序列，因此從 1~5 間隨機選一數字，以這裡為例是 3，所以把原始序列從左開始數的第 3 個數字 3 放到結果中
| 隨機數範圍 | 選擇隨機數 | 原始序列 | 產生序列 |
| ---------- | ---------- |:--------- | -------- |
| 1-5 | 3 | 1 2 3 4 5 | 3 |
* 4 個數字的序列，因此從 1~4 間隨機選一數字，以這裡為例是 4，所以把原始序列從左開始數的第 4 個數字 5 放到結果中
| 隨機數範圍 | 選擇隨機數 | 原始序列 | 產生序列 |
| ---------- | ---------- | ------------- |:-------- |
| 1-4 | 4 | 1 2 ~~3~~ 4 5 | 3 5 |
* 重複這個流程，隨機數範圍為 0 (原始序列的內容都被搬到產生的序列中)
### Modern method
考慮到在計算機上的使用，Richard Durstenfeld 提出了改進。因為原始方法 「 從左開始數的第 n 個數字」這個過程涉及對原始 array 的額外調整，所以時間複雜度會是 $O(n^2)$，這裡的時間複雜度則是 $O(n)$。此外，不需另外產生一個儲存的序列(inplace)，而是透過 swap 的方式達到同等的效果。
:::warning
這裡的時間複雜度當是以 array 儲存的前題下，考慮到資料結構的差異可能也會有複雜度的差異，必須思考自己使用的資料結構給出最恰當的演算法。
:::
* 假設初始的序列如下:
| 隨機數範圍 | 選擇隨機數 | 原始序列 |
| ---------- | ---------- |:--------- |
| | | 1 2 3 4 5 |
* 從 1~5 間隨機選一數字，以這裡為例是 3，所以把原始序列從左開始數的第 3 個數字和最後 1 個數字交換
| 隨機數範圍 | 選擇隨機數 | 更新後序列 |
| ---------- | ---------- |:--------- |
| 1-5 | 3 | 1 2 5 4 3 |
* 從 1~4 間隨機選一數字，以這裡為例是 2，所以把原始序列從左開始數的第 2 個數字和倒數第 2 個數字交換
| 隨機數範圍 | 選擇隨機數 | 更新後序列 |
| ---------- | ---------- | ------------- |
| 1-4 | 2 | 1 4 5 2 3 |
* 重複這個流程，直到隨機數範圍為 0
### 實作
```c=
void shuffle(node_t **head)
{
srand(time(NULL));
// First, we have to know how long is the linked list
int len = 0;
node_t **indirect = head;
while (*indirect) {
len++;
indirect = &(*indirect)->next;
}
// Append shffling result to another linked list
node_t *new = NULL;
node_t **new_head = &new;
node_t **new_tail = &new;
while (len) {
int random = rand() % len;
indirect = head;
while (random--)
indirect = &(*indirect)->next;
node_t *tmp = *indirect;
*indirect = (*indirect)->next;
tmp->next = NULL;
if (new) {
(*new_tail)->next = tmp;
new_tail = &(*new_tail)->next;
} else
new = tmp;
len--;
}
*head = *new_head;
}
```
* 首先，先走訪整個原始的 linked list，算出原本的 linked list 有多長
* 用一個 `new` 作為新的 linked list 的 dummy node
* `new_head` 總是指向新 linked list 的頭，這是為了回傳時更新 head
* `new_tail` 總是指向新 linked list 的尾端，這是為了重新 append 的時候不需要從頭找起
* 每次產生舊 linked list 長度範圍的隨機亂數 `n`，找到第 `n` 個 node，拆下來 append 到新的 linked list 上
* 重覆直到舊的 linked list 上沒有 node (`len == 0`)
:::warning
延伸問題：
* 檢驗洗牌後的結果是否「足夠亂」，確認演算法的實作正確性
* 思考現在的實作是否可以改善？或者是否有對於 singlely-linked list 更有效率的 shuffle 方式？(考慮到 $O(n)$ 的 access)
:::
Sign in with Wallet
Connect another wallet