2024q1 Homework2 (quiz1+2)

contributed by < gawei1206 >

第一周測驗題

測驗一

list_tail() / list_length()

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(*left)->next; //AAAA
    return *left;
}

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(*left)->next; //BBBB
    }
    return n;
}

list_tail 和 list_length 都需要從頭逐一走訪所有節點，*left 指向 list 的第一個節點，透過left = &(*left)->next 更改 left 持續走訪下一個節點

q_sort()

以非遞迴的方式來實作快速排序法，透過 begin 與 end 作為堆疊，紀錄串列的範圍，過程中判斷 begin[i] 與 end[i] 是否相等，如果相等就用 list_add 將 pivot 加入到 result 的開頭

if (L)
    list_add(&result, L);

若不相等，透過begin[i] 取出一段串列，並把第一個節點設為 pivot ，走訪串列時將節點的 value 與 pivot 比較，小於等於 pivot 的節點加入 left 串列中，大於 pivot 的節點加入 right 串列中

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

將一段串列分成 left 與 right 後，更新到 begin 與 end 中

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

以圖形化觀察變化

第一輪：

以測驗一的例子來看，第一個點作為 pivot ，以 p 開始走訪每一個節點，將各個節點分配至 left 與 right 之中

分配完成後，以 begin[i] 、 end[i] 指向 left 開始與結束的位址， begin[i+2] 、 end[i+2] 指向 right 開始與結束的位址， begin[i + 1] 、 end[i + 1] 則指向 pivot

第二輪：

這時 i = 2，取出 begin[2] 紀錄的串列，並重複第一輪的操作

第三輪開始：

這時 i = 4 ， begin[4] 指向 NULL ， i--
接下來 i = 3 、 i = 2 、 i = 1 時 begin[i] == end[i] ，將節點加入到 result 中，完成右半部的排序

最後剩下 begin[0] 、 end[0] 中有元素，重複上面的動作

再將這些節點加入 result 中，完成左半部的排序

改善程式碼

• 使用第一周作業用到的 element_t 結構，透過雙向鏈結串列可以更快的存取最後一個節點，避免像函式 list_tail 一樣需要從頭走訪一次
• 在快速排序中 pivot 的選擇會影響執行的效率，選擇當前最大或最小的 value 作為 pivot 是最差的情況，可以透過 median of three 或 median of median 來改善這種情況

測驗二

第二周測驗題

測驗一

以DFS的方法重建一棵樹，首先以 node_add 這個函式將節點加入雜湊表中

for (int i = 0; i < inorderSize; i++)
    node_add(inorder[i], i, inorderSize, in_heads);

node_add

找出此節點應該存放的開頭位址，並以 hlist_add_head 將他加入鏈結串列的開頭

int hash = (val < 0 ? -val : val) % size;
hlist_add_head(&on->node, &heads[hash]); //DDDD

hlist_add_head

從Linux 核心的 hash table 實作可以看到 hlist_node 的結構與使用方式
Linux 核心的 hash table 實作中，用以處理 hash 數值碰撞的 hlist_node 的結構:

struct hlist_node {
    struct hlist_node *next, **pprev;
};

再來可以知道知到 next 指向相鄰的節點本身，而 pprev 指向指著自身節點的指標

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first; //AAAA
    n->pprev = &h->first;
    h->first = n;
}

所以在 hlist_add_head 中要插入一個節點時，會先判斷 hlist_head 是否已經有儲存節點，若存在節點，先將第一個節點 h->first 的 pprev 指向 &n->next，再來將 n->next 指向第一個節點 h->first

find

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]) { //BBBB
        struct order_node *on = list_entry(p, struct order_node, node); //CCCC
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

再算出雜湊值後，找出對應的雜湊表開頭，走訪並找到符合條件的節點，回傳數值在 inorder 中的索引值

dfs

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

最後以dfs重建整棵樹時從 preorder[0] 開始，前序排列中第一個點為 root ，找出他在 inorder 中的索引，計算出 preorder 與 inorder 中左右子樹的索引範圍，透過遞迴重建整棵樹

左子樹

右子樹

延伸問題

測驗二

程式碼解說

在 Leetcode 146. LRU Cache 中我們得知三個函式的功能:

• lRUCacheCreate : 創建大小為 size 的快取
• lRUCacheGet : 如果 key 存在快取回傳 value，否則回傳 -1
• lRUCachePut : 如果 key 存在，更新快取中的 key,value ，否則新增 key,value 至快取中，如果超過快取大小，移除最久沒使用的 key

為了完成程式碼，需了解以下結構:

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

LRUCache 中的 dhead 使用雙向環狀串列來紀錄快取的使用情形，近期有使用過的節點會越靠近 dhead，hhead[] 則是像測驗一中一樣，用雜湊表來紀錄節點，提高存取節點的速度

LRUNode 中的 node 會根據雜湊值被紀錄在對應的 hhead[] 裡，link 則會加入 dhead 的串列中，根據使用情形改變在串列的位置

lRUCacheGet

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); //HHHH
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead); //IIII
            return cache->value;
        }
    }
    return -1;
}

先以 value 計算出雜湊值，再至對應的串列逐一走訪，找出 key 值相符的 cache ，如果資料存在，將找到的節點更新至 dhead 的開頭

lRUCachePut

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); //JJJJ
        if (c->key == key) {
            list_move(&cache->link, &obj->dhead); //KKKK
            cache = c;
        }
    }

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

主要在做三件事，

1. 第一段與 lRUCacheGet 相似，目的是查看欲加入的節點是否存在快取中，如果存在更新他在 dhead 中的位置
2. 再來是如果想加入節點但空間不足的情況，會將最久沒使用的節點刪除，並加入新節點在 dhead 開頭
3. 最後可以加入節點，配置節點需要的空間，插入新節點到雜湊表，也加入到 dhead 開頭

測驗三