2024q1 Homework2 (quiz1+2)

contributed by <yulin0625>

第一週測驗題

2024q1 第 1 週測驗題

測驗 1

補完程式碼、程式碼解析

list_tail

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

解釋: 這個函式的功能是找到鏈結串列的最後一個節點，並回傳該鏈結串列的最後一個節點的指標。

圖示說明:

Initial:

Step1:

Step2:

list_length

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

解釋: 原理與 list_tail 相同，當 left 每間接指到一個節點，計數器 n 就會增加一，函釋回傳值為該鏈結串列的長度。

quick_sort

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        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 = CCCC;
+        p = p->next;
        list_add(n->value > value ? &right : &left, n);

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

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

解釋: 此函式是運用 Optimized QuickSort — C Implementation (Non-Recursive) 所實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼。

排序過程:

迴圈 while (i >= 0) 用於走訪和排序鏈結串列的不同部分
在迴圈內，選擇串列的第一個節點作為 pivot
走訪 pivot 後的所有節點，並與 pivot 比較值的大小，若較小則將該節點加入 left 串列，否則加入 right 串列
更新 begin 和 end 堆疊
若達到一個只有一個節點的子列表，則將該節點添加到 result 串列中

圖示說明:

選擇第一個節點(節點4)作為 pivot

走訪pivot 後的所有節點，根據它們的值相對於 pivot 的大小，將它們分到 left 或 right 子串列

此時的 left, pivot, right:

更新 begin、end 堆疊，並將 i = i + 2
- 將begin[i] 設為 left
- 將begin[i + 1] 設為 pivot
- 將begin[i + 2] 設為 right

此時 i=2，演算法會對 begin[2] 堆疊所存的 right 串列進行走訪，並選擇節點7，作為 pivot

此時的 begin、end 堆疊

當 begin 與 end 相等(left == right 時)，將節點加入 result 串列，並將 i--

重複直到所有節點排序完成

可改進之處:
目前演算法每次都取第一個節點為 pivot ，若遇到已完成排序的鏈結串列時，就會成為 worst case，時間複雜度為O(n²)
解決方法:

Middle-of-Three: 令 middle = (left + right) /2，比較 left、middle 與 right 這三筆資料，排出中間值，再將中間值與 left 做交換
Random Pivot Selection: 用亂數選取的方式，隨機挑一個值作為 pivot，降低發生 Worst Case 的機率
Median-of-Medians

測驗 2

