2024q1 Homework2 (quiz1+2)

contributed by <pine0113>

第一週測驗題

測驗一 快速排序

解釋運作

宣告 begin[] 與 end[] 作為堆疊，其中 max_level 設定為 2n

node_t *begin[max_level], *end[max_level];

將 list 的開頭放置在 begin[0] ，結尾放置在 end[0]
是第一個需要被完整處理的資料紀錄

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

這個迴圈是用來確認堆疊裡是否還有未處理的資料
當還有資料時，堆疊中的待排序的資料的第i組讀入 L 跟 R

 while (i >= 0) {
     node_t *L = begin[i], *R = end[i];
     ...
    }

    node_t *pivot = L;
    value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

當 L!=R 代表的是讀入的序列 begin[i] 到 end [i] 之間沒排序好
則繼續運作，如果已經排序好，則將 begin[i] 中所存的資料儲存到
result 中，並用 i-- 來表示這個堆疊已經處理好了，可以回到前一層

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

Ｌ從左邊開始掃，逐漸往右移動
從p點開始逐點往右看，
若比 pivot 的值大 則把 p 點紀錄在 right 中
若比 pivot 的值小 則把 p 點紀錄在 left 中

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

把這一組left跟right成對紀錄在 begin[i]、end[i] (即紀錄在堆疊) 中後
清空 left 跟 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);

    left = right = NULL;
    i += 2;

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

• 將 struct __node 置換成 ListAPI

typedef struct {
    struct list_head *list;
    long value;
} node_t;

針對鏈結串列，提出可避免最差狀況的快速排序實作

測驗二 Timsort 填空

解釋運作原理

使用 pair 類別做成的堆疊 result 將 find_run() 找出來的 run 依序放入堆疊中

struct pair {
    struct list_head *head, *next;
};

find_run()

find_run()，傳入連結串列指標 跟 cmp，
傳回一個升序或是降序的 run ，
其中如果是降序的 run 會在製作 run 時同時將這段鏈結串列重新排序

        do {
            len++;
            list->next = prev;
            prev = list;
            list = next;
            next = list->next;
            head = list;
        } while (next && cmp(priv, list, next) > 0);
}

最後 將頭尾整理到 result 後傳回 result

    head->prev = NULL;
    head->next->prev = (struct list_head *) len;
    result.head = head, result.next = next;
    return result;

對每個 run 做 merge_collapse

這段程式碼就是把清單中的每一個 run 讀出
把 run 放在 tp
把 run 移出 list 並堆疊層數 +1
然後對 tp 執行 merge_collapse

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

merge_collapse

檢查堆疊頂端的 3 個 run 是否滿足以下原則：

A 的長度要大於 B 和 C 的長度總和。

n >= 3 時檢查
A 的長度要大於 B 和 C 的長度總和。
*tp->prev->prev
*tp->prev
*tp

B 的長度要大於 C 的長度

n>=4 的時候檢查
A 的長度要大於 B 和 C 的長度總和。
*tp->prev->prev->prev
*tp->prev->prev
*tp->prev

B 的長度要大於 C 的長度

如果不符合的時候用 merge_at 將 BC 合併

