2024q1 Homework2 (quiz1+2)

contributed by <csotaku0926>

程式碼

第一週測驗題

測驗一

解釋程式碼原理

先就現有的參考資料觀察

從原先作者的圖解，可以知道這段程式是在實現非遞迴的快速排序:

首先 L 會指向陣列的開頭 (從 begin 按照 LIFO 選取)，R 會指向陣列結尾 (從 end 按照 LIFO 選取)

在圖示的初始狀況中，L, R 指向的點不同，因此 pivot 選用陣列的開頭

利用指標 (上圖中的 p ) 走訪整個串列後 (pivot 除外)，將數值較 pivot->value 小的節點放到 left, 反之放到 right。

最後，begin, end 這兩個陣列會新增紀錄三個子串列的開頭與結尾： left, pivot 與 right
也就是說，begin[i] = left begin[i+1] = pivot begin[i+2] = right, end 堆疊同理
(end 存放串列的結尾)

接著下一個 partition 處理位於 i+2 位置的串列 (也就是上圖的 right )，重複上述動作
如果 L, R 指向同個位置，表示已經處理完畢，可以把這個節點放入已排序陣列中

思路：
測驗一中的 quick_sort 函式，並沒有使用到 swap ，反而是利用 begin end 這兩個 stack 達成遞迴的目的。所以 begin 裡面存放的應該是每次遞迴的子串列開頭, end 同理應是存放子串列的結尾。

改進方案

我觀察到的可能改進點如下：

• max_length 的大小
• pivot 的選取

首先討論 max_length 的大小
原先程式使用 2 * list_legnth(list) 作為 begin, end 的大小，這顯得不合理
理論上最多也只會放入 list_legnth(list) 這麼多的節點

為驗證以上說法，來實際測量begin, end 最大使用的長度為何
在 quick_sort 迴圈加入 count_i 變數紀錄最大長度

    left = right = NULL;
    i += 2;
+   count_i = MAX(count_i, i);

並且利用 lab0 裡面的 cpucycles() 測量執行時間

+   int64_t before = cpucycles();
    quick_sort(&list);
+   int64_t after = cpucycles();

以下為以不同長度的串列測試的結果輸出：

Size: 10
Max length: 4
elasped cycles: 22876

Size: 100
Max length: 14
elasped cycles: 93627

Size: 1000
Max length: 22
elasped cycles: 809319

Size: 10000
Max length: 34
elasped cycles: 14269767

Size: 100000
Max length: 60
elasped cycles: 77046564

Size: 1000000
Segmentation fault (core dumped)

可以發現使用到的長度遠小於預期，原先的實作甚至會導致 Segmentation fault
於是將程式改為：

int n = list_length(list);
int max_level = n * 0.25 + 20;

這時分配 1000000 個節點，也不會出現 Segmentation fault 了

談到 pivot 的選取，可以發現原先程式選用開頭作為 pivot
這麼做有個問題，若是輸入陣列節點數值是完全遞增或是遞減的狀況，會導致 worst case 的發生
因為每次都會將陣列分割成一個只包含 pivot 節點，以及另一個包含所有其他節點的子串列
顯然，這會讓時間複雜度退化為

$O(n^2)$

其中一個常見的作法是隨機選取 pivot。我的作法是利用 rand() 選取隨機節點後，將其移動到開頭。

// swap the random value with head
void swap_random_pivot(node_t **list) {
    if (!list)
        return;
    
    int len = list_length(list);
    srand(time(NULL));
    int r = rand() % len;

    node_t **rand_node = list;
    while (r > 1) {
        rand_node = &(*rand_node)->next;
        r--;
    }

    node_t *tmp = (*rand_node)->next;
    (*rand_node)->next = tmp->next;
    list_add(list, tmp);
}

以下是原來程式，對於每個長度 (10, 100, …, 100000) 執行十次後取執行時間與最大堆疊長度的中位數

Size: 10
Max length: 8
Elapsed Cycles: 5611

Size: 100
Max length: 16
Elapsed Cycles: 69692

Size: 1000
Max length: 26
Elapsed Cycles: 916829

Size: 10000
Max length: 38
Elapsed Cycles: 2481397

Size: 100000
Max length: 48
Elapsed Cycles: 50033392

以下是我在加入 swap_random_pivot 後取得的數值