static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head;
-   struct list_head **tail = AAAA;
+   struct list_head **tail = &head;

    for (;;) {
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
-           tail = BBBB;
+           tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
-           tail = CCCC;
+           tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

static void build_prev_link(struct list_head *head,
                            struct list_head *tail,
                            struct list_head *list)
{
    tail->next = list;
    do {
        list->prev = tail;
        tail = list;
        list = list->next;
    } while (list);

    /* The final links to make a circular doubly-linked list */
-   DDDD = head;
+   tail->next = head;
-   EEEE = tail;
+   head->prev = tail;
}

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
    stk_size = 0;

    struct list_head *list = head->next, *tp = NULL;
    if (head == head->prev)
        return;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

    do {
        /* Find next run */
        struct pair result = find_run(priv, list, cmp);
        result.head->prev = tp;
        tp = result.head;
        list = result.next;
        stk_size++;
        tp = merge_collapse(priv, cmp, tp);
    } while (list);

    /* End of input; merge together all the runs. */
    tp = merge_force_collapse(priv, cmp, tp);

    /* The final merge; rebuild prev links */
    struct list_head *stk0 = tp, *stk1 = stk0->prev;
    while (stk1 && stk1->prev)
        stk0 = stk0->prev, stk1 = stk1->prev;
-   if (stk_size <= FFFF) {
+   if (stk_size <= 1) {
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);
}

運作原理:

第二週測驗題

2024q1 第 2 週測驗題

測驗 1

hlist_add_head: 此函式的功能為將新的節點加入串列的前端。新節點的 next 應指向原本的第一個節點，所以 AAAA 為 h->first

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

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, BBBB) {
+   hlist_for_each (p, &head[hash]) {
-       struct order_node *on = CCCC(p, struct order_node, node);
+       struct order_node *on = CCCC(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

此段程式的功能為尋找 num 的位置，會先計算 hash 取得對應的 hlist_head ,接著走訪該鏈結串列。因此 BBBB 為 &head[hash] ， CCCC 為 list_entry 。

dfs

概念: 由前序可知哪個節點在上面 (越前面的越上面)、由中序可知哪個節點靠左(越前面的越左邊)，於是可得知前序的第一個元素一定是 root 的值，且該元素對應到中序後，左邊的值就在左邊，右邊的值就在右邊。
解釋: 此函式會先取前序的第一個節點，並利用 find 尋找該節點的值出現在中序的哪個位置，並將左側的節點當成左子樹的 root 、左側的節點當成右子樹的 root，繼續遞迴再尋找，直到 inorder 中找不到對應元素。

圖示說明:

若前序為: [3, 9, 20, 15, 7]，中序為: [9, 3, 15, 20, 7]
先查看前序的第一個節點的值 3 ,在中序的位置 idx，此時 idx = 1
左子樹的長度為中序第一個節點和 idx 之間的間隔，也就是 (idx - in_low) ，因此左子樹的範圍為 pre_low + 1 至 pre_low + (idx - in_low)
而右子樹的長度為 idx 到中序最後一個節點的間隔，也就是 in_high - (idx + 1)，因此右子樹在前序的範圍為 pre_high - (in_high - idx - 1) 至 pre_high

測驗 2

LRU(Least Recently Used Cache) 是一種快取的實做方式，概念是儲存最近用過的內容，如果越常被使用，內容會被擺在 List 越前方的位置。如果快取滿了，則會從 List 最末端元素開始移除。

LRUCache : LRU 緩存機制的主體結構。包含以下元素:
- capacity: cache 的最大容量
- count : cache 當前紀錄的資料筆數
- dhead : 儲存 LRU 快取中的節點，並按最近使用的順序排列。
- hhead[] : 儲存每個 hash 對應串列的 head 節點
LRUNode : 是緩存中每個項目的結構，包含以下元素:
- key : 鍵值
- value: 數值
- node : 用於將此 cache 項目連接到 hash 的結構
- link : 用於將此 cache 項目連接到雙向鏈結串列的結構

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, HHHH);
+       LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
-           list_move(IIII, &obj->dhead);
+           list_move(&cache->list, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

先將 key 丟入 hash function 進行計算得到對應的 hash 值。接著從快取中尋找 key 。如果 key 存在於快取內則返回該值，並將該節點移動到鏈結串列的頭部 (表示最近使用)；如果不存在則返回 -1。

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, JJJJ);
+       LRUNode *c = list_entry(pos, LRUNode, node);
        if (c->key == key) {
-           list_move(KKKK, &obj->dhead);
+           list_move(&c->link, &obj->dhead);
            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;
}

此函式將給定的鍵-值對(key–value pair)加入快取中,有以下三種情況

若 key 已存在，則更新對應的值，並將該節點被移動到鏈結串列的前端
若 key 不存在，則判斷快取容量是否已滿
- 若已滿則刪除鏈結串列尾部的節點(最久未使用)，然後將新的鍵-值對插入到鏈結串列的前端
- 若未滿則配置新空間將節點加入串列前端以及加入 hash table 中，並將 count++

測驗 3

目的: 找出 word 參數中最低位的1所在的位置（從0開始計算）

__ffs

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

#if BITS_PER_LONG == 64
-   if ((word & AAAA) == 0) {
+   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;
}

__ffs() 是用來查詢一個 word 中最低位 1 的所在位置, 若 (word & 0xffffffff) == 0 即可知道較低的32位元內沒有任一位元為1, 因此將 word 右移 32 位元再進行檢查。

__clear_bit

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 &= BBBB;
+   *p &= ~mask;
}

此段程式碼是透過 BIT_MASK(nr) 產生出只有第 nr 位為 1 ，其他位皆為 0 的遮罩，並利用 ~ 運算將 mask 反轉成只有 nr 位為 0，最後利用反轉後的遮罩與 addr 做 bitwise and，將該 addr 的第 nr 位清除。

fns

static inline unsigned long fns(unsigned long word, unsigned int n)
{
    while (word) {
        unsigned int bit = __ffs(word);
        if (n-- == 0)
            return bit;
        __clear_bit(bit, &word);
    }

    return BITS_PER_LONG;
}

此段程式碼目的為找到第 n 個被設為 1 的位置，它會不斷地呼叫 __ffs 找到最低被設為 1 的位元，若還不是第 n 個就會使用 __clear_bit 將目前的位元清除，再繼續找下一個被設為 1 的位元。

FIND_NTH_BIT

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

運作原理:
先利用 small_const_nbits 比較要找的位數是否超過限制的 size ，並利用 GENMASK(h, l) 將 h 到 l 間的位元變為 1和 addr 做 & 運算，若 val 有值代表 addr h 到 l 間有位元被設為1，因此再利用 fns 找到為第 n 個被設為 1 的位元並回傳其位置。若不符合 small_const_nbits 就利用 FIND_NTH_BIT 來處理。

FIND_NTH_BIT

#define FIND_NTH_BIT(FETCH, size, num)                          \
    ({                                                          \
        unsigned long sz = (size), nr = (num), idx, w, tmp;     \
                                                                \
        for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
            if (idx * BITS_PER_LONG + nr >= sz)                 \
                goto out;                                       \
                                                                \
            tmp = (FETCH);                                      \
            w = hweight_long(tmp);                              \
            if (w > nr)                                         \
                goto found;                                     \
                                                                \
            nr -= w;                                            \
        }                                                       \
                                                                \
        if (sz CCCC BITS_PER_LONG)                              \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })

FIND_NTH_BIT 能夠搜尋超出單個 BITS_PER_LONG 長度的範圍。如果要查找的位元不在目前處理的字節中，能透過迴圈繼續在下一個 BITS_PER_LONG 長度的區塊中搜尋，直到找到該位為止。
因為 size 可能無法被 BITS_PER_LONG 整除，因此搜尋到最後一輪時應避免找到超出 size 範圍的字元，因此使用取餘數的方式找到最後一個字節所需要搜尋的字元數量，故 CCCC 應為 %。

2024q1 Homework2 (quiz1+2)

第一週測驗題

測驗 1

補完程式碼、程式碼解析

測驗 2

第二週測驗題

測驗 1

測驗 2

測驗 3

Read more

2024 年「資訊科技產業專案設計」HW1

2024q1 Homework1 (lab0)

2024q1 Homework4 (quiz3+4)