---
tags: 進階電腦系統理論與實作
---
# 2020q3 Homework8 (quiz8)
contributed by < `RinHizakura` >
> [第 8 週測驗題](https://hackmd.io/@sysprog/2020-quiz8)
> [GitHub](https://github.com/RinHizakura/NCKU-System-Software-Quiz/tree/master/quiz8)
## 測驗 `1`
### 程式原理
解說遞迴版本的程式思維。
```cpp
int minNumberOfSemesters(int n,
int **dependencies,
int dependenciesSize,
int *dependenciesColSize,
int k)
{
const size_t cap = 1 << n;
int pre[cap];
memset(pre, 0, sizeof(pre));
for (int i = 0; i < dependenciesSize; i++)
pre[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1);
int dp[cap];
for (int i = 1; i < cap; i++)
dp[i] = INT_MAX;
dp[0] = 0;
```
* 初始化 `pre` 是根據課號 `dependencies[i][1]` 需要先修完課號 `dependencies[i][1]` 去設定 bitmask(-1 是因為課號會從 1 開始，但我們從第 0 bit 開始設定 bitmask)
* 初始化 `dp`
```cpp
for (int s0 = 0; s0 < cap; s0++) {
if (dp[s0] == INT_MAX)
continue;
int s1 = 0;
for (int i = 0; i < n; i++)
if (!((s0 >> i) & 1) && ((pre[i] & s0) == pre[i]))
s1 |= 1 << i;
solve(0, 0, k, n, s0, s1, dp);
}
return dp[cap - 1];
}
```
* 對照題目說明，`s0` 是一個 bitmask，表示當前可以選修的課程，數字的第 n 個 bit 為 0 表示考慮選修第 n 堂課
* `dp[n]` 表示要同時修過 n 中 bit 為 1 課程數需要多少學期
* 先思考 `s0 = 0` 的時候，所有的 bit 都為 0，這表示所有的課程都是可以考慮的，而事實上可以選得課無疑是那些不需要前置要求的
* 因此，內層的迴圈會調整 `s1` ，根據每堂課的前置是否已經修完(`(pre[i] & s0) == pre[i])`)，以及 `s0` 限制考慮的課程(`!((s0 >> i) & 1)`)決定目前可以被選擇的課程
* 則對照 `solve()` 的實作， `if ((k == 0) || (i == n))` 是遞迴到已經選了足夠數量的課、或者考慮每一堂課的可選與否後，更新 `dp`
* `solve(i + 1, s, k, n, s0, s1, dp);` 表示判斷第 i + 1 堂課是否可選
* `if ((s1 >> i) & 1) solve(i + 1, s | 1 << i, k - 1, n, s0, s1, dp);` 表示判斷若第 i 堂課可選，且此時 k > 0，因此再找找還有沒有其他可選
* 下一個遞迴時，`s0 = 1` 等於是課號 1 已經修完，因此 1 以外都能選，如此遍歷所有狀態的解後，則 `dp[cap - 1]` 也就是所有課號的表示 bits 皆為 1 時的數值，就是我們所求
改寫為非遞迴版本的程式則如下。
```cpp=
int minNumberOfSemesters(int n,
int **dependencies,
int dependenciesSize,
int *dependenciesColSize,
int k)
{
uint16_t prerequisite[n];
memset(prerequisite, 0, sizeof(prerequisite));
for (int i = 0; i < dependenciesSize; ++i)
prerequisite[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1);
const int cap = 1 << n;
uint8_t dp[cap];
memset(dp, 1 << 6, cap);
dp[0] = 0;
for (uint32_t i = 0; i < cap; ++i) {
uint32_t ready_for_take = 0;
for (uint32_t j = 0; j < n; ++j) {
if ((prerequisite[j] & i) == prerequisite[j])
ready_for_take |= 1 << j;
}
ready_for_take &= ~i;
for (uint32_t j = ready_for_take; j; j = ready_for_take & (j - 1)) {
if (__builtin_popcount(j) <= k)
dp[i | j] = min(dp[i | j], dp[i] + 1);
}
}
return dp[cap - 1];
}
```
* 15 行前面的操作與遞迴版本大致相同
* 17 行的 for 迴圈中， `ready_for_take` 根據 `i` (對應遞迴版本的 `s0`) 以及 `ready_for_take &= ~i` 操作，調整成可以選的課為 1 的 mask
* 則 25 行的 for 迴圈會遍歷 `ready_for_take` 的所有可能子集合
* 所謂子集合是指維持 `ready_for_take` 為 0 的 bit，而為 1 的 bit 可以為 0 或 1 的所有排列組合，這是因為對於 `dp` 的更新只要考慮從可以選的課中選出其中幾堂是否可行即可
* 因此 `__builtin_popcount(j)` 等於是判斷當前的選擇 `j` 1 數量，對應選課數量，是否符合學期只能選 k 堂的規定
最後，來看一個優化的版本。
```cpp=
#define min(a, b) (((a) < (b)) ? (a) : (b))
int minNumberOfSemesters(int n,
int **dependencies,
int dependenciesSize,
int *dependenciesColSize,
int k)
{
const size_t cap = 1 << n;
/* pre[i]: the bit representation of all dependencies of course i */
uint16_t pre[cap];
memset(pre, 0, sizeof(pre));
for (int i = 0; i < dependenciesSize; i++)
pre[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1);
/* i is the bit representation of a combination of courses.
* dp[i] is the minimum days to complete all the courses.
*/
uint8_t dp[cap];
memset(dp, INIT, sizeof(dp));
dp[0] = 0;
uint8_t count[cap];
memset(count, 0, sizeof(count));
for (uint32_t i = 0; i < cap; i++) {
for (uint32_t j = 0; j < n; j++)
if (i & (1 << j))
count[i]++;
}
for (uint32_t i = 0; i < cap; i++) {
uint32_t b = 0;
/* figure out "b", the bit representation of the all courses
* that we can study now. Since we have i and pre[j], we know
* course j can be studied if i contains all its prerequisites.
*/
for (uint32_t j = 0; j < n; j++) {
if (COND && (pre[j] & i) == pre[j])
b |= 1 << j;
}
if (count[b] <= k) {
dp[i | b] = min(dp[i | b], dp[i] + 1);
} else {
for (uint32_t j = b; j; j = (j - 1) & b) {
if (count[j] == k)
dp[i | j] = min(dp[i | j], dp[i] + 1);
}
}
}
return dp[cap - 1];
}
```
* 因為 n 堂課在有解的情況下最多就修 n 個學期，而題目中說 n <= 15，所以只要把 `dp` 中的值(`dp[0]` 以外)初始化成大於 15 的任意數即可。因此 `INIT = (a) 0x5F`
* `count` 預先計算每個 bitmask 的 popcnt
* 所以 25 行的迴圈其實還可以透過以下的調整優化
```cpp
for (uint32_t i = 0; i < cap; i++) {
count[i] = __builtin_popcount(i);
}
```
* 31 行的 for 迴圈對應前兩個版本更新 `dp` 的外層迴圈
* 則 37 行依據前面的邏輯，可以知道 `b` 的作用就是可以選擇的課程對應 bit 為 1 的 mask，因此 `COND = !(i & (1 << j))`
* 41 行的判斷可以看到，如果當前的 mask `b` 1 數量沒有超過可選課的上限，其實並不需要再透過迴圈去檢查其子集合
* 想像 n = 15 、 k = 15 、 bitmask 有 15 個 1 的情況下，如果用上一個程式的邏輯，迴圈會執行 $2^{15}$ 個 iteration，但透過這個額外判斷式僅需要一行程式
### [1595. Minimum Cost to Connect Two Groups of Points](https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/)
先不思考極致的實作效率，嘗試寫出可以正確算出結果的程式碼。
解題的思路是：對於兩群的點，如果要滿足題中的 connected 條件，則對於每個點，勢必都會最少選中自己最小 cost 的 edge。因此，我們可以想成先針對 group 2，選出其中每個點的最小 edge。如此一來，我們可以先保證 group 2 中所有的點都已經有連到 group 1 中的某個點。接下來，就可以利用 dynamic programming 決定 group 1 中的點如何挑選 edge 了。
```c=
#define min(a, b) (((a) < (b)) ? (a) : (b))
int connectTwoGroups(int **cost, int costSize, int *costColSize)
{
// size of first group
const int size1 = costSize;
// size of second group
const int size2 = costColSize[0];
// size of mask
const int mask_size = (1 << size2) - 1;
int min_table[size2];
// init dp table with all zero
unsigned int dp[size1 + 1][mask_size + 1];
// for the first round, pick up all min edge for each node in group 2
for (int j = 0; j < size2; j++) {
int min = 200;
for (int i = 0; i < size1; i++) {
if (cost[i][j] < min) {
min = cost[i][j];
}
}
min_table[j] = min;
}
// then update dp table:
// count cost for each mask for choosing jth node
// which the jth bit of mask is set to 1
memset(dp[0], 0, sizeof(int) * (mask_size + 1));
for (int m = 0; m <= mask_size; m++) {
for (int j = 0; j < size2; j++) {
if (m & (1 << j))
dp[0][m] += min_table[j];
}
}
// now, we already find the edge which let all the node of group2 connect to
// group1 for the next step, we should check the node in group1 now
// for dp[i][m], it means the min cost when node from 1 to i in group 1
// connect with node in group2 of the mask's jth bit of mask is set to 1
for (int i = 1; i <= size1; i++) {
for (int m = 0; m <= mask_size; m++) {
dp[i][m] = INT_MAX;
for (int j = 0; j < size2; j++) {
// if j is already the min edge of node in group2, the min cost
// should consider the combination without node j in group add
// this edge
if (m & (1 << j)) {
dp[i][m] = min(dp[i][m],
cost[i - 1][j] + dp[i - 1][m & ~(1 << j)]);
}
// or we just consider add this edge directly
else {
dp[i][m] = min(dp[i][m], cost[i - 1][j] + dp[i - 1][m]);
}
}
}
}
return dp[size1][mask_size];
}
```
* 第 16 行中，計算 group2 每個點 `j` 的最小 edge，放進 `min_table`
* 18 行的 `int min = 200;` 是因為題中限制最大 cost 為 100，隨便設個比 100 大的數字即可
* `dp[i][m]` 所代表的是對於 group1 的第 1 到第 i 個點，與 bitmask `m` 中位元為 1 的所有 group2 點形成 connected 的最小 cost
* 則透過 `min_table` 首先更新 `dp[0][m]`，其函義為不考慮挑選 group1 哪些點的情況下，根據 bitmask `m` 選擇的點形成 connected 的最小 cost
* 因此 33 行的 `if (m & (1 << j))` 在判斷該 mask 第 j 個 bit (從 0 開始算) 是否為 1，得知該 mask 對應的點有哪些
* 43 行的迴圈中
* 如果已知從 group1 的第 1 到第 i - 1 個點與 mitbask `m` 中 bit 為 1 對應的 group2 中的所有點形成 connected 的最小值
* 思考加入 group1 中第 i 個點要形成 connected，表示要找到 group2 的一個點 j 形成連線:
* 如果在第 1 到第 i - 1 個點時，已經和第 j 個點形成 connected，則把第 j 個點上的 edge 拆掉，替換成第 i 個點連到第 j 個點，選擇這個 j 是否會有更小的 cost？
* 如果在第 1 到第 i - 1 個點時，尚未和第 j 個點形成 connected，則把第 i 個點連接到第 j 個點上，選擇這個 j 是否有更小的 cost？
* 把前面的兩個狀態寫成程式就是迴圈中的 if else 敘述
* 特別注意到對於 group1 中的點 i 是從 1 開始數，對於 group2 的點 j 則是從 0 開始數，只是為了撰寫程式方便
如下，為在 leetcode 上提交並正確的結果。
## 測驗 `2`
### 程式原理
逐行來看幾個關鍵 macro 的作用。
#### `LIST_INIT`
```cpp
#define LIST_INIT(d) \
do { \
LIST_ALLOC(d, sizeof(skiplist)); \
LIST_ALLOC(d->head, (sizeof(list_node_t) + ((sizeof(list_node_t *)) * \
(LIST_MAX_HEIGHT - 1)))); \
d->height = 0; \
} while (0)
```
* 初始化 skiplist 的結構 `d`
* 第一個 `LIST_ALLOC` 分配出 `d` 本身需要的空間
* 第二個 `LIST_ALLOC` 分配出 `d` 底下的 `*head`，注意到 `((sizeof(list_node_t *)) * (LIST_MAX_HEIGHT - 1))` 表示 `*head` 底下有 `(LIST_MAX_HEIGHT - 1)` 個不同高度的 `list_node_t`
#### `LIST_INSERT`
```cpp
#define LIST_INSERT(d, k, l, v) \
do { \
custom_t vl; \
list_node_t *u[LIST_MAX_HEIGHT]; \
LIST_FIND(d, k, l, vl, u); \
if (vl) \
break; \
int h; \
LIST_HEIGHT(d, k, l, h); \
if (h > d->height) { \
HHH; \
u[h - 1] = d->head; \
} \
list_node_t *n; \
LIST_NODE_INIT(n, k, l, v, h); \
while (--h >= 0) { \
n->next[h] = u[h]->next[h]; \
u[h]->next[h] = n; \
} \
} while (0)
```
* 插入 key 為 `k`，key 的長度為 `l` 的數值 `v`
* 則首先透過 `LIST_FIND` 走訪 `d`，如果 `vl != 0` 表示該 key 已經存在，不能再 insert 相同的 key
* 否則透過 `LIST_HEIGHT` 計算出這個節點的 level 該為多少
* 如果 `h > d->height` 表示預設定的 height 已經超過目前的最大 height，則此時節點 level 是最大的 height + 1 即可，因此 `HHH = (d) h = ++(d->height)` (調整最大高度後，再用該高度初始化新節點)
* 否則就利用此高度產生對應空間的節點
* 此前的 `u` 紀錄著新節點對應每個 level 的 parent，因此對每個 level 去做插入即可
#### `LIST_FIND`
```cpp
#define LIST_FIND(d, k, l, v, u) \
do { \
list_node_t *iterator = d->head, **ud = u; \
for (int i = d->height - 1; i >= 0; --i) { \
while (iterator->next[i] && \
memcmp(k, iterator->next[i]->key, l) > 0) \
iterator = iterator->next[i]; \
if (ud) \
ud[i] = iterator; \
} \
list_node_t *n = iterator->next[0]; \
v = (n && l == n->key_len && !memcmp(k, n->key, l)) ? n->val : 0; \
} while (0)
```
* `iterator` 從 `d->head` 開始搜尋
* 從最高的 level (`d->height`) 開始，檢查走訪到的節點是否為 null，且比較該節點的 key 是否大於要找的 key
* 如果是，則往同一層的下一個節點繼續走訪
* 如果 `u` 非 NULL，則把這層走到的最後一個節點放進 ud 中
* 遞迴走訪直到最後一層
* 則判斷最後一個走訪的節點是否存在、且 key 長度等於要搜尋的 key 長度、內容也相同
* 如果是，把 `v` 設成該 key 對應之 value
* 否則把 `v` 設為 0
#### `LIST_ITERATE`
```cpp
#define LIST_ITERATE(d, callback) \
do { \
assert(callback); \
list_node_t *iterator = d->head; \
while (iterator->next[0]) { \
III; \
} \
} while (0)
```
* iterate 的部份就很單純，因為遞迴 level 0 就可以走訪所有節點，而透過 `callback` 去操作每個節點，因此 `III = iterator = iterator->next[0]; callback(iterator)`
### [1206. Design Skiplist](https://leetcode.com/problems/design-skiplist/)
這題要求設計 skiplist 一系列的 function，我們可以根據原測驗題的思維，調整至符合題目的要求。
```cpp
#define MAX_HEIGHT 8
typedef struct __list_node {
uint8_t height;
int val;
int ref;
struct __list_node *next[1];
} list_node_t;
typedef struct {
uint8_t height;
list_node_t *head;
} Skiplist;
Skiplist* skiplistCreate() {
Skiplist *l = malloc(sizeof(Skiplist));
l->height = 0;
int s = sizeof(list_node_t) + ((sizeof(list_node_t *)) * (MAX_HEIGHT));
list_node_t *n = malloc(s);
memset(n, 0, s);
n->val = -1;
l->head = n;
return l;
}
int _skiplistSearch(Skiplist* obj, int target, list_node_t **u){
list_node_t *iterator = obj->head, **ud = u;
for (int i = obj->height - 1; i >= 0; --i) {
while (iterator->next[i] && iterator->next[i]->val < target)
iterator = iterator->next[i];
if (ud)
ud[i] = iterator;
}
list_node_t *n = iterator->next[0];
if(!n)
return -1;
if(n->val == target){
return target;
}
return -1;
}
bool skiplistSearch(Skiplist* obj, int target) {
if (_skiplistSearch(obj, target, NULL) >= 0)
return true;
return false;
}
void skiplistAdd(Skiplist* obj, int num) {
list_node_t *u[MAX_HEIGHT];
int search = _skiplistSearch(obj, num, u);
if (search != -1){
u[0]->next[0]->ref++;
return;
}
// random height
int h = random() % (MAX_HEIGHT) + 1;
if(h > obj->height){
h = ++(obj->height);
u[h - 1] = obj->head;
}
list_node_t *n;
n = malloc(sizeof(list_node_t) + ((sizeof(list_node_t *)) * h));
n->height = h;
n->val = num;
n->ref = 1;
while (--h >= 0) {
n->next[h] = u[h]->next[h];
u[h]->next[h] = n;
}
}
bool skiplistErase(Skiplist* obj, int num) {
list_node_t *u[MAX_HEIGHT];
int search = _skiplistSearch(obj, num, u);
if (search == -1)
return false;
list_node_t *tmp = u[0]->next[0];
if(tmp->ref > 1){
tmp->ref--;
return true;
}
for (int i = obj->height - 1; i >= 0; --i) {
if(u[i]->next[i] == tmp){
u[i]->next[i] = u[i]->next[i]->next[i];
}
}
free(tmp);
return true;
}
void skiplistFree(Skiplist* obj) {
list_node_t *iterator = obj->head;
if(iterator->next[0])
iterator = iterator->next[0];
else
goto FREE;
while (iterator) {
list_node_t *tmp = iterator->next[0];
free(iterator);
iterator = tmp;
}
FREE:
free(obj->head);
free(obj);
}
```
* `skiplistCreate` 建立所需要的空間，包含 skiplist 本身以及其 head node
* `_skiplistSearch` 類似原題目的 find 設計，會搜尋 target 並且把 target 節點在每一個 level 的 parent 記錄起來
* 搜尋失敗回傳的是 -1，是因為節點的值有可能是 0，需區分開來
* 則 `skiplistSearch` 會透過 `_skiplistSearch` 進行搜尋，根據題意，找到回傳 true，否則回傳 false
* `skiplistAdd` 的結構則類似原測驗題，這裡就不多解釋
* 值得注意的是額外的 `ref` 欄位操作，這是因為題目中允許插入相同值的節點
* 我們當然也可以重新建立一個節點並找尋合適的位置插入，但可能對於空間與時間都不是很好的選擇
* 因此，對於重複值的插入，這裡的方法是僅將 reference count 加一，而不產生額外節點
* `skiplistErase` 只是把 `skiplistAdd` 的行為反過來思考，找出節點該在的位置，並判斷是否確實存在
* 如果存在，但 reference count >= 2，表示這次的 erase 不必刪除節點，因為還有其他的
* 否則就刪除，方法是將刪除目標在每一個 level 的 parent 和 child 接在一起，然後釋放刪除目標的節點
為了比較 Skiplist 的效益，我把之前 [quiz1](https://hackmd.io/@RinHizakura/BysgszHNw) 的內容稍做改寫，並加入測試的機制，先確認無論是 Skiplist 或是改寫的一般 linked-list 的行為符合預期後，進一步測試兩者的效率。(詳細程式請參考 [RinHizakura/Skiplist](https://github.com/RinHizakura/Skiplist))
Sign in with Wallet
Connect another wallet