owned this note
owned this note
Published
Linked with GitHub
---
tags: linux2023
---
# 2023q1 Homework1 (quiz1)
contributed by < `brianlin314` >
> [第一周測驗題](https://hackmd.io/@sysprog/linux2023-quiz1)
### 測驗一
:::danger
不用抄題目，開發紀錄著重於你的想法和過程中遭遇到的問題，紀錄和討論才是主體，程式碼僅作搭配說明的用途。
:notes: jserv
> 學生收到
:+1:
:::
遞迴版 `quick sort` ，使用 `Divide and Conquer` 的概念。
`quick sort` 實做流程：
1. 在資料列中找出一個基準值 `pivot`
2. 將小於 `pivot` 的資料放在左邊，大於 `pivot` 的資料放在右邊
3. 左右兩邊資料分別重複1~2步驟，直到剩下1筆資料
4. 合併
```c
if (list_empty(head) || list_is_singular(head))
return;
```
首先，會先判斷 `list` 是否有節點存在，抑或是只存在一個節點。
```c
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
`list_less`, `list_greater` 分別代表兩個不同 `list` 的 `head`，前者放入比 `Pivot` 小的節點，後者，反之。
```c
struct item *pivot = list_first_entry(head, item, list);
```
`pivot` 設為該 `list` 的第一個節點。
所以使用 `list_first_entry` 來取得 `list` 的第一個節點的 `entry`。
:::warning
不用提及行號，可斟酌列舉相關程式碼來解說。避免「舉燭」，你應該思考：要是我來實作這樣的程式碼，我會怎麼做。
:notes: jserv
:::
```c
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
list_move_tail (&itm->list, &list_less);
else
list_move_tail (&itm->list, &list_greater);
}
```
使用 `list_for_each_entry_safe` 來走訪整個 `list`，接著使用比較函式 `cmpint` 來判斷節點數值跟 `pivot` 的大小
- 若節點的值小於 `pivot`，用 `list_move_tail` 將該節點從原 list 移動到 `list_less` 的尾端。
- 反之若大於等於 `pivot`，用 `list_move_tail` 將改節點移動到 `list_greater` 的尾端。
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
```
接著持續不斷對 `&list_less` 與 `&list_greater` 進行遞迴，直到無法切割為止。
最後，將 `&list_less` 先串接到 `head`，再將 `&list_greater` 接到該 `list` 的尾端。
#### 可改進之處
因為上述程式碼每次皆選取 `list` 的第一個節點作為 `pivot`，這會遇到一個問題，就是當該 `list` 已經是由大到小或是由小到大排序時，會導致每次選到的 `pivot` 都剛好是最大值或最小值，而沒辦法均分 `list_less` 和 `list_greater`，若遇到該極端狀況，上述程式碼的時間複雜度就是 $O(n^2)$。
因此可以透過更改選擇 `pivot` 的方法，去改進上述的程式碼，大概分為以下三種方法:
1. Middle-of-Three
(1) 令 $middle = \dfrac{left + right}{2}$
(2) 比較 list[left]、list[middle] 與 list[right] 這三筆資料，排出中間值，並將此中間值再與 list[left] 做交換
(3) 讓現在新的 list[left] 作為 pivot
2. Randomized pivot
亂數選取的方式，隨機挑 list 中的一個值作為 pivot，但 worst case 還是 $O(n^2)$
3. Median-of-Medians
詳細流程可參考 [Median of medians](https://en.wikipedia.org/wiki/Median_of_medians)
---
### 測驗二
```c
struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
INIT_LIST_HEAD(&stack[i]);
int top = -1;
list_splice_init(head, &stack[++top]);
struct list_head partition;
INIT_LIST_HEAD(&partition);
```
一開始即宣告一個 `stack` ，代表之後的實作皆與之有關，並且依照其定義的大小，使用 `INIT_LIST_HEAD` 初始化，接著將整條未排列的 `list` 放到 `stack` 裡。
再宣告一個 `partition` ，作用是每次迴圈中都會存放 `stack` top 中的 `list`。
需特別注意 `++top` 與 `top++` 的差別，因為自己習慣用 `i++` 了，所以常常忘記區分這兩種 case。
```c
while (top >= 0) {
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
...
}
```
每次進入迴圈時，都會將 `stack` top 中的 `list` 放到 `partition` 中，並進行以下 if-else 判斷。
```c
if (!list_empty(&partition) && !list_is_singular(&partition))
```
若 `partition` 有大於等於兩個節點，則通過該條件式，並且與 `測驗一` 的實作方法相同，`pivot` 選為該 `list` 的第一個節點，使用 `list_for_each_entry_safe` 走訪整個 `list` 並將比 `pivot` 小的節點放到 `list_less` 中，反之，則放到 `list_greater` 。
```c
list_move_tail (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, &stack[++top]);
if (!list_empty(&list_less))
list_splice_tail(&list_less, &stack[++top]);
```
先將 `pivot` 放到 `list_less` 的尾端，因為 `list_less` 裡面的節點值皆比 `pivot` 小。
再來要將 `list_less` 和 `list_greater` 再次放到 `stack` 中，由於是要加入到 `stack` 中，所以要先放入 `list_greater`，再放入 `list_less`，這樣才符合 FILO，等等拿出來的順序才是由小到大。
```c
else {
top++;
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp =
list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(&stack[top--]);
list_add_tail(&tmp->list, head);
}
}
```
若 `partition` 只有一個節點的話，會將 `partition` 放回 `stack` 中。
`while` 迴圈會不斷從 `stack` 中 pop `list` 出來，並且插入到 `head` 的尾端，直到該 `list` 不是只有一個節點存在或該 `stack` 為空為止。
---
### 測驗三
Google Drive
Gist
Clipboard
Sign in with Wallet
