owned this note
owned this note
Published
Linked with GitHub
# 2019q1 Homework1(list)
contributed by < `st9540808` >
* [F02: list](https://hackmd.io/s/S12jCWKHN)
## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list?一般的 function call 有何成本?
有一些操作只能用 macro 實作像是 `list_for_each` ,需要展開成 for 才能支援這種循序走訪。
一般的 function call,caller 需要把引數放到 stack 中,新增一段新的 stack,並在回傳時收回,macro 沒有這些操作的成本
參考: [x86 calling convention](https://en.wikibooks.org/wiki/X86_Disassembly/Calling_Conventions)
### Linux 應用 linked list 在哪些場合?舉三個案例並附上對應程式碼,需要解說,以及揣摩對應的考量
> v4.20.13 kernel/sched/sched.h, line 228
`struct rq` 是 linux 中的 runqueue,裡面有兩個成員 `struct cfs_rq cfs` CFS 的排程器和 `struct rt_rq rt` 即時排程器的 runqueue,即時任務總共有 100 個優先級 (0-99),所以在 `struct rt_rq rt` 中有一個 `struct rt_prio_array` 的實體 `active`,對應的 runnable 及時任務會被放在相對應優先級的 runqueue 中
```c
struct rt_prio_array {
DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
struct list_head queue[MAX_RT_PRIO];
};
```
:::warning
列出 Linux 核心版本並 **解說**
只有列出結構體,不能算是解說,而要廣泛提及針對該結構體做了哪些 linked list 操作,又考量點為何
:notes: jserv
:::
### GNU extension 的 typeof 有何作用?在程式碼中扮演什麼角色?
## merge sort 實作
### function prototype:
```C
list_ele_t *get_middle(struct list_head *list);
void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head);
void list_merge_sort(queue_t *q);
```
`queue_t` 和 `list_ele_t` 的定義是從 lab0 引入,在兩者中都加入 `struct list_head` ,以便最終能夠支援 qtest
merge sort 需要兩個輔助的函式以便實作 `list_merge_sort()` ,兩個函式的說明如下:
* `get_middle()`: 回傳一個 list 中,位於中間節點的位址
* `list_merge()`: 合併兩個已排序的 list
### 實作細節
#### `get_middle()`
使用兩個指標 `fast slow` 來走訪 list,`fast` 一次會前進 2 個節點,`slow` 一次會前進 1 個。
參考: [Floyd Cycle Detection Algorithm](https://zh.wikipedia.org/wiki/Floyd%E5%88%A4%E5%9C%88%E7%AE%97%E6%B3%95)
```c
list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast, *slow;
fast = list->next;
list_for_each (slow, list) {
if (fast->next != list && fast->next->next != list)
fast = fast->next->next;
else
break;
}
return list_entry(slow, list_ele_t, list);
}
```
#### `list_merge()`
將兩個已排序好的 list `lhs rhs` 合併在一起並傳給 `head`,因為排序對象是字串,排序完要變成字典序,所以用 `strcmp()` 比較兩個字串在字典中的順序,
```c
void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
struct list_head *temp;
INIT_LIST_HEAD(head);
if (list_empty(lhs)) {
list_splice_tail(lhs, head);
return;
}
if (list_empty(rhs)) {
list_splice_tail(rhs, head);
return;
}
while (!list_empty(lhs) && !list_empty(rhs)) {
if (strcmp(list_entry(lhs->next, list_ele_t, list)->value,
list_entry(rhs->next, list_ele_t, list)->value) <= 0)
temp = lhs->next;
else
temp = rhs->next;
list_del(temp);
list_add_tail(temp, head);
}
list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}
```
#### `list_merge_sort()`
合併排序的主演算法,全部使用 `list_*` 的操作
1. 檢查 list 是否只有一個節點 (遞迴的中止條件)
2. 將 list 切成兩份,左邊的在 `left` ,右邊的在 `q`
3. 遞迴呼叫 ```list_merge_sort(&left); list_merge_sort(q); ```
4. 將左右兩個 list 合併,並將合併後的 list 放入 `q`
```c
void list_merge_sort(queue_t *q)
{
struct list_head sorted;
queue_t left;
if (list_is_singular(&q->list))
return;
INIT_LIST_HEAD(&left.list);
list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
INIT_LIST_HEAD(&q->list);
list_splice_tail(&sorted, &q->list);
}
```
merge sort 與 quick sort 的效能比較,資料來自 [dict](https://github.com/sysprog21/dict) 的 [cities.txt](https://github.com/sysprog21/dict/blob/master/cities.txt) ,內含九萬多筆城市的字串,並分別對 30000、60000、90000 筆資料做排序,比較兩種演算法對**亂序資料**的排序效能。
![](https://i.imgur.com/9w1AyCO.png)
可以看到 quick sort 比起 merge sort 有比較好的效能表現,但如果排序資料是已經排序好的,就會出現 worst case $O(n^2)$ 的時間複雜度。
`list_merge()` 需要插入 n 個節點,每次比較都要呼叫 `strcmp()` ,但因為測試資料中字串的最大長度是固定的,所以每次比較需要 $Θ(1)$。 `list_merge_sort()` 的時間複雜度可以用以下遞迴式表示:
$T(n) = 2T(n/2) + Θ(1)$
用 master theorem 可以解以上式子,得到 $T(n) = Θ(nlogn)$