# 2024q1 Homework2 (quiz1+2)
contributed by < [allenliao666](https://github.com/allenliao666) >
## 2024quiz1
### 測驗1
#### 想法及思考
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
```graphviz
digraph "__node"
{
node [shape="record"];
rankdir = "LR"
subgraph cluster_a
{
label = "node_t";
node1 [label="<head>value|*next|{<left> *left |<right> *right}"];
}
}
```
`node_t` 為佇列中的節點結構，由 `node_t` 指標 *left 、 *right 和 *next 還有 `long` value 所組成。
其中 *next 用於連接下一個 `node_t` , value 為該節點的值。
#### 所需函式
- void list_add(node_t **list, node_t *node_t)
- node_t *list_tail(node_t **left)
- int list_length(node_t **left)
- node_t *list_construct(node_t *list, int n)
- void list_free(node_t **list)
以此串列為例：
```graphviz
digraph "eg"
{
node [shape="record"];
rankdir = "LR"
a[label = 5]
b[label = 3]
c[label = 2]
d[label = 7]
e[label = 8]
a -> b -> c -> d -> e
}
```
在測驗一的快速排序非遞迴實作中，首先 pivot 指向串列第一個節點，並且把該節點的 value 設定為比較對象。並把 L 和 R 指標分別指向待排序串列兩側的節點。
```graphviz
digraph "eg"
{
node [shape="record"];
pivot[label = pivot]
L[label = L]
R[label = R]
rankdir = "LR"
a[label = 5]
b[label = 3]
c[label = 2]
d[label = 7]
e[label = 8]
pivot -> a -> b -> c -> d -> e
L -> a
R-> e
}
```
接著依序和串列中的其他節點比較大小，將 value 小於 piovt 的節點加入 left 指向的串列，反之加入 right 指向的串列。最後使用 begin[] 和 end[] 兩個指標陣列紀錄 left 和 right 指向的兩個串列的開頭和尾端節點，其中 begin[i] 指向 left 的串列的開頭節點，end[i] 指向 left 的串列的尾端節點，begin[i + 2] 指向 right 的串列的開頭節點，end[i + 2] 指向 right 的串列的尾端節點。
```graphviz
digraph "eg"
{
node [shape="record"];
pivot[label = pivot]
rankdir = "LR"
b1[label="begin[0]"]
b2[label="begin[2]"]
e1[label="end[0]"]
e2[label="end[2]"]
a[label = 5]
b[label = 3]
c[label = 2]
d[label = 7]
e[label = 8]
pivot -> a
c -> b
e ->d
b1 -> c
b2 -> e
e1 -> b
e2 -> d
}
```
接著會針對 right 串列中重複執行上述的步驟，持續分割排序串列，並把分割排序後的串列的頭尾紀錄在對應的 begin[] 和 end[] 中，直到待排序的串列只有一個節點後開始合併。
#### 改進空間
- 原程式碼中，先宣告 begin[] 和 end[] 的大小為串列長度的兩倍，然而實際執行時，最多僅會將串列分割為 n 個子串列，故 begin[] 和 end[] 僅須為串列即可。
- end[i] 的功能為記錄子串列的尾端節點，故可用 list_tail(&begin[i]) 取代。
- (實驗待補)據 quick sort 性質，其最差狀況是 pivot 為最小值，導致該次迴圈的比較無意義，最差的時間複雜度為 $O(n^2)$ 。
### 測驗2
#### 想法及思考
Timsort 結合合併排序及插入排序的優點。 Timsort 執行過程如下:
1. 首先使用 `find_run()` 尋找資料中已排序的子序列(以下稱為 run )，以避免浪費時間排序資料中已排序的部分。在尋找 run 的過程中，若遇到反向排序( value 由大到小)的部分時會將其反向排序成為 run 。
2. 將 run 透過 `pair` 結構紀錄，其中 `head` 指向 run 的第一個節點， `next` 指向剩餘串列的第一個節點。
```c
struct pair {
struct list_head *head, *next;
};
```
3. 透過堆疊儲存每一個 run ，以 `tp` ˋ指標指向最新的 run ，並用 `result.head` 的 prev 連接上一個加入堆疊的 run 。
4. 透過 `merge_collapse` 確保堆疊頂端的3個 run 符合長度規則，若不符合則合併相鄰的2個 run ，藉此維持堆疊中 run 長度的平衡。
#### 改進空間
## 2024quiz2
### 測驗1
#### 想法及思考
題意:給定二元樹的前序及中序表示法，藉此重建二元樹。
### 測驗2
#### 想法及思考
### 測驗3
#### 想法及思考
題意:尋找記憶體位置中的第 n 個設定位元。
因為對 bitwise 操作一竅不通，故依序理解巨集。
**GENMASK(h, l)**
```c
#define GENMASK(h, l) \
(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
```
其中`((~0UL) - (1UL << (l)) + 1)` 即把右邊 `l - 1`個位元設為0，`(~0UL >> (BITS_PER_LONG - 1 - (h)))` 把左邊 `h + 1`個位元設為0。其手法類似 linux 中 [bitops.h](https://elixir.bootlin.com/linux/v4.0/source/include/linux/bitops.h) 的程式碼。
```c
#define GENMASK(h, l) \
(((~0UL) << (l)) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
#define GENMASK_ULL(h, l) \
(((~0ULL) << (l)) & (~0ULL >> (BITS_PER_LONG_LONG - 1 - (h))))
```
其目的皆為設定 `l` 到 `h` 位元為1，其餘皆為0。
**BIT_WORD(nr)**
```c
#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
```
換算 nr 個位元的長度為多少個 word。
**#define BITS_TO_LONGS(nr)**
```c
#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(long))
```
使用 `DIV_ROUND_UP(n, d)` 和 `BITS_PER_TYPE(long)` 兩個巨集， `DIV_ROUND_UP` 的目的為將 n / d 的結果向上取至整數，例如42/5=8.4 代入 `DIV_ROUND_UP` 就會得到9。`BITS_PER_TYPE(long)` 則是計算 long 的位元數。故`BITS_TO_LONGS(nr)` 表示至多需要多少個 long 儲存 nr 。
**__const_hweight8(w)**
```c
#__const_hweight8(w) \
((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
(!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
(!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
(!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))
```
計算8個位元中共有多少個位元被設定(即為1)。
**BITMAP_LAST_WORD_MASK(nbits)**
```c
#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))
```
這個巨集會用在當 nbit 不整除於 BITS_PER_LONG 時(即 nbit 非64的倍數)，必須把多餘的部份湊成64位元，所以使用遮罩保護右邊 nbit % BITS_PER_LONG 的值。
**FIND_NTH_BIT(FETCH, size, num)**
這個巨集較複雜，故先從參數開始介紹：
* FETCH : 記憶體位置，並從該位置開始尋找設定的位元
* size(sz) : 尋找的範圍
* num : 尋找的目標
該巨集在 size 範圍內從 FETCH 開始尋找第 num 個設定的位元。 idx 為 word 的索引。
分為以下幾種狀況：
1. idx * BITS_PER_LONG + nr >= sz ： 當 idx * BITS_PER_LONG 長度超過 sz ，表示尋找範圍已經超過 size ，所以 goto out 並回傳 sz 。
2. w > nr ： w 為該 word 中設定的位元數，當 w 大於 nr 表示目標就在這個 word 中，故 goto found 利用 fns 巨集和 word 偏移地址即可得到目標。
```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; \
})
```
Sign in with Wallet
Connect another wallet