---
tags: linux kernel
---
# 2023q1 Homework1 (quiz1)
contributed by < `hankTaro` >
## 測驗一
* 實作快速排序法，數值由小到大排列，並確保可達到 stable sorting 的目標。
```c=
static void list_sort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);
struct item *itm = NULL, *is = NULL;
CCC (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
DDD (&itm->list, &list_less);
else
EEE (&itm->list, &list_greater);
}
list_sort(&list_less);
list_sort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);
}
```
* 此為遞迴模式的 quick sort
* 利用`Divide and Conquer`
1. 找出中間節點 `pivot`
2. 以 `pivot` 為比較值，分出值大於/小於 `pivot` 的兩群，重複進行 `list_sort` ，直到分不出新的大小群為止
```c
//將第一個節點設為 pivot，並將此點從串列中移出
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);
```
其中 `list_first_entry` 的參數是 `#define list_first_entry(head, type, member)` ，所以 `AAAA = struct item` ，`BBBB = list`
```c
//節點結構
struct item {
uint16_t i;
struct list_head list;
};
```
```c=
// 群訪各點判斷其與 `pivot` 的大小關係，並分群
struct item *itm = NULL, *is = NULL;
CCC (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
DDD (&itm->list, &list_less);
else
EEE (&itm->list, &list_greater);
}
// 將兩群分別進行遞迴
list_sort(&list_less);
list_sort(&list_greater);
// 將串列依據合併
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);
```
* 其中 `CCC = list_each_entry_safe` ，尋訪各點並且支援在尋訪期間移動當前節點移至其他串列中
* `if (cmpint(&itm->i, &pivot->i) < 0)` 由於是取第一個節點，所以與他相將等的值，必定在其後方，因此比較時使用 `<` 而非 `<=` 使與他相等的的節點存入 `greater` 中，以保持 ==stable==
* 利用 `list_move_tail` 將當前節點分別移到 `list_less` 和 `list_greater` 的尾端，由於 `list_each_entry_safe` 是正向尋訪，所以需要使用 `list_move_tail` 而非 `list_move` 以保持結果 ==stable== ，所以 `DDD = EEE = list_move_tail`
* 最後將大小串列合併，將小於 `pivot` 的放於 `pivot` 與 `head` 之間，將大於 `pivot` 的串列放於 `pivot` 之後，故 `FFF = list_splice_tail`
### (代辦)針對 Quick sort 提出上述程式碼的改進方案並實作
引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
## 測驗二
* 將測驗一的程式碼改為非遞迴
```c=
#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
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);
while (top >= 0) {
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
if (!list_empty(&partition) && !list_is_singular(&partition)) {
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
struct item *itm = NULL, *is = NULL;
GGGG (itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
HHHH (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);
} 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(KKKK);
list_add_tail(&tmp->list, head);
}
}
}
}
```
### 分段說明
* 初始化，將愈進行 quick sort 的串列放入 stack[0] 中
```c=
// 將 stack[0] 指向 head 後的串列，並將 head 指向自身
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]);
```
進入 `while` 後，將 `stack[top]` 中的值 `pop()` 進入 `partition` ，並且判別其值是否可再次分割，若可以，隨後所做的事與遞迴版本無異，都是先找出 `pivot` 並分出 less 和 greater 兩群，唯一不同的是這裡使用的是 `list_move` 而非 `list_move_tail` 會使其 ==non-stable== ，其餘與與測驗一相同，下方的程式碼 `GGGG = list_each_entry_safe`
```c=
while (top >= 0) {
// 將從 stack 中 pop() 出的值放入 partition
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
if (!list_empty(&partition) && !list_is_singular(&partition)) {
/*
.
.
.
*/
struct item *itm = NULL, *is = NULL;
GGGG (itm, is, &partition, list) {
// 不必 remove 因為在 `list_move` 時，自然就會被移出
// list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
/*
.
.
.
*/
}
}
```
而接下來的分治部分，先將 pivot 併入 list_less 這群中，再利用 stack 的 pop 和 push 實現
其中 `HHHH = list_move_tail` ，而 `IIII = JJJJ = &stack[++top]` 將兩群分別 `push()` 進入 stack
這裡 `push()` 的順序極為重要，會影響到後續程式碼的寫法，以下是以先 `push(greater)` 再 `push(less)` ，所以 `less` 方的會最先被分割到無法分割，也就是最終越接近頂端的值最小，隨後合併時要依序從上到下的放入 `head` 中，就會是由小到大的 (詳見圖解)
```c=
// 將 pivot 併入 list_less 這群中
HHHH (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);
```
當 `pop()` 出的值不可再次分割，由於 `less` 總是後 `push()` 所以會最早分割完，使不可分割值由大到小向上堆疊，所以依序將 stack 中 pop() 出的值 `list_add_tail` 至 `head`，直到遇上可分割的值為止
* `KKKK = &stack[top--]` 作為 `pop()`
* 另外 while 中做的事，與 `list_splice_tail_init(&stack[top--], head);` 等價，可直接用其替代
```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(KKKK);
list_add_tail(&tmp->list, head);
}
}
```
#### 圖例
* 圖一
```graphviz
digraph graphname {
rankdir="LR"
node [shape=record]
// label="divide"
subgraph cluster_0 {
label="stack[top]"
peripheries=0
stack[label="<f0>|<f1>|<f2>|<f3>list_less(1)|<f4>list_greater(1)"]
}
list_1[label="{<f0>3|<f1>2|<f2>1|<f3>6|<f4>4}"]
list_2[label="{<f0>7|<f1>10|<f2>13|<f3>8|<f4>12}"]
stack:f3 -> list_1
stack:f4 -> list_2
ptr [label=top ,shape=plaintext]
ptr -> stack:f3
}
```
* 圖二
`partition = pop(top)` 也就是 `list_splice_init(&stack[top--], &partition);`
```graphviz
digraph graphname {
rankdir="LR"
node [shape=record]
// label="divide"
subgraph cluster_0 {
label="stack[top]"
peripheries=0
stack[label="<f0>|<f1>|<f2>|<f3>|<f4>list_greater(1)"]
}
list_1[label="{<f0>3|<f1>2|<f2>1|<f3>6|<f4>4}"]
list_2[label="{<f0>7|<f1>10|<f2>13|<f3>8|<f4>12}"]
// stack:f3 -> list_1
stack:f4 -> list_2
ptr [label=top ,shape=plaintext]
ptr -> stack:f4
partition[label=partition ,shape=plaintext]
partition -> list_1
}
```
* 圖三
將其分群後使用
`list_splice_tail(&list_greater, &stack[++top]);`
`list_splice_tail(&list_less, &stack[++top]);`
```graphviz
digraph graphname {
rankdir="LR"
node [shape=record]
// label="divide"
subgraph cluster_0 {
label="stack[top]"
peripheries=0
stack[label="<f0>|<f1>|<f2>list_less(2)|<f3>list_greater(2)|<f4>list_greater(1)"]
}
list_1[label="{<f0>3|<f1>2|<f2>1}"]
list_2[label="{<f0>7|<f1>10|<f2>13|<f3>8|<f4>12}"]
list_3[label="{<f3>6|<f4>4}"]
stack:f3 -> list_3:f0
stack:f4 -> list_2:f0
stack:f2 -> list_1:f0
ptr [label=top ,shape=plaintext]
ptr -> stack:f7
}
```
### (代辦)效能分析
### (代辦)改進辦法與成果
#### 必免依賴 `MAX_DEPTH`
此程式碼的 wrost case 就是傳入遞減數列，會使得每一次 `push()` 進去的串列大小為 $n-1$ ，最終會占用到 `stack[n]` 才有辦法合併
```graphviz
digraph graphname {
rankdir="LR"
node [shape=record]
// label="divide"
subgraph cluster_0 {
label="stack[top]"
peripheries=0
stack[label="<f0>|<f1>[4,1]|<f2>[7]|<f3>[8]|<f4>[9]"]
}
// list_1[label="9",width=0.3, height=0.3]
// list_2[label="8",width=0.3, height=0.3]
// list_3[label="7",width=0.3, height=0.3]
// list_4[label="{<f0>4|<f1>1}",width=0.3, height=0.3]
// stack:f1 -> list_4
// stack:f2 -> list_3
// stack:f3 -> list_2
// stack:f4 -> list_1
ptr [label=top ,shape=plaintext]
ptr -> stack:f1
}
```
```graphviz
digraph graphname {
rankdir="LR"
node [shape=record]
// label="divide"
subgraph cluster_0 {
label="stack[top]"
peripheries=0
stack[label="<f0>[1]|<f1>[4]|<f2>[7]|<f3>[8]|<f4>[9]"]
}
// list_1[label="9",width=0.3, height=0.3]
// list_2[label="8",width=0.3, height=0.3]
// list_3[label="7",width=0.3, height=0.3]
// list_4[label="{<f0>4|<f1>1}",width=0.3, height=0.3]
// stack:f1 -> list_4
// stack:f2 -> list_3
// stack:f3 -> list_2
// stack:f4 -> list_1
ptr [label=top ,shape=plaintext]
ptr -> stack:f0
}
```
>>想法一:
>>使用動態記憶體分配，將 `stack` 大小分配成 `list_count_nodes(head)` 的大小
>
>>想法二:
>>利用 hybrid sort 的概念，在不同深度使用不同排序法，進而減少運算時間並且降低 `stack` 最大所需空間
```c=
#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
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]);
int top = 0;// 作為stack_ptr
list_splice_init(head, &stack[0]); //減少沒必要的運算量
// struct list_head partition;
// INIT_LIST_HEAD(&partition);
INIT_LIST_HEAD(partition); // 可用一行指令表示
while (top >= 0) {
INIT_LIST_HEAD(&partition);
// 將資料 pop() 進 partition 中
list_splice_init(&stack[top--], &partition);
// 與遞迴版本中一致，找出 pivot 並且分群出 less 和 greater
if (!list_empty(&partition) && !list_is_singular(&partition)) {
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
//尋訪各點進行分群
struct item *itm = NULL, *is = NULL;
list_each_entry_safe(itm, is, &partition, list) {
// 不必 remove 因為在 `list_move` 時，自然就會被移出
// list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
// list_move(&itm->list, &list_less);
//使其 stable
list_move_tail(&itm->list, &list_less);
else
// list_move(&itm->list, &list_greater);
//使其 stable
list_move_tail(&itm->list, &list_greater);
}
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]);
} 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(KKKK);
// list_add_tail(&tmp->list, head);
list_splice_tail_init(&stack[top--], head);
}
}
}
}
```
## 測驗三
LLL = (uintptr_t) a ^ (uintptr_t) b
MMM = &list->tail
PPP = real_next->cmp
Sign in with Wallet
Connect another wallet