2024q1 Homework2 (quiz1+2)

contributed by < wu81177 >

第一周測驗題

測驗一

參考 Optimized QuickSort — C Implementation (Non-Recursive)，實作非遞迴 (non-recursive; iterative) 的快速排序法。此處提到的方法是以 swap 為主體，利用 L 與 R 去紀錄需交換的數量，再用 begin[] 與 end[] 作為堆疊，用來紀錄比較的範圍

node_t

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

可以看到此結構用於單向鏈節串列，而 left 和 right 是在遞迴版本 quick sort 會使用，在非遞迴版則沒有使用到

list_tail

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

其目的是要找到鏈節串列的最後一個節點
在以下程式碼被使用： end[0] = list_tail(list) ，其中 list 為指向頭的指標，被帶入 left ，因此可以推斷 AAAA 為 (*left)->next 才會使得 left 從頭出發在迴圈中前進，當 left 間接指向最後第二個節點時會再前進最後一步，這時 (*left)->next 為 NULL 結束迴圈

list_length

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

這個函式是要走訪鏈節串列，過程中計數，最後回傳節點個數
同理， BBBB 也是 (*left)->next ，這樣才能走訪鏈節串列
而由於迴圈中止條件是找到空指標，此函式不能用於環狀鏈節串列

非遞迴 quick_sort

運用 Optimized QuickSort — C Implementation (Non-Recursive) 所實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼
值得注意的是，此版本使用 begin[] 和 end[] 作為堆疊去取代遞迴的功能
若 L 不等於 R ，走訪 begin[i] 指向的鏈結串列，因此 CCCC 是 &p->next
而 list_add(n->value > value ? &right : &left, n) 可以看出 left 和right 為被 pivot 分開節點的鏈節串列入口，最後存到 begin[] ，如圖：

而對所有 i ，end[i] 則指向 begin[i] 所指鏈節串列的最後一個節點，因此 DDDD 為 list_tail(&left)，EEEE 為 list_tail(&right)

避免最差情況

Quick sort 的最差情況就是每次 pivot 都選擇到待排序數列的最小（或最大）值，如此一來每次切割只能將一節點排序，需要切割

$n$ 次，每次切割的代價為

$O(n)$ ，因此最差情況的時間複雜度為

$O(n^2)$
通常發生在已經大致排序完的數列，有幾種方法可以解決：

1. 三數取中法：選擇數列頭尾和中間三者的中位數作為 pivot
2. 隨機選擇法：隨機選擇數列中某元素作為 pivot
3. 混用插入排序：當數列切割至長度小於某值改用插入排序法

使用 Linux 核心風格的 List API 改寫

若要使用 linux/list.h 來實作， node_t 應該要改為以下這樣，加入 list_head 用來串連鏈節串列

typedef struct {
-   struct __node *left, *right;
-   struct __node *next;
+   struct list_head list;
    long value;
} node_t;

其他操作函式可參考上次作業 lab0-c 的部份，做以下取代

1. void list_add(node_t **list, node_t *node_t)
   => static inline void list_add(struct list_head *node, struct list_head *head)

2. list_tail的部份由於 list_head 是雙向的，只需要從 head 往前一步，做以下改寫：

   ​​​​node_t *list_tail(struct list_head *head)
   ​​​​{
   ​​​​    node_t *left = list_entry(head->prev, node_t, list);
   ​​​​    return *left;
   ​​​​}
   

3. int list_length(node_t **left)
   => int q_size(struct list_head *head)

4. void list_free(node_t **list)
   => void q_free(struct list_head *head)

5. node_t *list_construct(node_t *list, int n)
   => bool q_insert_head(struct list_head *head, char *s)

快速排序的程式的部份只要再根據以上取代做一些調整就能完成實作

測驗二

Timsort

結合插入排序和合併排序，對於部分已排序的資料有出色的表現

1. 切割已排序的子數列 (run):
   • 將數列拆分成單調的子數列，在此子數列稱為 run
   • 將遞減的 run 反轉，使全部 run 遞增
2. 選擇 minrun ：
   • 若 run 的數量等於或者略小於 2 的冪，效率會最高
   • 為了滿足上一點，定義 minrun 表示 run 的最小長度
   • 若長度太短就用二分插入排序，將後面的元素插入前面的 run
   • 實際操作中，將 n 不斷除以 2 直到 n 小於預設的最小合併長度（MIN_MERGE），只要有任何一次不能整除 2，最終結果就加一
3. 使用堆疊：
   • 為了避免使用大量記憶體，採用一組堆疊來暫存 run
   • 運用 merge_collapse 函式來檢查堆疊頂端的 3 個 run 是否平衡，並且決定是否合併
