2024q1 Homework2 (quiz1+2)

contributed by < LindaTing0106 >

第一週測驗題

測驗 1

此函式目的在於找到串列的尾端，故在 *left 和 (*left)->next 不等於 null 的情況下，
left 應該要等於 &(*left)->next ，也就是 *left 下一個節點的地址。

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

此函式是在計算整個串列的長度，所以 while 中只需要判斷 *left 當下的節點是否為 null ，如有指向節點，則可以持續往下一個節點，並計算長度。
則 left = &(*left)->next。

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

此處 CCCC 填入 p->next ，因為此函式需要去遍歷串列的每個節點，並根據他們大於或是小於 pivot 的值，決定應該插入 right 或是 left 。

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

原本想法是因為 begin 和 end 儲存一段串列的頭與尾，像是前面的

begin[0] = *list;
end[0] = list_tail(list);

所以 DDDD = list_tail(left)， EEEE = list_tail(right)。

後來發現是傳進去的型態問題， node_t *list_tail(node_t **left) 傳入的型態應該為 pointer of pointer of node_t ，故將答案改為 DDDD = list_tail(&left)， EEEE = list_tail(&right)。

begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;

延伸問題：

解釋上述程式碼的運作原理。

上述的快速排序法是使用非遞迴的方式實作。

還沒進入迴圈之前， begin[0] 和 end[0] 分別會指向串列的頭與尾。

先選定 4 作為 pivot ，並且將 pivot 從串列移除，之後開始比較 pivot 與串列各個節點之間的大小，將小於 pivot 的節點 list_add 進 left ，大於 pivot 的節點 list_add 進 right。

排列好大小後，利用 begin[i] 和 end[i] 指標指向串列的頭跟尾。
begin[i] 和 end[i] 指向的是比 pivot 小的串列， begin[i+2] 和 end[i+2] 指向的是比 pivot 大的串列， begin[i+1] 和 end[i+1] 則指向 pivot 。

由於 i += 2; 所以先從上一回合比 pivot 大的串列開始執行上述動作。
將 7 當作 pivot 所以在比大小的時候， 將節點 5list_add 進 left，而right 只能指向 NULL 。

再下一回合 i = 4 時，因為 begin[4] 和 end[4] 都指向 NULL ，所以進到else中，並且 i-- ，來到 i = 3 ，由於 begin[3] 和 end[3] 都指向節點 7，故將 7 list_add 進 result ，且 i-- ， i = 2 時也是相同操作，將 5 list_add 進 result 。重複以上步驟，最終 result 則會為一個遞增串列，以上及為程式碼的運作原理。

提出改進方案並予以實作。

從上述程式碼可以看出他永遠都是選擇第一個節點作為 pivot ，但當最差情況發生時的時間複雜度會來到 O(n²) ，像是 [1, 2, 3, 4, 5] 則每次選到的 pivot 都為最左邊的數字，如此 left 都為 NULL 而 right 為除了 pivot 以外的節點。如此每次選擇 pivot 後，都要遍歷剩下的節點，那麼就可以使用 Median of Medians Algorithm 的方法去規避最差情況發生。

使用 Linux 核心風格的 List API 改寫上述程式碼

程式碼

在程式碼中引入 list.h 函式，並將 node_t 改為串列連接。

+#include "list.h"

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

將程式碼內部用到 node_t 的函式，都改寫為 list_head 的型態。
由於改為 list_head 的型態，故可以將 list_tail 的函式刪除，直接使用 list->prev 的方式表示最尾端的端點，故也將 end 移除。但因為要保存每次分治的串列，故這裡的 begin 需要配置 list_head 的空間。

-    begin[0] = *list;
-    end[0] = list_tail(list);
+    for (int be = 0; be < max_level; be++){
+        begin[be] = list_new();
+    }

+    begin[0] = list;

     while (i >= 0) {
-        node_t *L = begin[i], *R = end[i];
+        struct list_head *L = begin[i]->next, *R = begin[i]->prev;

此外將原本很多單純用 = 賦予值的部分，改為運用 list_splice_init 、 list_move 。

並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

測驗 2

AAAA 填入 &head ，則可以透過指標的指標進行編寫。

struct list_head *head;
struct list_head **tail = AAAA;

當此處的priv不為 NULL ，則會將型態轉為整數的指標，使用*取值後再加 1 。初步認為這裡應是對應到最後算出比較次數的計算。

int compare(void *priv, const struct list_head *a, const struct list_head *b)
{
    if (a == b)
        return 0;

    int res = list_entry(a, element_t, list)->val -
              list_entry(b, element_t, list)->val;

    if (priv)
        *((int *) priv) += 1;

    return res;
}

在比較完兩個節點的大小後，使用 *tail 將較小的節點連接到 head ，而後應該要將 tail 指向此節點的 next ，讓下次比較大小時，較小的節點可以繼續接在 *tail 處，也就是讓尾端的 next 可以放入下一個節點的地址。
故 BBBB 應該填入 &(*tail->next) ， 但因為要填入最精簡的程式碼，故寫成 &a->next 。
而 CCCC 只是換成在如果節點 b 比 a 的值小的情況，所以可以直接填入 &b->next 。

 if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = BBBB;

從此段程式碼來看， list 最終會指向 NULL ，而需要補上 DDDD 和 EEEE 才能使整個串列變成雙向環狀鏈結串列，所以需要將 list 的前一個節點，也就是 tail 的下一個節點變為 head ，並且 head 的上一個節點也應該要為 tail 。故 DDDD 填入 tail->next ，而 EEEE 為 head->prev 。

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

在這段程式碼中我們可以觀察到 stk_size 此變數，一開始是設為 0 ，而在後面找 run 的迴圈裡，此變數也會更著增加，從這裡我們可以判斷 stk_size 是表示著切了幾個 run 的個數，並且在各個合併的函示中， stk_size 的數量也會減少。
而在 build_prev_link(head, head, stk0); 此函式中，我們可以得知是在將最後合併出來，只剩下一個 run 的串列修正為雙向環狀鏈結串列，故 FFFF 填入 1。

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)