static struct list_head *merge_collapse(void *priv,
                                        list_cmp_func_t cmp,
                                        struct list_head *tp)
{
    int n;
    while ((n = stk_size) >= 2) {
        if ((n >= 3 &&
             run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
            (n >= 4 && run_size(tp->prev->prev->prev) <=
                           run_size(tp->prev->prev) + run_size(tp->prev))) {
            if (run_size(tp->prev->prev) < run_size(tp)) {
                tp->prev = merge_at(priv, cmp, tp->prev);
            } else {
                tp = merge_at(priv, cmp, tp);
            }
        } else if (run_size(tp->prev) <= run_size(tp)) {
            tp = merge_at(priv, cmp, tp);
        } else {
            break;
        }
    }

    return tp;
}

merge_at

合併 2 個 run 並讓堆疊數 stk_size -1

merge_force_collapse

當 run 都已經放置到堆疊中後，會再用 merge_force_collapse 強制檢查一次
A 的長度要大於 B 和 C 的長度總和。
B 的長度要大於 C 的長度

static struct list_head *merge_force_collapse(void *priv,
                                              list_cmp_func_t cmp,
                                              struct list_head *tp)
{
    while (stk_size >= 3) {
        if (run_size(tp->prev->prev) < run_size(tp)) {
            tp->prev = merge_at(priv, cmp, tp->prev);
        } else {
            tp = merge_at(priv, cmp, tp);
        }
    }
    return tp;
}

做完 merge 後，把每一個堆疊依序銜接起來

struct list_head *stk0 = tp, *stk1 = stk0->prev;
    while (stk1 && stk1->prev)
        stk0 = stk0->prev, stk1 = stk1->prev;
    if (stk_size <= 1) {
        build_prev_link(head, head, stk0);
        return;
    }

merge final ()

這段對應到的是題目文件上的

當 A 的長度小於 B 時，會先將 A 數列暫存。直觀的合併方法是從 A 和 B 的開頭開始進行逐對比較，將較小的元素放置於 A 的原位置，這一過程一直持續到 A 和 B 完全排序，類似於經典的合併排序類似，也稱為逐對合併(one-pair-at-a-time)。

文件中提到的改進方向 Galloping mode 並沒有在這份程式實作
持續改進：首先尋找 B 的首個元素（即 ）在 A 中的排序位置，從而確定 A 中有一段是小於 者，可將這部分元素放回 A。接著，尋找剩餘 A 的首個元素在 B 中的位置，如此反覆進行，直到完成排序

提出改進方案

實作整合進 lab0-c

第二週測驗題

測驗一

解釋運作

程式以 hash table 來實作二元樹

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

Build Tree

二元樹建立的過程分成以下幾個步驟

1. 用 string size 當作 index，依照 inorder 的順序將節點放置 hash table 中

int hash = (val < 0 ? -val : val) % size;

以範例 9,3,15,20,7 來說，Hash Table 就會變成

hlist_head[0] -> (val=15,idx=2 -> (val=20,idx=3)
hlist_head[1] ->
hlist_head[2] -> (val=7,idx=4)
hlist_head[3] -> (val=3,idx=1)
hlist_head[4] -> (val=9,idx=0)

2. 用遞迴方式 用 preorder 找出 子樹的 root
   preoder 3,9,20,15,7

dfs函式中 用 find(preorder[pre_low], size, in_heads);找出該點在 inorder 的 index，再透過該 index

preorder 以 3 為例, 透過數值 3 可以取得 has_listhead[3] 的第一個節點，idx=1
來區分 左子樹有 9, 右子樹有 15,20,7

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

測試程式找出改進空間

找出 pre-order walk 程式碼並探討

測驗二

解釋運作

一個 LRUCache 物件由 dll 跟 hash table 組成，
另外用兩個 int 紀錄 capacity 跟 count

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

LRUNode

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

LRUCache 透過 HashTable 的方式來存取 LRUNode
hlist_head 的數量就是 capacity

LRUCacheGet 為用 key 去向 LRUCache 要求資料
如果該資料在 LRUCache 的 Hash Table 有資料

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

將 key 跟 value 配對放進 Cache中
如果

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(&c->link, &obj->dhead);
            cache = c;
        }
    }
...

如果 cache 不存在
檢查是否已經到達上限了，如果到達上限則將最沒使用的 cache 移掉並加入新的點
如果還未達上限則直接建立新的 cache 並將技術 +1

 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;

測試程式找出改進空間

找出 LRU 程式碼並探討

測驗三

解釋運作

find_nth_bit

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

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

#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 的應用案例，並予以解說和分析

• 需要涵蓋 CPU affinity 相關的原始程式碼。