if (L != R) {
+   swap_random_pivot(&L);
    node_t *pivot = L;
    value = pivot->value;
    ...

可以看到最大的深度確實有所減少，但整體花費 cycle 反而上升不少

Size: 10
Max length: 4
Elapsed Cycles: 100035

Size: 100
Max length: 14
Elapsed Cycles: 814267

Size: 1000
Max length: 26
Elapsed Cycles: 3605319

Size: 10000
Max length: 38
Elapsed Cycles: 18732945

Size: 100000
Max length: 48
Elapsed Cycles: 222897390

結合 List API

本項實作使用 lab0-c 中的 list.h

由於是雙向鍊結串列，因此在 quick_sort 中不再需要以 end 紀錄結尾，可以進一步節省空間使用量

修改過的 quick_sort 初始版本會有陷入迴圈的問題
要留意 list API 與單向鍊結中的節點的型態差異，並且注意正確的函式呼叫
quick_sort 程式碼

避免最差狀況的實作

根據 StackOverflow 的討論，PRNG 的選取不僅會影響執行速度，有時在安全性的考量也是個問題 (e.g. 如果使用顯著的PRNG，可能被有心人士更改節點順序，導致一直選到「不好的」 pivot )

一個常見的作法是 median-of-three ，考慮以下程式碼 (原著)

int medianThree(int a, int b, int c) {
    if ((a > b) ^ (a > c)) 
        return a;
    else if ((b < a) ^ (b < c)) 
        return b;
    else
        return c;
}

我們比較三個數值： 開頭，中間點，以及尾端
這麼一來，可以優化遞增或遞減串列的最差狀況
但是排序的對象是鍊結串列，如果要找中間點需要耗費

$O(n)$ 的時間搜尋。這種策略用在鍊結串列上還能勝過隨機指定嗎？

測驗二

解釋程式碼原理

在 timsort 函式中，先將給定的循環串列拆解成 null-terminated 的串列
接著透過 find_run 找尋當前串列的下一個 run ，處理規則如下

• 如果下個節點的數值比當前的小，回傳反轉後的序列
• 反之，回傳由當前節點開始，數值遞增的序列

考慮以下狀況

由於 list 指向的節點數值比 next 還要大，適用於狀況一
原始程式碼：

do {
    len++;
    list->next = prev;
    prev = list;
    list = next;
    next = list->next;
    head = list;
} while (next && cmp(priv, list, next) > 0);
list->next = prev;

我想了很久才逐漸了解其中邏輯

新增一個暫時指標 prev ，指向 NULL
在這個迴圈中，next 指向下一個 run 開始的節點，head 指向這個反向序列的開頭
list 指向單調遞增的子串列，迴圈中 list->next 指向 prev 代表 list 中的順序和原先的遞減串列是反向的
也就是最後的結果會像這樣

不論哪種狀況，回傳的 pair 中 head 都會指向一個遞增子串列的開頭，next 則是下一個 run 的開頭，並將子串列的長度存在 head->next->prev 當中

處理好 run 之後，進行 merge_collapse
此函式的目的是合併 run 至兩個以下，並根據堆疊前三個 run 長度的大小關係決定要合併的點：

• 若 tp->prev->prev 長度小於 tp 以及 tp->prev 的長度總和，選取後兩者較小的串列合併
• 若 tp->prev 長度小於 tp，選取長度較小的 tp 合併

直到所剩的堆疊小於三個，或是長度不滿足上述關係後，才進行統一融合

最後，由於原先的串列被拆解成一個個堆疊的架構，需要透過 build_prev_link 恢復成雙向串列

嘗試改進

作業說明中至少提到兩點可以改進的地方：

• 設計 minrun 使得串列分割成 2 的冪
• Galloping mode 的實作

參考 Tim 在 github 的解釋:

This is easier to do than it may sound: take the first 6 bits of N, and add 1 if any of the remaining bits are set.
In fact, that rule covers every case in this section, including small N and exact powers of 2; merge_compute_minrun() is a deceptively simple function.

以 N = 2112 而言
2112 化成二進位是 0b100001000000
取前六位: 0b100001 –> 33
剩餘的 bit 沒有被設置的，所以 33 就是預期的 minrun

對應程式碼:

static size_t find_minrun (struct list_head *head) 
{
    size_t len = list_length(head);

    // find first 6 bit & add up remain bits
    size_t minrun = 0;

    while(len >> 6) {
        minrun += (len & 1);
        len >>= 1;
    }
    
    minrun += len;
    
    return minrun;
}

目前這方面卡在 insertion sort 的部份有實作錯誤，一直無法跳出迴圈，待修正
有 bug 的程式碼

另外，我發現 main.c 沒有將動態分配的記憶體釋放

free(samples);
free(warmdata);
free(testdata);

第二週測驗題

測驗一

解釋程式碼原理

初始化和二元樹節點一樣多的 hlist_head
給定 inorder 以及 preorder 序列，將每個 inorder 節點放入 order_node 這個架構後，
利用 node_add 將節點插入 hlist_head 鍊結中

以題目舉的範例而言：

每個 hlist_head 都有個稱為 first 的指標，用來指向已經在這個鍊結的頂端節點 (初始指向 NULL)
next 指向下一個節點，pprev 較為特別，指向上一個節點指向自己的指標

以上述案例，假設節點0和節點1被分配到同一個 hlist ，數值 9 的節點會先進入，再來是數值 3
只有第一個進入的節點的 next ，也就是數值 9，會指向 NULL

而建立 inorder 雜湊表的目的，是要在 preorder 序列中找到對應的 inorder 元素
引用題目的圖表：

第一個 preorder 元素是樹根，而我們在 inorder 序列的第二個元素找到它
這代表在第二個元素之前的屬於左半邊樹，反之則是右半邊樹。這種問題很適合以遞迴解決

嘗試改進

顯然，在 find 函式中並未實現 hash function，而是單純以 hlist_for_each 搜索

完整的檢測程式碼可以參考我的 github

for (int i=0; i<test_time; i++) {
    start = clock();
    struct TreeNode *test_root = buildTree(preorder_list, Tree_size(depth), 
                                           inorder_list, Tree_size(depth));
    end = clock();
    if (!checkTree(root, test_root)) {
        printf("Check tree failed :(\n");
        success = false;
        break;
    }

    total_time_used += (end - start);
}

if (success)
    printf("elapsed avg time: %f\n", 
           (double)(total_time_used) / CLOCKS_PER_SEC / test_time); 

作為測試資料，我建立一顆長度為 d 的完整二元樹
就原始的程式碼而言，當 d = 10，耗費時間約為 0.0012 秒

由於原先程式中已經宣告足夠數量 (等同於節點數量) 的 hlist_head ，直接使用簡潔的雜湊函數

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &heads[hash]) {
    // ...
}