4. Galloping mode：
   *　合併相鄰子數列時，使用臨時記憶區域，大小設定為兩個子數列中較短者的長度
   *　暫存較短者 A，找較長者 B 首元素在其排序位置，將小於 B 的部份放回A ，在剩餘 A 中找在 B 中位置，反覆進行

timsort.c

merge

此函式用於合併兩個有序的 run ，頭分別為 a 和 b
struct list_head *head 用來表示合併後 run 的頭部
struct list_head **tail 為指向新 run 尾部的指標，一開始應指向頭部，等待後面更新，因此 AAAA 為 &head

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

上面為 a, b 兩數列比較元素大小的部份，較小或相等時應把尾部設為 a 的元素，反之設為 b 的元素，這樣才能排進合併後的數列，所以 BBBB 應為 &a->next ， CCCC 應為 &b->next ，直到有一方先結束，把另一個數列剩下的部份接上去再退出迴圈，完成合併

build_prev_link

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;
    EEEE = tail;
}

這個函式是用於將 list 中的元素逆向走訪，放置到 head 和 tail 之間的環狀鏈節串列 ，因此迴圈走訪完後根據註解的提示，要將 head 和 tail 雙向串連，因此 DDDD 為 tail ->next ， EEEE 為 head->prev

timsort

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) {
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);
}

此函式是timsort 演算法的主要函式，將一個雙向鏈表進行排序
在 do-while 迴圈中透過 find_run 找到 list 中的 run 並使用 merge_collapse 確保堆疊上的 run 長度保持平衡
當 list 被讀取完後使用merge_force_collapse 強制執行堆疊的合併，以確保堆疊中的 runs 長度平衡
最後階段如果 stk_size 小於 FFFF ，則不用再合併，否則要用 merge_final 執行最後合併，因此 FFFF 應為 1

第二周測驗題

測驗一

給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹
前序：訪問順序是「根左右」
中序：訪問順序是「左根右」
後序：訪問順序是「左右根」
因此前序越前面的數在樹的越上面，中序越前面數越左邊
題目程式中使用深度優先搜尋函數 dfs 建構二元樹，並在 buildTree 函式中建立雜湊表給 dfs 查找

dfs

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

preorder：前序走訪結果陣列
pre_low 和 pre_high：前序走訪結果陣列的當前走訪範圍
inorder：中序走訪結果陣列
in_low 和 in_high：中序走訪結果陣列的當前走訪範圍
in_heads：中序走訪的 hlist 頭部陣列
size：中序走訪結果陣列的大小
這個函式遞迴過程中每一次都在前序走訪中取得當前的根節點，並在中序走訪中找到根節點的位置，然後遞迴構建左子樹和右子樹直到當前範圍為空，建構完成整個二元樹

hlist

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

static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
    h->first = NULL;
}

hlist 指的是雜湊表鏈節串列，當發生碰撞時便會以 hlist 儲存元素，這裡以 hlist_node 定義了節點，根據 Linux 核心的 hash table 實作，可以看到和 next 不同的是 pprev 為間接指標指向前一個元素的 next ，如此一來就可以消除第一個元素的特例， list_head 中的 first 和一般元素中的 next 無異
若是用典型的雙向鏈節串列，當要移除第一個節點時，必須做出額外的操作來更新 list_head 指向的節點，除了移除的目標之外，還必須傳入 list_head
最後，hlist_head 作為鏈節串列的頭，也代表了雜湊表的一個 bucket ，包覆在 hlist_node 外面
每當要使用一個 bucket 的時候，便會用 INIT_HLIST_HEAD 初始化，供日後連接元素

hlist_add_head

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

每當要加入一個元素進入 hlist 便會使用這個函式將新元素作為 first
函式首先判斷 first 是否為空，若不為空就代表 first 已經存在元素，函式結束前會被新元素推擠到第二個，因此 AAAA 應為 h->first
若 first 為空一樣成立 AAAA 為 h->first 一樣成立，所以最後一個元素的 next 才會指向 NULL

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

此函數是用來在一個 bucket 鏈節串列中用來找到某個 num 對應的索引值 idx ，
透過 num 絕對值對 size 取餘數後得到 hash 值，從 struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads)) 可以看出 in_heads 是一指標陣列，用來指向結構， in_heads 會用來代入 find ，因此可以推斷 hash 值是作為此陣列的索引，因此 BBBB 應為 heads[hash]
而 CCCC 應為 list_entry ，因為要從 hist_node 找到外層的 on 才能進入找到裡面的 val

node_add

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, DDDD);
}

此函式的目的是為了將新的 order_node 加入到 hlist ，將 val 和 idx 寫入後，接下來與上段同理， hash 值應作為陣列索引，因此 DDDD 應為 heads[hash]

測驗二

