2023q1 Homework1 (quiz1)

contributed by < POCHUN-CHEN >
2023q1 第 1 週測驗題

測驗1

struct item 為參考 list.h內的結構體，負責存值與順序的 list 分開寫，往後可以運用 contain_of 。

#include <stdint.h>
#include "list.h"

struct item {                         
    uint16_t i;
    struct list_head list;
};

---

為什麼要用 static inline ?
->主要目的為提升程式速度。

the program behaves the same as if you had not used the inline keyword, except for its speed.

---

用以對節點內含值比較的函式:

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

cmpint 函數返回的整數值代表了比較 p1 和 p2 這兩個指向 uint16_t 數據的指標的結果。這種方式是用於標準庫函數 qsort 中，qsort 函數會根據 cmpint 函數的返回值來對數組進行排序。

比較結果	回傳	Column 3
*i1 大於 *i2	正整數	p1 排在 p2 後面
*i1 等於 *i2	0	排序不變
*i1 小於 *i2	負整數	p1 排在 p2 前面

這樣可以實現對任意類型(因為有 (const uint16_t *) 指標轉型)的數據進行排序的功能。

Q: 為什麼要把兩個指標函式傳進 cmpint 函式，再用 i1 、 i2 來被賦值呢？

p1 從指向 void 顯示轉型成 (const uint16_t *) (這邊是指轉換成指向 const uint16_t 的指標，會有這種括號寫法，是因為 p1 本來就是指標了)。
再賦值給指向 const uint16_t 的 i1 。
宣告 i1 、 i2 才不會影響到本來的。

上述問題

static inline int cmpint(const void *p1, const void *p2)
{
    return *((const uint16_t *) p1) - *((const uint16_t *) p2);
}

顯示指標轉型不會影響到原本 p1 、 p2 的值，因此這樣寫應該更精簡？

顯式的指標型別轉換會更改指標指向型別的編碼方式嗎？

顯式的指標型別轉換通常不會更改指標指向型別的編碼方式。指標的編碼方式（如指標的位元組長度、對齊方式等）是由編譯器和操作系統決定的，與指標指向的型別無關。因此，進行顯式的指標型別轉換時，被指向的二進制內容不會改變，只是指標的型別被視為不同的型別。把顯示指標轉型的指標解構後，會將指向的型別的二進位數值，利用轉換後的型別方式顯示值（可能會與原本不同，但是二進位的部分是一樣的，但有可能長度不同）

---

首先，來看看 list_sort 的程式碼

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);

接下來建立 list_less 、 list_greater ，等等來存放，比原串列中某個數值大 / 小的數值們。

接下來 INIT_LIST_HEAD，負責把新建立的 list_head 初始化，一定要把 prev / next 的前 / 後指標定義。

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

補充說明，以 list_less 為例， &list_less 與 &(list_less.prev) 是同樣地址，因為結構體 list_head 內是按照 *prev 、 *next 排序，所以第一個結構的起始地址就代表結構體的地址。

是否可善用 Micro 來簡化程式碼？作法如下。

LIST_HEAD(list_less);
LIST_HEAD(list_greater);

由於 LIST_HEAD() 本身就包含宣告、初始化，故可以簡化程式碼。

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

LIST_HEAD(list_less) = struct list head list_less + INIT_LIST_HEAD(&list_less)。

---

struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);

接下來就要把剛剛 list_sort 函式的輸入參數引進來比較排序。這時候 item 結構可以用來包含順序串列與其節點內該有的值。之後我們就要來看 list_first_entry() 代表什麼意思，參考list.h中，可得到以下定義。

/**
 * list_first_entry() - Get first entry of the list
 * @head: pointer to the head of the list
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 *
 * Return: @type pointer of first entry in list
 */
#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

這時可以查詢到 list_entry 是 container_of 等價的包裝，符合以 list_ 開頭的命名慣例，此處的 entry 就是 list 內部的節點。

特別注意：在 list_ 系列的 member 都限定在 list_head member 。

如果 list_ 系列的 member ，故意輸入 struct 中，不是 list_head member 的成員，會不會發生錯誤？

接著了解 container_of(ptr, type, member) 的實作手法。
程式碼是從 struct 中的 member 推算出原本 struct 的位址。

• @ptr: 指向 member 的指標
• @type: 結構物件的資料型態
• @member: 結構物件中，成員變數名稱
• Return: 會回傳一個指向包含指定ptr的type結構的指標。

這裡需要討論一下細節，由目前的程式碼中，我們只知道，我們把 list_head 結構的 head 傳進來 list_sort 函式。但熟知 linux 風格的 linked list ，我們知道在這個未經過排序的串列中，也是由 item 結構，包裹著決定串列順序的 list_head linked list 結構。並且第一個 list_head 沒有被包含在 item 結構。

由此我們可以知道， list_first_entry(head, AAA, BBB) 可以看成 container_of((head)->next, type, member) ，藉此得到原本串列的第一個 item 記憶體位置。再將其賦值給 pivot 。

AAA,BBB = ?

由 container_of(ptr, type, member) 可知，

