# 2020q3 Homework1 (quiz1)
contributed by < `eecheng87` >
###### tags: `進階電腦系統應用2020`
## 延伸問題
### 改寫 reverse
需求: 使用 recursive 版本的 pointer to pointer 做 reverse 運算且避免回傳 `head`
```cpp
void reverse(node_t **head)
{
if(*head && (*head)->next){
node_t *cursor = *head;
*head = (*head)->next;
reverse(head);
cursor->next->next = cursor;
cursor->next = NULL;
}
}
reverse(&head);
```
簡單來說 `reverse` 因為是遞迴，所以會一直往後做 `*head = (*head)->next`，那在 main block 的 `head` 就會變成最後一個節點，這樣就達到 reverse 最基本的要求，頭變尾。
接著用例子來說明遞迴後的兩行，假設 A->B->C，那 `reverse(head)` 回來後 `B` 是 `cursor` 而 `C` 是 `head`，執行後兩行會變成 A 和 null<-B<-C。注意，接著 return 後回到上一層，`A` 的 next 仍是 B，因為每層的參數 `node_t **head` 都是獨立的(unique)。
### 效能分析
設計實驗比較使用 pointer to pointer 且 recursive 版本的 reverse 運算和 quiz1 提供的 iterative 版本速度。為了讓執行時間比較明確，這裡用長度為 1000 的 linked list 分別做 1000 次不同版本的 reverse。為了不被多核心影響，本實驗也會綁定 program 在某 cpu 上執行。透過 `time.h` 內的 `clock_gettime` 和 gnuplot 來展現實驗結果:
執行多次後發現都是 recursion 版本表現的比較好。
除了速度外，順便用 valgrind 內的工具 massif 來看記憶體用量:
recursive 的 reverse
```text
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
80 4,100,302 23,712 15,808 7,904 0
81 4,148,176 23,856 15,904 7,952 0
82 4,196,338 24,000 16,000 8,000 0
```
iterative 的 reverse
```text
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
80 4,100,308 23,712 15,808 7,904 0
81 4,148,182 23,856 15,904 7,952 0
82 4,196,344 24,000 16,000 8,000 0
```
除了一開始大量的和 heap 要求空間外，基本上也沒額外再要其他的記憶體，所以兩個版本在記憶體的表現上一樣。
### 改寫 swap pair
```cpp
void swap_pp(node_t **head){
node_t **node = head;
while(*node && (*node)->next){
node_t *tmp = *node;
*node = (*node)->next;
tmp->next = (*node)->next;
(*node)->next = tmp;
node = &(*node)->next->next;
}
}
swap_pp(&head);
```
相較 reverse，swap 就顯的比較好改寫，除了用 pointer to pointer `node` 來當成移動的節點(第一個 iteration 透過 `*node` 保留開頭是誰的資訊，所以不需要回傳)，其他的操作和原本的一樣。
### 效能比較
實驗方式和 reverse 大致一樣，但這次比較意外的是沒有回傳結果的版本竟然比較慢。
:::warning
上方實作裡頭的指標操作很多，可嘗試引入另一個指標來操作原本 `*node` 的內容，降低 indirection
:notes: jserv
:::
### 實做 Fisher–Yates shuffle 於 linked-list 上
網路上提供的 pseudo code，本次實做按照以下的邏輯:
```cpp
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
由於沒有要求 Fisher–Yates shuffle 在洗牌的時候要交換節點，所以這裡選用比較方便的方式，只交換 `value`
```cpp
void shuffle(node_t *head){
node_t *tmp = head;
int len = 0; // length of list
while(tmp){
tmp = tmp->next;
len++;
}
srand(time(NULL));
for(int i = len - 1; i > 0; i--){
int pos = 1;
int r = (rand() % i) + 1;
node_t *a = head;
node_t *b = head;
while(a->value != r && pos != i){
a = a->next;
pos++;
}
b = a->next;
while(b->value != r && pos != i){
b = b->next;
pos++;
}
a->value ^= b->value;
b->value ^= a->value;
a->value ^= b->value;
}
}
```
首先需要計算 list 的長度，如此才能界定隨機範圍。界定好範圍後那就只剩下遍歷整條 list，找出該次 iteration 需要交換的兩個點做交換。
Sign in with Wallet
Connect another wallet