2024q1 Homework2 (quiz1+2)

contributed by < Lccgth >

第一週測驗題

測驗 1

list_add()

將一個新的節點添加到鏈結串列的開頭處。

node_t 為要加入到鏈結串列的節點，而 *list 為指向鏈結串列的開頭的指標。

node_t->next = *list;
*list = node_t;

list_tail()

返回鏈結串列尾部的節點。

從 *left 開始逐一走訪鏈結串列中的節點，直到找到尾部節點就將其回傳。

while ((*left) && (*left)->next)
    left = &((*left)->next);

list_length()

返回鏈結串列的長度。

從 *left 開始逐一走訪鏈結串列中的節點，並同時計算長度，走訪完後回傳，此函式的 **left 需要指向鏈結串列的開頭，否則長度會計算錯誤。

while (*left) {
    ++n;
    left = &((*left)->next);
}

list_construct()

創建一個節點，並將其加到鏈結串列的開頭處。

使用 malloc() 分配記憶體空間，再將新節點的 next 指向鏈結串列的開頭，最後將新節點的 value 設成 n。

node_t *node = malloc(sizeof(node_t));
node->next = list;
node->value = n;

list_free()

逐一釋放鏈結串列的節點所使用到的記憶體空間。

逐一走訪鏈結串列，並同時釋放目前走訪到的節點使用到的記憶體空間。
進行小幅改寫移除迴圈中的 if 判斷式，使程式碼更加簡潔。

- node_t *node = (*list)->next;
+ node_t *node;
  while (*list) {
-     free(*list);
-     *list = node;
-     if (node)
-         node = node->next;
+     node = *list;
+     list = (*list)->next;
+     free(node);
 }

list_is_ordered()

檢查鏈結串列是否已經排序完成。

逐一走訪鏈結串列中的節點，並和目前為止觀察到的最大值 (value) 比較，若當前節點小於 value，回傳 false，若當前節點大於 value，則更新 value 成目前節點的值。

我將一開始的 value 就設定為開頭節點的 value，在迴圈內就不用判斷是否為第一次進入迴圈，但需要先判斷一次 list 是否為 NULL。

- bool first = true;
- int value;
+ if (!list)
+     return true;   
+ int value = list->value;
+ list = list->next;
  while (list) {
-     if (first) {
-         value = list->value;
-         first = false;
-     } else {
-         if (list->value < value)
-             return false;
-         value = list->value;
-      }
+     if (list->value < value)
+         return false;     
+     value = list->value;
      list = list->next;
  }

shuffle()

打亂鏈結串列中的節點順序。

逐一走訪鏈結串列的節點，並隨機選一個後續節點和目前節點交換。
此方法只在 n < RAND_MAX 時有效，因為 rand() 會返回一個 0 到 RAND_MAX 的隨機數，若 n >= RAND_MAX 時會導致無法產生足夠均勻的隨機數。

for (size_t i = 0; i < n - 1; i++) {
    size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
    int t = array[j];
    array[j] = array[i];
    array[i] = t;
}

quick_sort()

使用非遞迴的方式實作快速排序。

每一組 begin[i] 和 end[i] 表示第 i 個鏈結串列，利用 i 選擇目前要處理的串列是哪一個。
迴圈會先判斷目前的 begin[i] 是否和 end[i] 相等，如果相等就直接將此串列加入 result 的開頭。

if (L != R){
// ...
} else {
    if (L)
        list_add(&result, L);
}

接著將目前串列的開頭設為 pivot，並從下一個節點開始逐一走訪，如果走訪到的節點小於 pivot，就將其加入 left，反之則加入 right。

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

然後更新 begin 和 end，將 begin[i] 設為 left，begin[i + 1] 設為 pivot，而 begin[i + 2] 設為 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 中的每條串列都會只有一個節點，並會依序被加入到 result 中，完成排序。

快速排序法圖解

例題

Step 1:
將 4 設為 pivot，逐一走訪串列，將比 pivot 小的節點放到 begin[0]，比 pivot 大的放到 begin[2]，pivot 放在 begin[1]。

Step 2:
將 7 設為 pivot，逐一走訪 begin[2]，將比 pivot 小的節點放到 begin[2]，pivot 放在 begin[3]。

Step 3:
因為 begin[3]、begin[2]、begin[1] 都只有一個節點，所以依序加入到 result 中。

Step 4:
將 2 設為 pivot，逐一走訪 begin[0]，將比 pivot 小的節點放到 begin[0]，比 pivot 大的放到 begin[2]，pivot 放在 begin[1]。

Step 4
因為 begin[3]、begin[2]、begin[1] 都只有一個節點，所以依序加入到 result 中。

測驗 2

Timsort

結合了 Merge sort 和 Insertion sort 的優點，適用於部分已經排序完成的串列，且為一種穩定 (stable) 的排序法。

run_size()

計算並返回一段以排序好的元素 (run) 大小，此大小被儲存在 head->next->prev 中

merge()

合併兩段已排序好的鏈結串列，會依序將目前兩個串列開頭處較小的節點加入到 head 後。

可使用 while 替換 for，並在其中一個串列已走訪完後跳出迴圈，將剩下的串列直接串接在尾部。
新增參數 *last 表示合併完的串列要插入的位置，將 merge_final() 中的功能進行整合，只要將 *last 設定為 NULL 就是原本 merge() 的功能，其他情況則會是 merge_final() 的功能。

  struct list_head *head;
  struct list_head **tail = &head;

- for (;;) {
+ while (a && b)
      if (cmp(priv, a, b) <= 0) {
          *tail = a;
          tail = &a->next;
          a = a->next;
-         if (!a) {
-             *tail = b;
-             break;
-         }
      } else {
          *tail = b;
          tail = &b->next;
          b = b->next;
-         if (!b) {
-             *tail = a;
-             break;
-         }
      }
  }
