# 2023q1 Homework1 (quiz1)
contributed by < [Chiwawachiwawa](https://github.com/Chiwawachiwawa) >
## 第一題
:::danger
不用抄題目，善用超連結。
:notes: jserv
:::
延伸問題:
### 1.解釋上述程式碼運作原理
首先,我們判斷head是否為空或是其它的值<s>,這段很好看出來</s>。
```c
if (list_empty(head) || list_is_singular(head))
return;
```
再來,我們接下來看這一段,
```c
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
我們宣告左右兩個 list 。
接下來，我們轉到這一段,這一段是用來找出 pivot。
```c
struct item *pivot = list_first_entry(head, struct item, list);
list_del(&pivot->list);
```
比較每一個節點, list 並將小於 pivot 值的節點先從原 list 上移除，再將節點移到 list_less 的第一個節點,大於等於 pivot 值的，先從原 list 上移除,再將節點移到 list_greater 的第一個節點。
處理大於以及小於 pivot的兩個 list 。
```c
list_sort(&list_less);
list_sort(&list_greater);
```
我們將 pivot 加入 list 的第一個節點。
然後將 list_less 串接到 list 的首,list_greater 串接到 list 的尾,由於 list_less 以及 list_greater 都已經排序過了,我們經過以上步驟便可以得到排序完的 list 。
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
```
### 2.針對 Quick sort 提出上述程式碼的改進方案並實作
我想改良的地方為,當我遇見 quick sort 的最糟情況時,我們會出現 O($x^{2}$) 的時間複雜度,綜上所述,我想要進行的改良就是,進行 pivot 選擇時,我們需要慎思,讓我們的選擇不會是最差&很差的。
由上所說,我將會取三個 value 並且找出中間值用它來當作 pivot 。
### 3.引入上述的 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
```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 *first = list_first_entry(head, struct item, list);
struct item *last = lsit_last_entry(head, struct item, list);
struct list_head *s = head->next, *f = head->next;
while (f != head && f != head->prev){
s = s->next;
f = f->next->next;
}
struct item *mid = s;
struct item *mid_target = NULL;//初始值,不重要
int f, m, l = first->value, mid->value, last->value;
int swicher = f > m ? (m > l ? m : ( f > l ? l : f)) : ( f > l ? f: (m > l ? l : m));//找出中間值
switch(swicher){
case f:
mid_target = first;
break;
case m:
mid_target = mid;
break;
case l:
mid_target = last;
break;
}
struct item *pivot = mid_target;//pivot = 中間值
list_del(&pivot->list);
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_sort(&list_less);
list_sort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
### 4.BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻
---
## 第二題
### 解說
首先定義了一個常數 MAX_DEPTH = 512。這個常數用於定義堆疊的最大深度，即可以排序的最大子列表數量。
再來定義了一個靜態函式 list_sort_nr，其參數是一個指向列表頭節點的指針。這個函式用於對一個單向鏈結串列進行非遞迴快速排序。
```c
if (list_empty(head) || list_is_singular(head))
return;
```
我們要判斷是否為空,並且是否只有一個元素,如是,直接 return 。
```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]);
```
接下來需要定義一個堆疊,其大小為 MAX_DEPTH = 512 。
然後,使用 for 迴圈將堆疊中每個元素都初始化為一個空列表。
緊接著,定義一個變數 top = -1 。
然後,使用函式 list_splice_init 將輸入列表加入 stack ,並將 top + 1 。
```c
struct list_head partition;
INIT_LIST_HEAD(&partition);
```
定義一個 partion 指向 list 的 head ,
最後,完成前置步驟之後,我們可以開始進行真正 sorting 的部分,
進入 while 迴圈後,
首先,把 `stack[top]` 目前的資料移到 partition，並初始化 stack[top]
因為 `stack[top]` 目前的資料被拿出來了，所以 top 要 -1 。
而我改進的部分,我希望將`list_splice_init(&stack[top--], &partition);`
合併到下面的 if 判斷之中,
隨之我們需要修改 if 判斷的以下內容:
`&partition` -> `&stack[top]`
這樣就可以省略 else 裡面的:
```c
top++;
list_splice_tail(&partition, &stack[top]);
```
接下來到 if 裡面,
partition 如果不是空或者只有一個元素，就把 partition 依照 pivot 分成 list_less 和 list_greater 兩個 queue。
其中 `list_del(&itm->list)` 以及 `list_move` 有重複的功能。
接下來,將 pivot 連結上 list_less 的尾端,如果 list_greater 不為空,便加入 stack 之中,而 list_less 亦然。
由上可知, stack ***是先放大才放小的***
最後,如果 partion 為空,或是只有一個元素且 stack 之中也只有一個元素,就把 stack 之中的元素加入 head的尾端,
欲達到上述步驟,我們可以使用 `list_splice_tail_init`
## 實驗:第一題與第二題
我想要直觀的看到兩個程式的實際運算數字(ns)
---
## 第三題
### 補全程式碼
### 程式碼說明
這裡我們從`int main(void)`開始看,
設置兩個指標,分別為 p1, p2。
這段程式碼的 list 經過初始化後,進入下面的迴圈,我們需要做 1000 次node[0]~node[999],
將 new->value 以 i 賦值
值得注意的是,當 i == 5 或是 i == 6 的時候, p1 或是 p2 將指向我們重置過的 `&new->xornode`,
#### 1.`xorlist_for_each`
接下來宣告 i = 0,
這個函式處理串列中的每個節點，首先根據目前節點和前一個節點計算出下一個節點的地址(利用題目中上述的方法)，更新前一個節點為目前節點，然後將目前節點更新為下一個節點。這個過程持續到達到串列尾端為止。並且印出每一個 xornode 的 value。
#### 2.`xorlist_for_each_from`
以我的了解,這是上一個巨集的優化版本,他額外新增了 pos1, pos2 的兩個參數,分別代表歷遍範圍的 start & end,當我們在循環時, rp->pos2,
node->pos1, 每次進行迴圈時, rn->rp ^ node, rp->目前位置,
node 會指向下一個節點位置,當 node->tail 時,
代表我們已經結束了我們的<s>歷遍</s> ---
這個巨集的作用是<s>遍歷</s> --- XOR 雙向鏈結串列中從 pos1 到 pos2 之間的所有節點,
它的好處是可以減少一個需要<s>訪問</s> 存取的 pointer (prev),固可減少我們的<s>訪問</s> 存取時間。
:::danger
注意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)，改進你的漢語書寫，留意標點符號的使用，區分逗號 (即「，」) 和 comma (即 `,`)，後者用以分隔英文詞彙和程式碼的 identifier。
:notes: jserv
:::
好的老師，我會注意
#### 3.`xorlist_for_each_from_prev`
與上一個巨集差不多,只是不同之處在於起點和終點的位置相反，且從終點開始往起點<s>遍歷</s> ---。這樣做的好處是可以減少遍歷節點時需要訪問指向前一個節點的指針，從而提高<s>遍歷</s> --- 的效率。這段的改動之處在於,當 node <s>遍歷</s> --- 到起點節點 `&(list)->head` 時,遍歷停止。
#### 4.`xorlist_for_each_prev`
與 `xorlist_for_each` 類似,
不同之處在於從尾部開始往頭部遍歷。這樣做的好處是可以減少遍歷節點時需要訪問指向前一個節點的指針，從而提高遍歷的效率。
#### 5.`xorlist_destroy`
用來刪去一個 XOR 雙向鏈結串列。
函式首先檢查 delete_func 是否為 NULL，如果是,我們可以return NULL。
定義了四個 pointer ：real_prev 指向頭部節點 list->head, node 指向 real_prev 的下一個節點，real_next 指向 real_prev 和 node 的 XOR 值解析出來的下一個節點，以及 tmp 指向 real_prev。
定義完他們之後呢,我們進入一個 loop, 歷遍每一個節點,並且依次刪除,我們先計算出下一個節點的位置,放入 real_next 之中,然後將其餘的 pointer 導向下一個,然後使用 xorlist_del,來進行刪除,直到 node 歷遍到尾部節點 (list)->tail 才算結束。
#### 6.`xorlist_del`
這是一個用於從 XOR 鏈結串列中刪除特定節點的函式
target：欲刪除的節點。
定義三個指標 nn 指向 target 的前一個節點,
an 指向 n 的下一個節點,
ana an 的下一個節點,
然後修改 n 和 an 的 cmp 值，使其跳過 target 節點，接著呼叫 delete_func 函式刪除 target 節點，
最後更新 XOR Linked List 的節點數量並回傳 0 表示成功。
Sign in with Wallet
Connect another wallet