2024q1 Homework2 (quiz1+2)

contributed by <ShawnXuanc>

第一週測驗

測驗1

運作原理

測驗 1 的程式碼內容，實作一個非遞迴的快速排序，排序的對象為鏈結串列，使用 node_t 的指標陣列來模擬 stack 的部分

int max_level = 2 * n;
...
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;

在這次測驗中所使用的演算法為非遞回版本的 quick sort ，首先會先取得傳入的 list 長度，並將 max_level 設置為長度的兩倍即 2 * n ，並使用 left 跟 right 來暫存經由判斷比 pivot 大以及比 pivot 小的節點

if (L != R) {
    node_t *pivot = L;
    value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    while (p) {
        node_t *n = p;
        p = p->next; 
        list_add(n->value > value ? &right : &left, n);
    }
        ...
    }

迴圈中設定當前 pivot 並將 p 移動到 pivot 的下一個節點再將 pivot 斷開串列的連結，接下來在內層的 while 迴圈中可以看到會先將 n 指向目前鏈結串列中的第一個元素也就是 p，在移動將 p 的指標往前移動，最後依造與 pivot 的大小判斷分別將比 pivot 大的節點加入 right 比 pivot 小的節點加入 left 之中

• p 以及 pivot

• 進入迴圈 n = p 以及 p = p->next

• 將比 pivot 小的節點的放置到 left 比 pivot 大的節點的放置到 right

    begin[i] = left;
    end[i] = list_tail(left);
    begin[i + 1] = pivot;
    end[i + 1] = pivot;
    begin[i + 2] = right;
    end[i + 2] = list_tail(right)

• 使用 begin 以及 end 來記錄 left 跟 right 的頭以及尾

下一次開始的位置會從 begin[i+2] 開始並將鏈結串列進行切割直到剩下一個節點為止，接著依序將切割過後的串列加入到 result之中，形成一個排序好的鏈結串列

改善方式

在這邊將長度設置為 2 * n 其實是沒有必要的，因為在將節點以指標陣列暫存時最多只會用到 n 個空間因此可以將 max_level 的大小進行調整來節省空間

而再將串列的尾部元素的位置賦值給 end[i] 時 會用到 list_tail 函式需要 O(n)的時間來遍歷整個串列，因此可以考慮使用其他的資料結構像是環狀的鏈結串列，用這樣的方式就可在 O(1) 的方式來取的串列的尾端

為了避免 quick sort 在 partition 的階段選擇到最大最小，可以有更多的pivot 選擇來進行優化以防止 worst case

測驗2

運作原理

Tim sort 演算法結合了 merge sort 以及 insert sort 的合併方式，在排序一開始會先找尋序列中已經排序好的部份，藉由 find_run來尋找，若找到的串列為遞減的串列，會將串列反轉直到遇到遞增的並更新指標內容，若是遞增的串列，則將指針向後移動，直到遇到遞減的

    static struct pair find_run(void *priv,
                            struct list_head *list,
                            list_cmp_func_t cmp)
{
    size_t len = 1;
    struct list_head *next = list->next, *head = list;
    struct pair result;

    if (!next) {
        result.head = head, result.next = next;
        return result;
    }

    if (cmp(priv, list, next) > 0) {
        /* decending run, also reverse the list */
        struct list_head *prev = NULL;
        do {
            len++;
            list->next = prev;
            prev = list;
            list = next;
            next = list->next;
            head = list;
        } while (next && cmp(priv, list, next) > 0);
        list->next = prev;
    } else {
        do {
            len++;
            list = next;
            next = list->next;
        } while (next && cmp(priv, list, next) <= 0);
        list->next = NULL;
    }
    head->prev = NULL;
    head->next->prev = (struct list_head *) len;
    result.head = head, result.next = next;
    return result;
}

• find_run 會先比較串列的遞增關係找出已排序好的串列，若找到的是遞增的串列則回傳，若找到的是遞減的則進行反轉再回傳

static struct list_head *merge_collapse(void *priv,
                                        list_cmp_func_t cmp,
                                        struct list_head *tp)
{
    int n;
    while ((n = stk_size) >= 2) {
        if ((n >= 3 &&
             run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
            (n >= 4 && run_size(tp->prev->prev->prev) <=
                           run_size(tp->prev->prev) + run_size(tp->prev))) {
            if (run_size(tp->prev->prev) < run_size(tp)) {
                tp->prev = merge_at(priv, cmp, tp->prev);
            } else {
                tp = merge_at(priv, cmp, tp);
            }
        } else if (run_size(tp->prev) <= run_size(tp)) {
            tp = merge_at(priv, cmp, tp);
        } else {
            break;
        }
    }

    return tp;
}

下一步要藉由 merge collapse 來判斷串列是否有符合條件，若不符合則將兩個 run 進行合併，合併完離開函式之後，再將所有的 runs 進行合併

條件為要長度要符合：

1. A > B + C
2. B > C

第二週測驗

測驗1

藉由給定的二元樹前序以及中序來進行重建，而在測驗一中所使用節點的資料結構為 hlist_node ，在前面由一個 hlist_head 為開頭而後接著 hlist_node的形式這邊的 pprev 是以 **preve 的方式與前一個節點做連接，藉由這樣指標的指標可以省去在第一個 hlist_node 的 pprev 指向 head 時因結構不同無法指向的問題，也可以在操作上更加便利

在測驗的這個程式的大致想法為，先將二元樹的 inorder 的內容記錄到 hash table中儲存起來以便用O(1)的時間找到所對應的位置，再利用 dfs 遍歷 preorder 的內容，使用 find 來找到 inorder 與 preorder 所對應的位置來進行遞迴重新建立一顆二元樹

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &heads[hash]);
}

