---
# System prepended metadata

title: 2020q3 Homework8 (quiz8)
tags: [進階電腦系統理論與實作]

---

---
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 上提交並正確的結果。

![](https://i.imgur.com/jNEX3bs.png)



## 測驗 `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))