執行時間來到 0.000137 秒，顯然這是空間換取時間的策略
有沒有可能使用少一點空間，時間效能上又不會影響太多？

Linux 核心的 cgroups 相關原始程式碼

什麼是 cgroup ？ 和樹有什麼關係？
根據官方 github:

cgroup is a mechanism to organize processes hierarchically and
distribute system resources along the hierarchy in a controlled and
configurable manner.

而 cgroups 是一個樹狀的架構，每個系統行程都屬於一個且唯一的 cgroup
cgroup 可分為兩個部份 – 核心 (core) 以及控制器 (controller)
控制器的作用是分配一種特定類型的系統資源給階層架構

查閱 linux kernel

struct cgroup_subsys_state *
css_next_descendant_pre(struct cgroup_subsys_state *pos,
			struct cgroup_subsys_state *root)
{
	struct cgroup_subsys_state *next;

	// ...

	/* no child, visit my or the closest ancestor's next sibling */
	while (pos != root) {
		next = css_next_child(pos, pos->parent);
		if (next)
			return next;
		pos = pos->parent;
	}

	return NULL;
}

雖然說是 preorder-walk ，卻沒有看到類似 left, right 的子節點架構
其利用 css_next_child 尋找下一個子節點，若不存在，則返回到上一層重新搜索

測驗二

解釋程式碼

首先透過 lruCacheCreate 建立需要的架構
初始化一個 LRUcache ，這個架構有以下成員:

• 一個 list_head dhead，是存放節點的架構。當節點被存取時，會重新放到 dhead 的開頭，這時若要移除 least recent 的節點，移除其中排位最後的節點
• 數量為 capacity 的 hlist_hea hhead[], 是用來查找節點的雜湊表
• capacity，代表 LRUcache 可容納的節點數量
• count, 代表目前 cahce 已存放的節點數量

而 LRUNode 則是節點架構，正如圖上方指向 hlist_head, dhead 的架構

嘗試改進

注意到 Get Put 所使用的雜湊函式

int hash = key % obj->capacity;

十分簡潔易懂，但相對碰撞的機率很高

我嘗試使用 linux核心 引進的 multiplication-based 雜湊函式實作

unsigned int hash_32(unsigned int key, unsigned int bits)
{
    return (key * GOLDEN_RATIO_32) >> (32 - bits);
}

初步使用 clock() 進行測試時間

    start = clock();
    
    for (int i=0; i<100; i++)
        lRUCachePut(lru_cache, rand(), 111);
    
    for (int i=0; i<10; i++)
        lRUCacheGet(lru_cache, rand()); 
    
    end = clock();

leetcode 的要求

The functions get and put must each run in O(1) average time complexity.

提到常數時間，可以使用 lab0-c 的 dudect 測試程式來檢驗

測驗三

雜記

關於 hlist_del 利用間接指標完成操作的部份，確實讓我思考了很久，於是在這裡紀錄
以下是節錄自 Linux 核心的 hash table 實作 的擷圖，我覺得這張圖很好的解釋了原理

void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
        next->pprev = pprev;
}

假設今天要移除 node 2，有兩件事情需要完成，那如何完成？

• 將 node 1->next 指向 node 3 (node 1 的下一個節點改為 node 3)
  • 這時 **prev = n->pprev 是指向 node 1->next
  • next 指向 node 3
  • *prev = next : 更改 prev 間接指標指向的指標。這麼一來，不需要存取 prev->next 也能修改其值。同時，也不需以特例考慮 prev 是否為 NULL
• 將 node 3->pprev 指向 node 1 「指向 node 2」 的 next 指標 ( node 3 的前一個節點改為 node 1)
  • next 有可能指向 NULL (如 node 3)