+ *tail = a ? a : b;
+ if (last) 
+    build_prev_link(last, last->prev, head); 

build_prev_link()

將 tail 和 list 拼接起來，並設定其中節點的 prev，使其成為環狀雙向鏈結串列。

tail->next = list;
do {
    list->prev = tail;
    tail = list;
    list = list->next;
} while (list);

tail->next = head;
head->prev = tail;

merge_final()

將最後兩段 run 進行合併，並使用 build_prev_link() 調整串列，使其成為環狀雙向鏈結串列。

此函式和 merge() 的重複性太高，可以進行重構使程式碼更精簡。

find_run()

找到一段排序好的串列，若為降序排列則反轉其為升序。

merge_at()

在特定位置 at 合併兩個串列，並同時更新 stk_size (run 的數量)。

merge_force_collapse() 和 merge_collapse()

當 run 的數量達到一定條件時就選擇合併一些 run，以提升後續合併時的效率。

timsort()

將一鏈結串列依照 find_run() 分成多段 run，並依照 merge_force_collapse() 和 merge_collapse() 的規則進行適當的合併，最後再使用 build_prev_link() 進行串列的調整以完成排序。

第二週測驗題

測驗 1

INIT_HLIST_HEAD()

藉由將 h->list 設為 NULL 來初始化 hlist。

hlist_add_head()

將一個的新的節點插入到 hlist 的開頭處。

如果 hlist 不為空，就將開頭處節點的 pprev 指向 n->next 的位址，接著依序更新新節點的 next 和 pprev，最後將開頭節點設為 n。

if (h->first)
    h->first->pprev = &n->next;
n->next = h->first;
n->pprev = &h->first;
h->first = n;

find()

在一組 hlist 中尋找 num 的 idx。

先通過計算 hash 得知此數在 heads 中的哪一個串列中，接著逐一走訪此串列的節點來和 num 做比對。

int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) {
    struct order_node *on = list_entry(p, struct order_node, node);
    if (num == on->val)
        return on->idx;
}

dfs()

深度優先搜尋，根據前序和中序建立出二元樹。

因前序中首節點為樹的根節點，再依據中序得知每個節點是在根節點的左子樹還是右子樹中，依序建立出獨一無二的二元樹。

node_add()

將新節點根據雜湊函式加入到 heads 中，這裡的雜湊函式會返回一個 0 到 size - 1 間的整數。

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

buildTree()

先根據中序節點數初始化對應數量的 hlist，接著將這些節點根據雜湊函式加入到對應的 hlist 中，最後使用 dfs() 來建立出二元樹。

測驗 2

hlist_del()

將 hlist 中的節點 n 刪除。

struct hlist_node *next = n->next, **pprev = n->pprev;
*pprev = next;
if (next)
    next->pprev = pprev;

list_add()

將新的節點插入到串列的開頭處。

list_del()

將特定的節點從串列中刪除。

list_move()

利用 list_del() 和 list_add() 將特定節點移到串列的開頭處。

lRUCacheCreate()

創立一個指定大小的快取，並初始化其 dhead 和 hhead。

lRUCacheFree()

逐一走訪串列中的節點，並依序釋放占用的記憶體空間。

list_for_each_safe (pos, n, &obj->dhead) {
    LRUNode *cache = list_entry(pos, LRUNode, link);
    list_del(&cache->link);
    free(cache);
}
free(obj);

lRUCacheGet()

從 LRU 快取中獲取 key 對應的值。

先透過取餘數的方法計算 hash，再逐一走訪對應的串列，當找到對應的值時，將其移到串列的開頭處，表示最近被訪問過。

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

lRUCachePut()

在 LRU 快取中新增或更新 key-value。

此函式和 lRUCacheGet() 有高度相似的程式碼，可將其獨立成一個函式使程式碼更精簡。

+ LRUNode* findLRUNode(LRUCache *obj, int key)
+ {
+     int hash = key % obj->capacity;
+     struct hlist_node *pos;
+     hlist_for_each(pos, &obj->hhead[hash]) {
+         LRUNode *node = list_entry(pos, LRUNode, node);
+         if (node->key == key)
+             return node;
+     }
+     return NULL;
+ }

  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, link);
-         if (cache->key == key) {
-             list_move(&cache->link, &obj->dhead);
-             return cache->value;
-         }
-     }
+     LRUNode *cache = findLRUNode(obj, key);
+     if (cache) {
+         list_move(&cache->link, &obj->dhead); 
+         return cache->value;
+     }
      return -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, link);
-         if (c->key == key) {
-             list_move(&cache->link, &obj->dhead);
-             cache = c;
-         }
-     }
+     LRUNode *cache = findLRUNode(obj, key);
+     if (cache) {
+         list_move(&cache->link, &obj->dhead);
+         cache->value = value;
+     }
      // ...
  }

測驗 3

__ffs()

利用二分搜尋法的方式依序找到 word 第一個值為 1 的位元。

if ((word & 0xffffffff) == 0) {
    num += 32;
    word >>= 32;
}

__clear_bit()

將特定位元的值設為 0。

BITMASK(n) 會返回一個只有第 n 個位元為 1 的數，將其作反轉就能得到只有第 n 個位元為 0 的數。

unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

*p &= ~mask;

fns()

在 word 裡找到第 n 個值為 1 的位元。

find_nth_bit()

在一個記憶體區域中找到第 n 個值為 1 的位元。

FIND_NTH_BIT()

逐一走訪記憶體區域的 unsigned long，使用 hweight_long() 計算每單位中位元值為 1 的數量，從而找到第 n 個值為 1 的位元位置

if (sz & BITS_PER_LONG)                              
    tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);