2023q1 Homework1 (quiz1)

contributed by < kata1219 >

第一週測驗題題目
實作程式碼

測驗 1

延伸問題

1. 解釋程式碼運作原理

• 使用 Quick sort 排序，在每一輪指定第一個元素做為標準，將 list 分為小於標準的陣列及大於標準的陣列，再分別對兩個陣列進行排序，完成後將排序完的陣列合併。

2. 針對 Quick sort 提出上述程式碼的改進方案並實作

• 目前程式碼會在每次遞迴都產生 list_less 和 list_greater 兩個 list，改成在原 list 內排序可減少記憶體消耗。

3. 引入上述的 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響

4. BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻

---

測驗 2

延伸問題

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

---

測驗 3

剛開始解讀程式碼，推測 xorlist 有兩種可能，一種是會連 head 一併循環的，另一種是不包含 head 形成 circle 的。

我嘗試藉由 xorlist 的操作找出節點的關係。首先，在 xorlist 初始化的方式與 list_head 就有比較大的差異，list_head 是把 next、prev 都指向自身，並在新增節點時會改變 next、prev；而在 xorlist 中是 head 指向 tail，tail 指向 head，且新增節點不會改變 tail。接著觀察 xorlist_add 這個函式，從 lab0 的命名規則推測函式的作用是在開頭新增一個 node。我們可以由程式碼推測出 real_prev 代表 list 的 head，real_next 代表 head 指向的位置，也就是 tail。

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;
    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    if (node == &list->tail)
        real_next = &list->tail;
    else
        real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
    list->count++;

    return 0;
}

延伸問題

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