LRU Cache（Least Recently Used Cache）是一種常見的快取管理策略。在這種策略下，每當訪問一個資料時，就會將該資料移到快取的頭部，表示這個資料最近被使用過，當快取已滿時，會將最近最少使用的的資料，也就是最尾部的資料刪除以釋放空間給新的資料，這樣的做法是假設最近使用的資料更有可能在未來被再次使用
在題目程式碼中，為了降低搜尋的時間複雜度，使用雜湊表，結構和上一題類似，函式和結構是以 hlist 為關鍵字，而串連 LRU Cache 的鏈節串列以 list 為關鍵字

hlist_del

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

這題 hlist 的部份和上一題一樣，唯獨多了 hlist_del 的部份，作用就是移除 hlist 中的節點，函式最後的 if 是處理當節點為最後一個的特例，當 next 不為空的時候代表不是最後一個節點，這時 pprev 應改為前面節點的 pprev ，應此 EEEE 應為 next->pprev

LRUCache & LRUNode

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;

第一個結構用來代表一個 cash ， hhead 陣列內的每個元素代表雜湊表的一個 bucket， dhead 則是 LRUChe 的頭
而 LRUNode 代表一個元素， node 用在雜湊表的連接， link 則用在 LRU 順序的連接，一個 LRUNode 有兩種指標串連

lRUCacheFree

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, FFFF);
        list_del(GGGG);
        free(cache);
    }
    free(obj);
}

這段程式碼是釋放 LRUCache 的結構和其包含的所有節點
首先通過 list_for_each_safe 走訪 dhead ，因此 FFFF 應為 link ，這樣才能一次走訪全部，若是用 node 走訪要以 hhead 陣列的多個元素為入口
參考 list_del 的函式定義，GGGG 應為 pos ，刪除當前節點

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

此函式用於從 LRU 快取中獲取給定 key 的值，先取餘數找到 hash 值，在 hhead 找到對應的 bucket 然後走訪 hlist ，相較於 lRUCacheFree 要走訪全部，此函式只需要找到一個節點，因此使用雜湊表的指標路線走訪， HHHH 應為 node ，而參考 list_move 的函式定義， IIII 應為 pos

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

此函式用於在 LRU 快取中插入或更新給定 key 和 value 的節點，和前段同理， JJJJ 應為 node ，KKKK 應為 pos

測驗三

__ffs

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

#if BITS_PER_LONG == 64
    if ((word & AAAA) == 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 中最低位1的位置
由於不知道 word 是32位還是64位，所以先用 #if-#endif 判斷如果 word 長度是64，就看後面32位是否都是0，如果是 num 就加32，然後右移32位，因此 AAAA 應該要是二進位的32個1，也就是 0xffffffff 8個 f
後面同理，逐項以二的冪遞減檢查，把0排除，如此就能找到最低位1的位置

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

用來把指定位元變成0
mask 是在指定位元為1，其他為0
透過 p 定位到要操作的 word
最後用 mask 將指定位置歸0，但 mask 是將指定位置標記為1，因此若要用&來操作要先把 mask 反轉，因此 BBBB 應為 ~mask

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

這個函式在 word 中尋找第 n 個被設置為 1 的位元的位置，如果找到了就返回該位置
過程中使用 __ffs 找到最低位1，然後把找到的1用 __clear_bit 歸零，直到找到第 n 個就回傳位置

find_nth_bit

此函式可找出指定的記憶體空間找出第 N 個設定為1的位元

• addr : 指向陣列的指標
• size : 陣列的位元大小
• n :要找的第 N 個被設定的位元
  函式首先判斷如果 n 大於或等於 size，就直接返回 size，因為沒有更多的位元可以搜尋
  接下來判斷如果 size 是一個小型且常數的值（ small_const_nbits(size) 為真），就執行一個快速的位元操作。它從 addr 指向的位元陣列中取出 size 位元，然後使用 GENMASK(size - 1, 0) 將除最低位元外的所有位元設定為 1。最後使用 fns 找到第 N 個被設定為 1 的位元的位置並回傳
  如果 small_const_nbits(size) 不為真則執行 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;                                                     \
    })

前面的迴圈在給定的位元陣列中進行迭代，過程計算 1 的位元的數量，直到找到第 N 個 1 或超過位元陣列的大小，而迴圈的條件 (idx + 1) * BITS_PER_LONG <= sz 保證每次迭代都在有效的位元陣列範圍內，而在迴圈內用 w = hweight_long(tmp) 來找到每次迭代中被設置為 1 的位元數
如果位元陣列的大小 sz 不是 BITS_PER_LONG 的整數倍時，對位元陣列的餘數位元，因此 CCCC 應為 ％
再來用 tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz) 留下餘數位元的部份
最後 sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz) 算出已檢查過都是 0 的 word 數乘以 64 加上最後一個 word 找到 1 的長度，就是答案，而 min 的作用是確保不超過 sz