# 2020q1 Homework3 (quiz3)
contributed by < [Hsuhaoxiang](https://github.com/Hsuhaoxiang) >
> [2020q1 第三週測驗題](https://hackmd.io/@sysprog/linux2020-quiz3) 解題思路
## 測驗 `1`
```cpp=
list *sort(list *start)
{
if (!start || !start->addr)
return start;
list *left = start, *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 = left->addr;
if (next)
next->addr = XOR(left, next->addr);
if (!merge) {
start = merge = left;
merge->addr = NULL;
} else {
merge->addr = LL1;
left->addr = LL2;
merge = left;
}
left = next;
} else {
list *next = right->addr;
if (next)
next->addr = XOR(right, next->addr);
if (!merge) {
start = merge = right;
merge->addr = NULL;
} else {
merge->addr = RR1;
right->addr = RR2;
merge = right;
}
right = next;
}
}
return start;
}
```
## XOR linked list
本題與[第一週](https://hackmd.io/@sysprog/linux2020-quiz1)極為相似，重點在於要看懂每個 node 的連結方式，除了頭尾的每個 node 都可以藉由與指向上個 node 的 pointer 以及自己本身的 addr 做 XOR 得到下個節點的位置，同樣地如果擁有指向下個 node 的 pointer 便可以與自己的 addr 做 XOR 得到上個節點的位置，那頭尾的 addr 要放什麼呢？如果是 list 的 head 要指出下一個節點的位置就要將 head 前一個節點 NULL 與 addr 做 XOR ，而 NULL 轉型為 `uintptr_t` 其內含值仍是 0，根據 $A \oplus 0 = A$ ，我們只需要放下一個 node 的記憶體位置即可，至於如果是一個 list 的 tail 則只要放上一個 node 的記憶體位置。藉由此技巧我們就能在降低空間使用量的情況下實作雙向的 linked list。
```graphviz
digraph xor_linked_list {
rankdir=LR;
node [shape=record];
a [label="{ <data> 12 | <ref> B }",width=1.2]
b [label="{ <data> 99 | <ref> A XOR C}",width=1.2];
c [label="{ <data> 37 | <ref> B XOR D}",width=1.2];
d [label="{ <data> 35 | <ref> C}",width=1.2];
a:ref:c -> b:data [arrowhead=vee, dir=both];
b -> a:ref [arrowhead=vee,dir=both];
b:ref -> c:data [arrowhead=vee, dir=both];
c -> b:ref [arrowhead=vee,dir=both];
c:ref -> d:data [arrowhead=vee, dir=both];
d -> c:ref [arrowhead=vee,dir=both];
}
```
如上圖假設 node 的記憶體位址依序為 A 、 B 、 C 、 D , 則 head 在 addr 只要放下個節點的記憶體位址與 0 (NULL) 做 XOR 還是 得到下個節點的位置 B ，而對於第二個節點需要上個節點的記憶體位址也就是 A 便可得到 $(A \oplus C) \oplus A = C$ ，對於 tail 與 head 相同只需要放上一個節點的記憶體位置 C 就好了。
## 解題思路
### LL1 = ?
從第 13 行的 for loop 可以看出這段和[第一週測驗題](https://hackmd.io/@sysprog/linux2020-quiz1)一樣是在 merge 左右兩邊已經 sort 好的 xor linked list，如果第一個判斷式 `!right || (left && left->data < right->data)` 成立的話，要 merge 的點就會是 left 的 head ， `list *next = left->addr` 由於 left 為 head addr 即為下個 node 的位置不必經過 XOR 運算，而 next 若不為 NULL (如果 list 只有單一節點他的 addr 放的會是 NULL) 原本的 left head 將會被合併到正在排序的 list 所以這個 next 會成為新的 head 故我們必須更新他的 addr ，也就是只需要放下個 node 的記憶體位置利用與前一個節點記憶體位置和現在的 addr 便是next 新的 addr 的值，也就是 `next->addr = XOR(left, next->addr)`。再來我們需要知道 `merge` 這個變數，他是指著正在合併的 list 的 tail
所以第一題 `merge->addr = LL1` ，我們便可以知道需要將尾巴再加上現在要合併的點left 的 head 所以答案刪到只剩 (d) (h)，那我們知道既然 `merge` 是正在合併的 tail 那他的 addr所放的就會是他的上一個 node 的記憶體位置，我們必須讓 addr 的值變成 上個 node 與 下個 node 的記憶體位置的 XOR。
> 答案為 `(h) XOR(merge->addr, left)`
### LL2 = ?
`left->addr = LL2`將會是正在合併的 list 的 tail 只要放上一個節點的記憶體位置就好了，
> 答案為 `(c) merge`
### LL3 & LL4 = ?
這兩題其實只是上面的題目變成 right 先合併所以只要找對稱的選項即可
> LL3 = `(i)XOR(merge->addr, right)`
> LL4 = `(c)merge`
:::warning
延伸問題:
3. 修改 [lab0-c](https://github.com/sysprog21/lab0-c) 裡頭的 [harness.c](https://github.com/sysprog21/lab0-c/blob/master/harness.c)，將原本內部使用的 doubly-linked list 換為 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list)，觀察記憶體佔用率的變化，可設計頻繁的 `test_malloc` / `test_free` 呼叫交錯情境。
:::
---
## 測驗 `2`
考慮以下 singly-linked list 程式:
```cpp
#include <stddef.h>
struct node {
int data;
struct node *next;
} *head;
void insert(struct node *newt) {
struct node *node = head, *prev = NULL;
while (node != NULL && node->data < newt->data) {
prev = node;
node = node->next;
}
newt->next = node;
if (prev == NULL)
head = newt;
else
prev->next = newt;
}
```
可透過以下 pointer to pointer 改寫 `insert` 函式，功能等價但更簡潔，如下:
```cpp
void insert(struct node *newt)
{
struct node **link = &head;
while (*link && AA)
BB;
newt->next = *link;
*link = newt;
}
```
#### AA = ?
```
(a)(link)->data < newt->data
(b)*link->data < newt->data
(c)(*link)->data < newt->data
(d)**link->data < newt->data
```
要將list中的data值取出來故選`(c)(*link)->data < newt->data` (*link) 為指向目前 node 的 pointer
#### BB = ?
```
(a)link = &(*link)->next
(b)*link = *link->next
(c)(*link) = (*link)->next
(d)link = (*link)->next
```
因為 link 為 pointer to pointer 一開始他指著 head 也就是 `(*link)` 為 head 如果 選 `(c)(*link) = (*link)->next` head 就被改變。
> 答案是 `(a) link = &(*link)->next`
#### 為何要用 pointer to pointer?
* [從刪除 linked list node 看程式設計的品味](https://medium.com/fcamels-notes/%E5%BE%9E%E5%88%AA%E9%99%A4-linked-list-node-%E7%9C%8B%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88%E7%9A%84%E5%93%81%E5%91%B3-b597cc5af785)
在你所不知道的 C 語言中有提到，「有品味」(Linus 原話) 的程式碼，不管是不是 head 其實只是要將一個 `node *` 的指標指向他而已，如果使用 pointer to pointer 的方式存取 list 就能直接改動 `*list` 這個 pointer 如果假設 insert 的node 是最小的元素那 `*list` 其實還是等於是 head 便能將 head 指向新插入的 node，而如果今天是 insert 在中間 list 這個 pointer to pointer 已經指向目前欲插入元素位置前一個 node 的 next 所以不用多加處理，只要一行`*link = newt;`就能完成這些指標的連結，稍微能體會到一點什麼是有品味的程式碼了！
---
## 延伸問題
### [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort) 找到一個恰當的 S
:::warning
在 Wikipedia 關於合併排序的詞目中，談及 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)，我們可知道一種最佳化策略是：在子序列大小達到 $S$ 時就不再繼續分割，此時這個 $S$ 為可完整放進處理器 cache 中的元素數量。每個大小為 $S$ 的子序列，都透過適用於小規模 in-place (即不需要額外配置記憶體) 排序演算法（如插入排序或泡沫排序）進行排序，以減少在記憶體內交換特定區域的次數。在小型子序列排序完畢後，再以典型的遞迴型合併排序完剩下的部份。
若可找到一個恰當的 $S$， 便能有效的同時利用到插入排序和合併排序的優點，並減少原始的合併排序當中 locality 不好的影響。請觀察你的硬體組態 (如 L1 data cache 的容量和行為)，以上述策略實作效率更好的 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 排序程式。過程中應該充分量化數據並進行視覺化處理。
:::
#### 修改 sort
* 原本的 `sort` 在分成左右兩個 `list` 時只是單純的把最左邊的 `node` 分開
* 修改成左右兩邊各為原來的一半，原本 `sort()` 的參數加上一項 `list` 的長度
* 測試排序1~10000 個 `node` ，原本的 merge sort 為 $O(n^2)$
```cpp
int m2 = size / 2;
list *left = start, *right = start->addr, *left_end = start;
for (int i = 0; i < m2 - 1; i++) {
list *tmp;
tmp = right;
right = XOR(right->addr, left_end);
left_end = tmp;
}
left_end->addr = XOR(right, left_end->addr);
right->addr = XOR(right->addr, left_end);
left = sort(left, m2);
right = sort(right, size - m2;
```
#### In-place Sort Algorithm
* 我選擇使用 `bubble sort`
* 中間的 `swap` 我只是單純交換 `node` 的 `data` 而不是 `addr`
```cpp
void bubble_sort(list* head, int count)
{
int i, j, swapped;
for (i = 0; i < count-1; i++) {
list *h = head;
list *pre = NULL;
swapped = 0;
list *p1 = h, *p2 = XOR(p1->addr, pre), *temp;
for (j = 0; j < count - i - 1; j++) {
if (p1->data > p2->data) {
swap(p1, p2);
swapped = 1;
}
temp = p1;
p1 = p2;
p2 = XOR(temp, p1->addr);
}
if (swapped == 0)
break;
}
}
void swap(list* node1, list* node2)
{
int tmp = node1->data;
node1->data = node2->data;
node2->data = tmp;
}
```
#### Experiments
* 每次使用`merge sort` 時先將 `list` 分成 `left` 與 `right` 長度為 $len/2$
* 直到 $len$ 小於 `S` 再用 `bubble sort` 做好排序
* 最後合併 `left` `right`
* `list` 長度為 10000， `S` 測到1000
:::danger
看起來S越接近零排序越快完成，也就是直接使用 merge sort 排的最快，我覺得跟問題所說的策略(找到一個恰當的 S， 便能有效的同時利用到插入排序和合併排序的優點)不相符，之後要再看看 S 從零到五十的時間
:::
Sign in with Wallet
Connect another wallet