owned this note
owned this note
Published
Linked with GitHub
# 2024q1 Homework2 (quiz1+2)
contributed by < `w96086123` >
## [第一週測驗](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗一
#### 了解資料結構
``` C
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
`left` 代表比 value 小的集合。
`right` 代表比 value 大的集合。
`next` 表示此 node 的下一個 node 。
`value` 表示此 node 的數值。
#### 了解操作函數
##### list_add
將一個 node_t 加入至 list 的 head 。
##### list_tail
尋找此 node_t 中 left 的最後一個 node_t ，並且回傳該指標。
其中的 `AAAA` 為 (*left)->next。
##### list_length
尋找此 node_t 中 left 的長度。
其中的 `BBBB` 為 (*left)->next。
##### list_construct
建立一個 value 為 n 的 node_t ，並且將 node_t 加入至 list 的頭，且回傳該指標。
##### list_free
將 list 中的已配置記憶體的全部釋放。
##### list_is_ordered
檢查此 list 是否已完成排序。
##### shuffle
將 array 中的資料已亂數交換的方式打亂。
##### quick_sort
此方法利用堆疊取代原本的遞迴呼叫。
1. 將 DDDD 和 EEEE 完成，與了解 max_level 的數值定義
```c
// Area 1
begin[i] = left;
end[i] = DDDD;
// Area 2
begin[i + 1] = pivot;
end[i + 1] = pivot;
// Area 3
begin[i + 2] = right;
end[i + 2] = EEEE;
```
此區主要作為切割並且儲存的區域，因此我將此區分成三個區域了解。
```
區域一：
紀錄比 pivot 還要小的數值，因此範圍要為 left 至 list_tail(&left)。
因此 `DDDD` 為 list_tail(&left) 。
區域二：
紀錄 pivot 的位置，因此範圍要為 pivot 至 pivot 。
由於該位置已經進行分類確定好位置，因此 begin 和 end 為相同，在最後進行放置時，就可以判斷為可以放置的狀態了。
區域三：
紀錄比 pivot 還要大的數值，因此範圍要為 right 至 list_tail(&right)。
因此 `EEEE` 為 list_tail(&right) 。
```
藉由上面解析，可以知道每次的切割會新增兩個區塊，因此最大堆疊的空間需要 2 * n 。
2. 完成 CCCC
```C
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
```
此區將 list 中進行分類。
逐一利用 `list_add` 進行分類，分類條件為 `n->value > value` ，若為真，則表示較大，將 n 分類為 right，否則，將 n 分類為 left 。
因此 `CCCC` 為 p->next 。
3. 將 1 與 2 一起觀看
原本的狀態
```graphviz
digraph G
{
rankdir=LR
node [shape=box];
NULL [shape=plaintext];
pivot [shape=plaintext, fontcolor=red];
L [shape=plaintext, fontcolor=green];
R [shape=plaintext, fontcolor=green];
4 -> 1;
1 -> 3;
3 -> 5;
5 -> 2;
2 -> 7;
7 -> NULL;
{
rank="same"
pivot -> 4;
L -> 4;
}
{
rank="same"
R -> 7;
}
}
```
進行分類過後的狀態
```graphviz
digraph G{
rankdir = LR;
node [shape=box];
NULL1[label="NULL", shape=plaintext]
NULL2[label="NULL", shape=plaintext]
NULL3[label="NULL", shape=plaintext]
Left [shape=plaintext, fontcolor=red];
Right [shape=plaintext, fontcolor=red];
pivot [shape=plaintext, fontcolor=red];
Left -> 1 -> 3 -> 2 -> NULL1;
pivot -> 4 -> NULL2;
Right -> 5 -> 7 -> NULL3;
}
```
4. 觀看整體
由於先進行 right 的切割，因此第一次將 L 儲存為 result 的一定為最大值，第二次則為第二大值，依序下來，直到堆疊的索引小於 0 ，結果必為完成排序。
#### main
建立一個長度為 100000 的 array ，順序則為 1 至 100000，並且利用 `shuffle` 進行打亂，後建立打亂後順序的 list ，並進行 `quick_sort` 排序，排序後利用 `list_is_ordered` 進行排序結果的判斷，最後利用 `list_free` 將記憶體釋放，並且釋放該 array 。
#### 延伸問題 1
因為每次的切割都需要使用兩次 `list_tail` ，但每次使用都需要 O(N) ，如果改成使用雙向鏈結串列的方式實做，時間複雜度將降低為 O(1) 。
##### 修改資料結構
``` C
typedef struct __node
{
struct __node *left, *right;
struct __node *prev, *next;
long value;
} node_t;
```
新增 `prev` 節點。
##### 修改操作函數
###### list_add
``` c
if (*list != NULL)
(*list)->prev = node_t;
node_t->next = *list;
node_t->prev = NULL;
*list = node_t;
```
###### list_tail
``` c
node_t *list_tail(node_t **left)
{
if (*left){
return (*left)->prev;
}else{
return *left;
}
}
```
藉由新的結構，可以直接訪問最後的節點，無須逐步訪問，因此時間複雜度可變為 O(1) 。
###### list_construct
``` c
node_t *list_construct(node_t *list, int n)
{
node_t *node = malloc(sizeof(node_t));
node->next = list;
node->prev = NULL;
node->value = n;
if (list != NULL)
list->prev = node;
return node;
}
```
由於修改為新的結構，因此在建立的過程中也需要做相對應的修改。
##### 比較（10000 個節點）
| | 單向鏈結 | 雙向鏈結 |
| -------- | -------- | -------- |
| 處理時間 (s) | 0.049148 | 0.036808 |
由上表可知，這樣得修改方式是有提昇處理時間。
#### 延伸問題 2
若想要避免最壞狀況，可以使用 Median of Three 的方式取得 pivot ，這樣可以避免一直取得最大或是最小值。
### 測驗二
#### Timsort 步驟
1. 先尋找 run
由左到右尋找非嚴格遞增或遞減的序列，每個 run 的長度盡量符合 minrun 跟 2 的冪。
2. 內部 run 進行插入排序法
3. 利用合併排序的方式進行合併
#### 程式碼解讀
##### find_run
## [第二週測驗](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
#### 原版
利用深度優先搜尋的方式建立樹。
##### AAAA
``` c
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;
}
```
此函數主要作用為將 n 插入至 h 的頭。
因此 `AAAA` 為 h->first 。
##### BBBB 和 CCCC
``` 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;
}
```
此函數為尋找特定值。
`BBBB` 這裡要遍歷 hlist_node ，因此 `BBBB` 為 &heads 。
每次的遍歷都需要將當前指針轉換為 order_node，因此 `CCCC` 為 list_entry 。
##### DDDD
``` c
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 ，並且將此 node 放入置 hlist_head。
因此 `DDDD` 為 heads 。
##### dfs
``` c
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;
}
```
利用深度優先搜尋法的方式建立 Tree。
先利用 `find` 尋找出 `preoder[pre_low]` 在 inorder 中的索引值，此索引值稱為 `idx` 。
切割方式：
左子樹：
preorder ： pre_low + 1 至 pre_low + (idx - in_low) 。
(idx - in_low) 表示有多少個節點。
inorder : in_low 至 idx - 1 。
右子樹：
preorder ： pre_high - (in_high - idx - 1) 至 pre_high 。
(in_high - idx - 1) 表示有多少個節點。
inorder : idx + 1 至 in_high 。
循環利用上面的方式，就可以將有 preorder 與 inorder 的序列，轉換為 Tree 了。
### 測驗二
#### 了解資料架構
##### LRUCache
``` c
typedef struct {
int capacity;
int count;
struct list_head dhead;
struct hlist_head hhead[];
} LRUCache;
```
`capacity` 用於儲存 LRU 緩存的容量。
`count` 用於紀錄當前 LRU 緩存中儲存的數量。
`dhead` 用於紀錄 LRU 中節點的訪問順序，用於尋找替換順序。
`hhead` 用於紀錄 LRU 中節點的哈希表連結。
##### LRUNode
``` c
typedef struct {
int key;
int value;
struct hlist_node node;
struct list_head link;
} LRUNode;
```
`key` 節點的鍵值。
`value` 節點的值。
`node` 與其他節點的指標。
`link` 用於與 LRU 的連結。
### 測驗三
Sign in with Wallet
