# 2024q1 Homework2 (quiz1+2)
contributed by <`pine0113`>
## 第一週測驗題
### 測驗一 快速排序
#### 解釋運作
```graphviz
digraph foo {
rankdir=LR;
node [shape=record];
a [label="{ <data> 4 | <ref> }", width=1.2]
b [label="{ <data> 1 | <ref> }"];
c [label="{ <data> 3 | <ref> }"];
d [label="{ <data> 5 | <ref> }"];
e [label="{ <data> 7 | <ref> }"];
f [label="{ <data> 2| <ref> }"];
g [label="{ null }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> e [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
e:ref:c -> f [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
f:ref:c -> g [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
宣告 `begin[]` 與 `end[]` 作為堆疊，其中 max_level 設定為 `2n`
``` c
node_t *begin[max_level], *end[max_level];
```
將 list 的開頭放置在 begin[0] ，結尾放置在 end[0]
是第一個需要被完整處理的資料紀錄
``` c
begin[0] = *list;
end[0] = list_tail(list);
```
這個迴圈是用來確認堆疊裡是否還有未處理的資料
當還有資料時，堆疊中的待排序的資料的第i組讀入 L 跟 R
``` c
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
...
}
```
``` c
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--` 來表示這個堆疊已經處理好了，可以回到前一層
``` c
if (L != R) {
...
else {
if (L)
list_add(&result, L);
i--;
}
```
Ｌ從左邊開始掃，逐漸往右移動
從p點開始逐點往右看，
若比 pivot 的值大 則把 p 點紀錄在 right 中
若比 pivot 的值小 則把 p 點紀錄在 left 中
``` c
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 準備紀錄下一對
``` c
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
```c
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 時同時將這段鏈結串列重新排序
```c
do {
len++;
list->next = prev;
prev = list;
list = next;
next = list->next;
head = list;
} while (next && cmp(priv, list, next) > 0);
}
```
最後 將頭尾整理到 result 後傳回 result
``` c
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
``` c
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 合併
``` c
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 的長度
``` 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 後，把每一個堆疊依序銜接起來
``` c
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 來實作二元樹
``` c
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
```c
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
```c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
LRUNode
```c
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 有資料
```c
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中
如果
```c
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
```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;
```
#### 測試程式找出改進空間
#### 找出 LRU 程式碼並探討
### 測驗三
#### 解釋運作
find_nth_bit
```c
if (small_const_nbits(size)) {
unsigned long val = *addr & GENMASK(size - 1, 0);
return val ? fns(val, n) : size;
}
```
```c
#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 相關的原始程式碼。
Sign in with Wallet
Connect another wallet