• AAA應為type，在這個程式內應為item。
• BBB應為member，在這個程式內應為list (因為我們知道linux 風格的 linked list ，是由 item 結構包裹，所以成員函數可以用 item 內部的 struct list_head list )。

再將 pivot 利用 list_del(&pivot->list) 從 head 這個串列中移除。

這邊 list_del(&pivot->list) 應該也可以寫成 list_del(&head->next) 但是這樣很不直觀，我們都寫了 pivot ，就直接專注在該節點就好。

---

CCC = ?

觀察到後面出現 cmpint 比較大小的函示，可以推斷 CCC 應該為推進整個串列比較的迴圈函式。為了在宣告完 pivot 後，確保可以比較到串列中的每一個值，再參考輸入參數後，使用函式 list_for_each_entry_safe。

• CCC為list_for_each_entry_safe。

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))d

透過額外的 safe 紀錄每個迭代 (iteration) 所操作的節點的下一個節點，因此目前的節點可允許被移走，其他操作則同為不可預期行為。

---

DDD,EEE = ?

當把 head 串列中的值比較大小後，移動到 list_less / list_greater 的尾部，使用函式 list_move_tail 。

• DDD 為 list_move_tail 。
• EEE 為 list_move_tail 。

---

list_sort(&list_less);
list_sort(&list_greater);

這邊可以看出遞迴的結構，把原本串列按照數值大小分類。依序持續切到排序完成。

比較Merge Sort實作。

---

FFF = ?

當分類完比 pivot 大或小所組成的兩串列後，且經由迭代即可完成排序。將 pivot 與排序後的串列，依序串成與原先串列長度一致的新串列。
將 pivot 加入 list 中的 head ， list_less 用 list_splice 加在 head 後; list_gearter 用 list_splice_tail 加在 head 前。

• FFF為 list_splice_tail 。

---

補充資料：

Timsort

ChatGPT對於Timsort的解釋

Timsort是一種在排序演算法中廣泛使用的混合排序演算法。它由Tim Peters於2002年開發，並在Python中成為預設排序演算法。Timsort結合了插入排序和歸併排序的優點，因此具有高效的排序速度和佔用較小的內存空間。

Timsort的基本思路是將數組分為若干個小塊，對每個小塊進行插入排序，然後將這些小塊進行歸併排序。在實際應用中，Timsort還有一些優化措施，例如檢測已經有序的塊，跳過已經有序的塊，使用二分查找尋找插入位置等等。

Timsort的時間複雜度為O(n log n)，在最壞情況下的時間複雜度為O(n log n)，空間複雜度為O(n)。Timsort是一種穩定的排序演算法，可以處理大規模的數據集，被廣泛應用於Java、Python等編程語言的標準庫中。

Introsort

ChatGPT對於Introsort的解釋

---

延伸問題

• 1. 解釋程式碼運作原理
  1. Check linked list in head has more than two entry and not empty. If not return it.
  2. Use INIT_LIST_HEAD to initialize two list structure we made.
  3. Use list_first_entry to get first entry to set it as pivot.
  4. Delete the pivot from linked list(use list_del)
  5. Compare through all list. Use strncmp to compare item->value to pivot->value, and seperate them to each list_less and list_greater.
  6. Call q_sort to regress list_less & list_greater.
  7. Add pivot to list
  8. Splice list_less before pivot in list.
  9. Splice list_greater after pivot in list.
• 2. 針對 Quick sort 提出程式碼的改進方案並實作
• 3. 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
• 4. BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻

測驗2

參考 list.h

答案解析

GGGG,HHHH = ?

由程式碼可知GGGG，此程式碼與遞迴版本對應，在比對pivot前，必需先確保可以比較到串列中的每一個值，使用函式list_for_each_entry_safe。

當把串列中的值補在list_less和list_greater的尾部，使用函式list_move_tail。

• GGGG為list_for_each_entry_safe。
• HHHH為list_move_tail。

IIII,JJJJ,KKKK = ?

• IIII為&stack[top--]。
• JJJJ為&stack[top--]。
• KKKK為XXX。

---

延伸問題

• 1. 解釋程式碼運作原理，指出設計和實作的缺失
• 2. 比較測驗 1 和測驗 2 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快
• 3. 提出效能改進方案，特別是避免依賴 MAX_DEPTH
• 4. 引入 Introsort ，也就是 quick sort 和 heap sort (或其他可避免前者
  $O(n^2)$ 最差時間複雜度的演算法)。加入 heapsort 的原因為，當 quicksort 迭代
  $2\ast log(n)$ 次後還排序完成，那就很可能會得到
  $O(n^2)$ 時間複雜度。此時切換為 heap sort 能將其時間複雜度控制在
  $O(nlogn)$

測驗3

答案解析

LLLL = ?

MMMM,PPPP = ?

---

延伸問題

• 1. 解釋程式碼運作原理，指出其實作缺陷並改進
• 2. 在 XOR linked list 的基礎，實作測驗 1 和 2 提及的快速排序演算法，注意要引入你改進效能的版本
• 3. 修改 xorlist_destroy，使其不急著釋放記憶體，而搭配 atexit(3) 並在程式即將結束執行時，才批次處理資源釋放