使用 node_add 函式來將節點加入到 hlist 中讓之後再進行 dfs 時可以快速的取的 inorder 的資訊

    static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

用來建立二元樹的程式碼內容，使用 tn 作為 TreeNode 的指標 tn 的 val 為 preorder 陣列中的元素在設定好 tn 的內容之後會使用 find 來找到 inorder 在 hlist (Hash Table) 中與 preorder 的值相對應的位置即為子樹中 root 的位置

藉由 root 的位置可以切割陣列的左右兩邊也就是 [(tn->left) root (tn->right)] 左右遞迴建立左子樹與右子樹

tn->left 的 dfs 參數 idx - in_low為在 inorder 陣列中從起點到所選擇的 root 的節點個數，用這樣的方式來取得 pre_high 的值就可以對應到左半邊的節點個數，另一邊 tn->right 同理也是

改善方法

可以使用更簡單的資料結構來建立 hash table 而不用用到 hlist_node 這樣較為複雜的結構，以節省實作的複雜以及空間的利用

記憶體空間的釋放，在最後將二元樹重建之後未釋放 hash table 的記憶體空間，
可以在 return 之前將不使用的 hash table 釋放掉以避免記憶體洩露的問題

hash function 使用較為簡單的方式，可以考慮使用更為複雜的 hash function 來減少碰撞的發生

Linux 相關原始碼

pre-order-walk 的應用在 cgroup/cgroup.c 裡面的一個函式 css_next_Descendant_pre

cgroup_iter 中有提供不同的探訪方式

cgroup 的功能在於限制、控制與隔離 process 所使用到的系統資源包含

• 資源限制
• 優先權
• 結算
• 控制

測驗2

運作原理

LRU Cache 的運作原理為最近最不常使用的會被替換掉，而每當有使用時會將使用的元素值更新，而當 Cache 的容量滿了的時候會進行移除，移除的對象即為最不常被使用的

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

根據 hash 的值來判斷所要的 key 值是否存在於 hlist 之中若存在就將其移動到鏈結串列的最前端，代表為最新使用到的，如果不存在則回傳 -1

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *c = list_entry(pos, LRUNode, node);
        if (c->key == key) {
            list_move(&c->link, &obj->dhead);
            cache = c;
        }
    }

   .....
}

函式用來將 key 值放入到 cache 之中，一開始會先計算 hash的值並判斷 key值是否存在於 cache 之中，如果存在會將 key 值在 hash table 之中的位置進行更新，也就是移動到前面的位置，代表為最新使用到的，並且記錄起來，以便判斷是否有找到

if (!cache) {
    if (obj->count == obj->capacity) {
        cache = list_last_entry(&obj->dhead, LRUNode, link);
        list_move(&cache->link, &obj->dhead);
        hlist_del(&cache->node);
        hlist_add_head(&cache->node, &obj->hhead[hash]);
    } else {
        cache = malloc(sizeof(LRUNode));
        hlist_add_head(&cache->node, &obj->hhead[hash]);
        list_add(&cache->link, &obj->dhead);
        obj->count++;
    }
    cache->key = key;
}
cache->value = value;

接續上方的程式碼藉由 cache 來判斷是否有找到這個值，如果沒有找到的話則判斷目前 cache 的容量有沒有滿，如果滿了就將最後一個串列的元素移動到第一個代表刪除了最後一個節點並且新增一個節點，並刪除最後一個元素在 hlist 中的內容再加入

若 cache 的容量未達上限，則新增一個節點並更新 hash table 以及串列的內容，最後再把 key 跟 value 重新設定

改善方式

Linux 相關原始碼

LRU cache

測驗3

#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG))

這個聚集的功能在於將位於 nr 位置的 bit 設置成 1 而 % BITS_PER_LONG 是要確保 nr 介於 0 ~ BITS_PER_LONG - 1 之間

    static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;

#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 0) {
        num += 32;
        word >>= 32;
    }
#endif
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}

用來找到 word 之中的第一個 bit 為 1 的位置，一開始先檢查是否為 64 位元的系統，使用 num 來記錄最低位元的位置依序判斷若沒找到就將 word 向右移直到找到 bit 為 1 的位置

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= ~(mask);
}

函式的作用在於將指定的 bit 清除掉 mask 的用意在於設定要遮罩的位元位置，最後在用 not 的方式將其變成 0， 在用這個 0 為元的位置做 and 來將 mask 位置的位元消除成 0

#define GENMASK(h, l) \
    (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

這巨集的功能在於可以將 h ~ l 位元的位置設定成 1 其他設定成 0，在這個巨集中 (~0UL) 為一個位元皆為 1 的數 ，而 1UL << (l)) 為將位置 l 設置成 1 再使用位元皆為1 的數去減掉第 l 個位置為 1 的數，使用這樣的方式可以獲得一個 ....111101111 這樣的結果，最後再加上 1 就可以藉由進位的方式得到 ....111110000 ，得到 l之前皆為 0， 在用 (~0UL >> (BITS_PER_LONG - 1 - (h)))) 可以想為將低位元的 h + 1 個位置都設定為 1 其他為 0也就是 h = 2 時右邊會是 111，藉由這樣的方式來將 h ~ l 的位元設定成 １

Linux 相關原始碼

bitops linux kernel