延伸問題：

解釋上述程式碼的運作原理。

在上述程式碼內，並無設定 minrun 的部分，假設被傳入 find_run 的 list 。

因為 5 > 4 的關係想辦法讓這段 run 反轉。

最後回傳回主程式遞增的 run ( 稱 run1 ) ，以及另一個還沒被排序過的串列。

tp 會將排序過的 run 的 head 串接在一起，經過剛剛的 find_run ，現在 run 的數量等於 1 ，接著進入 merge_collapse ，但因為 run==1 ，所以直接跳出。
再跑一次迴圈後，剛剛剩下來沒有被排序的串列，經過 find_run 的處理後， result.head 的指針會指向處理好的 run ，在這裡程式是用 result.head->prev 指向 run1 。

之後再次進到 merge_collapse 函式，根據是否滿足上面提到的原則，來決定要不要進行合併。

提出改進方案並予以實作。

明顯可以發現上述程式碼中並沒有包含 minrun 的實作，故應將 minrun 加入程式的實作。 minrun 的大小為，將總資料長度轉為二進位後的前 6 位數字，若 6 位數字後不為 0 ，則加 1。

第二週測驗題

測驗 1

這段重建二元樹的程式碼，是先從 TreeNode *buildTree 開始，首先程式會先創一個空的 hash table ，並且利用 void node_add 將 inorder 的節點放入 hash table 中，其中節點資訊包含了數值和位置。

之後在 TreeNode *dfs 中，會利用指標 *tn 去存取目前在前序中最前面的節點的數值，當作此子樹的頭，以及利用這個數值在 int find 中找尋其在中序裡的位置。

其中 tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size); ，會持續遞迴出左子樹的函式。 pre_low + 1 做為下輪的 int pre_low 是因為第一個已經被當作頭了，所以 pre_low 就往前一格。 pre_low + (idx - in_low) 做為下輪的 int pre_high ，則是利用 idx - in_low 可以算出左子樹有的節點數量，所以用 pre_low + 左子樹有的節點數量，得出後面 pre_low + (idx - in_low) 格的節點都是左子樹的節點。 idx - 1 做為下輪的 int in_high 是因為在中序中，頭左邊的所有節點都是左子樹的節點。

而 tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size); ， pre_high - (in_high - idx - 1) 做為下輪的 int pre_low 是因為 (in_high - idx - 1) 可以得出在前序中右子樹的尾到右子樹的頭中間的節點數量，故用 pre_high 減去，可得右子樹的頭的節點的位置。 idx + 1 做為下輪的 int in_low ，則是因為在中序中頭的右側即全為右子樹節點。

測驗 2

LRU Cache 是將一種快取的實做方式，當有新資料進來時，將快取中最後一次被存取的部分給替代掉。

需要寫一般串列和 hash table 的串列，來去串接節點是因為可以利用 hash table 提升我們在取值時的速度，如果只有一般串列，那我們必須遍歷 count 個節點找尋我們要的節點。而需要一般串列是因為我們這樣才有哪個節點是最後被使用的紀錄。

typedef struct {
    int capacity; // 其LRUCache的大小
    int count; // 目前使用的數量
    struct list_head dhead; // 串接所有的節點
    struct hlist_head hhead[]; // 用 hash table 的方式儲存節點
} LRUCache;

LRUCache *lRUCacheCreate(int capacity) 會根據其容量大小來為其配置記憶體大小。

void lRUCacheFree(LRUCache *obj) 利用傳入的指標，將其指向的快取給刪除，程式裡面用到 list_entry 函式，來取得快取中的串列的物件，再將其各個刪除。應該也可以使用 hlist_del 將 hash table 中串列的節點移除。

int lRUCacheGet(LRUCache *obj, int key) 程式碼中會先遍歷對應的 hash table 中的串列，如果有找到對應的值，則將 dlist 中該節點，搬去串列的最前方，並回傳該值，如果找不到，則回傳 -1 。

void lRUCachePut(LRUCache *obj, int key, int value)
是希望將給定的值放入快取中，首先會利用 key 求出 hash 值，再利用 hash 值來檢查是否此 key 值已經使用過了。

• 如果使用過了，則將此節點移動至串列最前方並且將 value 改為新的值。
• 如果沒有使用過，則比對傳進來的快取是否已經滿了。
  • 如果空間滿了，則將最後一個使用的節點移至串列的最前方，並將其在 hash 中對應的位置刪除，並且再將其放入 hash table 中。
  • 如果空間沒有滿，則新配置一個空間，並將節點加入串列，也加入 hash table 中，並將 count++ 。

這段程式碼相當為將 &cache->node move 至 &obj->hhead[hash] ，既然都有 list_move 了，也可以實作出 hlist_move 。

hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);

測驗 3

find_nth_bit 在指定的記憶體空間找出第 N 個設定的位元。
__ffs(unsigned long word) 是用來找一段 long 中，最高的位元是哪一位，程式碼當中用了多個判斷式。
其中原理為，當 word & 0xf 為 0 則表示在 4 位元內 word 的值都為 0 ，故 word 必大於 \(2^4\) ，以此類推。

if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }

find_nth_bit 的程式碼運作原理為，先比較要找的數字有無超過限制的 size ，並檢查 size 的設置是否符合規範， GENMASK(h, l) 是將 h 到 l 間的位元變為 1 ， 故 val 為 addr h 到 l 間的值，如果 val 有值，則利用 fns 找到為 1 的最高位元並回傳。