# 2020q3 Homework8 (quiz8)
contributed by < `JimmyLiu0530` >

###### tags: `進階電腦系統理論與實作`

## 測驗一: LeetCode [1494. Parallel Courses II](https://leetcode.com/problems/parallel-courses-ii/)

給定一整數 $n$ 表示某所大學裡課程的數目，編號為 $1$ 到 $n$，給定陣列 `dependencies`，使得 $dependencies[i]=[x_i,y_i]$ 表示先修課的關係，亦即課程 $x_i$ 必須在課程 $y_i$ 之前選修並通過。
另外，給予一整數 $k$，表示在一個學期裡頭，最多可同時選修 $k$ 門課，前提是這些課的先修課在之前的學期裡已修過。程式應該回傳上完所有課最少需要多少個學期。題目保證一定存在一種修完所有課的方式。

- [ ] 範例1

給定輸入:
- n = 4 (即 4 門課程)
- dependencies = $[[2,1],[3,1],[1,4]]$
- 即選修 `1` 這門課，應當先修過 `2` 和 `3` 這二門課，又，選修 `4` 之前應當先修過 `1` 這門課
- k = 2 (一個學期中，至多可同時選修 2 門課程)

預期輸出: 3
- 下圖展現可能的修課方式: 第一個學期選修課程 `2` 和課程 `3`，然後第二個學期選修課程 `1` ，第三個學期選修課程 `4`。

digraph{
    rankdir=LR
    
    2->1->4
    3->1
}

- [ ] 範例2
給定輸入:
- n = 5 (即 5 門課程)
- dependencies = $[[2,1],[3,1],[4,1],[1,5]]$
- 即選修 `1` 這門課，應當先修過 `2`,`3` 和 `4` 這三門課，又，選修 `5` 之前應當先修過 `1` 這門課
- k = 2 (一個學期中，至多可同時選修 2 門課程)

預期輸出: 4
- 上圖展現可能的修課方式: 第一學期選修課程 `2` 和 `3` (注意一學期僅能同時選修 `2` 門課程)，第二學期選修課程 `4`，第三學期選修課程 `1`，第四學期選修課程 `5`。

digraph{
    rankdir=LR
    
    2->1->5
    3->1
    4->1
}

本題的限制:
- $1\leq n\leq 15$
- $1\leq k\leq n$
- $0\leq$ $dependencies.length$ $\leq\dfrac{n×(n-1)}{2}$
- $dependencies[i].length=2$
- $1\leq x_i, y_i\leq n$
- $x_i \neq y_i$
- 所有先修關係都不同，也就是說 $dependencies[i] \neq dependencies[j]$
- 題目輸入的圖是個有向無環圖

注意本題是 [NP 問題](https://en.wikipedia.org/wiki/NP_(complexity))，運用貪婪演算法 (greedy algorithm) 很容易遇到 TLE (time limit exceeded)，於是我們可嘗試狀態壓縮和 [dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming) 結合的技巧。狀態壓縮是利用二進位來表達中間的狀態，也就是說，狀態只能是 0 或 1，若用集合來思考，就是「在」或「不在」集合中。此手法適用於資料量不大的案例。先用陣列儲存之前的狀態，再由狀態及其對應的數值，推導出狀態轉移方程式，最終可得適當的解法。

以本題來說，$n$ 至多為 $15$，而且一門課「選」或者「不選」即可運用二進位的位元表示，符合上述的狀態壓縮技巧。演算法如下:
1. 計算每個課程的直接相依課程的 bit mask (位元遮罩)，記為 `pre`
2. 令狀態 $f(S)$ 表示完成位元遮罩 $S$ 的課程所需要的最少學期數
3. 在初始階段，$f(0)=0$，其餘為位元遮罩有效範圍以外的數值
4. 狀態移轉時，從某個已修過的課程位元遮罩 $S_0$，嘗試求出 $S_1$，後者表示目前可選擇的新課程（新課程也該滿足相依條件)，再從 $S_1$ 逐次找出小於等於 $k$ 門課程，其位元遮罩記作 $S$，移轉關係為 $f(S_0 ∨ S)=min(f(S_0 ∨ S),f(S_0)+1)$
5. 最終解為 $f((1<<n)-1)$

對應的遞迴程式碼如下: (`recursive-nos1.c`)

#include <string.h>                                                                                                                                           
#include <limits.h>

#define min(a, b) (((a) < (b)) ? (a) : (b))
static void solve(int i, int s, int k, int n, int s0, int s1, int *dp)
{
    if ((k == 0) || (i == n)) {
        dp[s0 | s] = min(dp[s0 | s], dp[s0] + 1);
        return;
    }

    solve(i + 1, s, k, n, s0, s1, dp);

    if ((s1 >> i) & 1)
        solve(i + 1, s | 1 << i, k - 1, n, s0, s1, dp);
}

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));
    /* pre[i]: \\the bit representation of all dependencies of course i */
    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;

    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];
}

:::info
:angel:`recursive-nos1.c` 在 LeetCode 提交後的執行結果
Runtime: 124 ms
Memory Usage: 6.2 MB
:::

我們可改寫為非遞迴的形式。對應的程式碼如下: (`iterative-nos1.c`)

#define min(a, b) (((a) < (b)) ? (a) : (b))

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];
}

:::info
:angel:`iterative-nos1.c` 在 LeetCode 提交後的執行結果
Runtime: 80 ms
Memory Usage: 6.1 MB
:::

我們可改良上述的非遞迴的實作，先計算出每個數在二進位表示中有幾個 `1`，亦即選修幾門課，保存於陣列 `count[]` 中，共有 $2^n$ 種狀態。如下: (`iterative-nos2.c`)

#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];
}

:::info
:angel:`iterative-nos2.c` 在 LeetCode 提交後的執行結果
Runtime: 44 ms
Memory Usage: 6.1 MB
:::

### 程式說明
這三個程式碼其實都環繞在同一個想法上，只是使用不同的方法實作而已，譬如說利用遞迴或迭代。所以下面的說明一概以`iterative-nos2.c` 為例，至於上面那兩個程式碼，請自行參考對照。

首先，將 `dependencies[]` 內的資料移植到 `pre[]` 中 (line 13-14)，其中 `pre[i]` 代表要修課程 `i+1` 之前要先修的課程的位元表示法 ( 即 pre[2] = 3 = $(011)_2$ 代表要修課程 3 之前要先修過課程 1 跟 2 )。

`dp[]` 用來儲存修過某些課程所需的最少學期數。舉例來說，$dp[5=(101)_2]$ = $2$，代表最少需要 **2** 個學期才能修完課程 1 跟 3。 line 19-21 在做 `dp[]` 的宣告以及初始化，要注意的是初始化的值至少要大於總課程數 `n`，又 $1 \leq n \leq 15$，因此，`INIT = 0x5F`。

接著，line 31 的 `for` 迴圈中的 `i` 代表之前修過的課的二進位表示法，透過窮舉去看所有課程
1. 之前是否已經修過 以及
2. 他們的先修課是否已修過

來決定這學期可以修哪些課，並儲存在 `b` (line 37-40)。因此，`COND = !(i & (1 << j))`，用來檢查是否已修過此堂課。
> NOTE: 前兩個程式碼都將此步驟(i.e. 將修過的課移除) 移到 for 迴圈外面去做

最後，列舉所有這學期可以修的課的排列組合，去看總堂數有沒有超過 `k` 堂，若小於等於 `k`，則更新對應的 `dp[]` with
`dp[之前修過 | 這學期修的] = min(dp[之前修過 | 這學期修的], dp[之前修過] + 1)`；
若超過 `k` 堂，則從中選取 `k` 堂，一樣更新 `dp[]`。

:::info
:Notes: 為何 `interative-nos2.c` 會比 `interative-nos1.c` 有更短的執行時間呢？

1. 主要是因為在最後檢查所有這學期可以修的課的排列組合時，`interative-nos2.c` 檢查的比 `interative-nos1.c` 來的精簡。舉例來說對於可以修的課堂數小於等於 `k` 的情況，前者只會更新 "全取" 的情況；而後者卻會更新所有可能性，造成不必要的更新。這是因為當這學期可以修的課堂數小於等於 `k`，那一定是全選會使得所需的總學期數最小。再者，對於這學期可以修的課堂數大於 `k`，前者也只會更新那些加起來課程數為 `k` 的組合而已。

2. 用預先算好的 `count[]` 取代 `__builtin_popcount()`。
:::

### 延伸問題
#### 1. `interative-nos2.c` 可如何改進？
- 可以將 `pre[]` 的大小從 `cap` 下降至 `n` 即可

#### 2. 實作上述不同的程式碼 (限制為 C99/C11 + GNU extensions)，應比較遞迴和非遞迴的形式在效能的落差
#### 3. LeetCode [1595. Minimum Cost to Connect Two Groups of Points](https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/)
----------------------------------------
## 測驗二: [Skip List](https://en.wikipedia.org/wiki/Skip_list)
Linked list (鏈結串列) 允許時間複雜度為 $O(1)$ 的隨機插入 (insert) 及隨機移去 (remove) 節點，但搜尋卻需要 $O(n)$ 時間複雜度。假設一個 linked list 內容如下:

$HEAD→1→10→18→38→22→39→47→59→next$

從開頭 (即上方 `HEAD`) 找起，`59` 這個節點需要存取或比對 7 次才能找到，你直覺可能想到二分法，但對於 linked list 來說，隨機存取節點的時間複雜度仍是 $O(n)$，也就是說，二分法無法帶來效益。

我們可在鏈結串列中，增加額外的 “skip” (作用是提供資料存取的捷徑) 節點，如下：

如此一來，我們就可依據 “skip” 節點查詢，只需要比對 3 次即可找到上述的 `59`。
至於若想搜尋 `47`，我們先根據 “skip” 節點來比對，於是在節點 `22` 上，它的 “skip” 指標會指向 `59`，後者大於 `47`，因此我們可知 `47` 可能會存在於節點 `22` 和節點 `59` 之間，這時候再根據鏈結串列順序搜尋，一共要比對 5 次。

隨著節點的增多，我們的 “skip” 鏈結串列會變成這樣：

“skip” 節點的密度約為普通節點的一半，能否再提高密度呢？我們可在這基礎上再加一層新的 “skip” 節點，這層節點的密度為第一層 “skip” 節點的一半。

換個視角，呈現如下:

我們再給予新的限制：每層的 “skip” 節點都由它下一層的 “skip” 節點中產生，最終我們可得類似下圖的 “Skip List”:

於是，我們不再區分每層是原節點還是 “skip” 節點，而將最底下的那層節點通稱為第一層 (level 1) 節點，第一層節點上面為第二層 (level 2) 節點，再來是第三層，以此類推。假設每層的節點數為下一層的一半，於是搜尋的時間複雜度縮減為 $O(log\ n)$。

一般的 linked list 搜尋時必須從第一個開始，按照順序一個一個搜尋，因此不論是搜尋或存取的時間複雜度皆為 $O(n)$，而 Skip list 可將存取、搜尋、新增和刪除等操作的平均時間複雜度降到 $O(log\ n)$
> [Know Thy Complexities!](https://www.bigocheatsheet.com/)

Skip list 是種針對 sorted linked list 的資料結構，透過不同 level 做出不同的 linked list 達到加速搜尋。
舉例來說，當我們想在上方 Skip List 示意圖中搜尋 7，步驟如下:
1. 從 level 4 (圖中左上方) 比對，因 $1 \leq 7$ 得知 level 4 不存在 `7`，但其他 level 可能具備。於是跳到 level 3 繼續找
2. 從 level 3 比對，因 $4 \leq 7$ 且 $6 \leq 7$ 得知 level 3 一樣不存在 `7`，於是跳到 level 2 繼續找
3. 從 level 2 比對，因 $9 \geq 7$ 表示此 level 不存在 `7`，跳去 level 1
4. 在 level 1 比對，發現 `7`

總共比對為 5 次，比直接循序查詢（需要 7 次存取) 還快。

如之前所及，skip list 是具有分層結構的鏈結串列，那麼每層的節點該如何產生呢？
我們可在新增元素時，使用隨機方法 (稱作 “coin flip”，也就是「擲硬幣看正反面結果」) 決定這個元素有幾層節點。設定該元素僅有 1 層節點機率為 $\dfrac{1}{2}$，且有 2 層節點機率為 $\dfrac{1}{4}$，僅有 3 層節點機率為 $\dfrac{1}{8}$，以此類推。
然後觸發隨機事件，當機率為 $\dfrac{1}{2}$的事件發生時，該元素有 1 層節點; 機率為 $\dfrac{1}{4}$的事件發生時，該元素有 2 層節點，以此類推。另外，我們限定一個 “skip” 表格應當具有最大的層數限制。

假設一個 “skip” 表格最大層數限制為4，於是我們可設定一個整數區間為 $[1,2^{4-1}]$，即 $[1,8]$。然後取一個介於 1 到 8 之間的隨機數，當落在 $[5,8]$ 區間時有 1 層節點，落在 $[3,4]$ 區間時有 2 層節點，落在 $[2,2]$ 區間時有 3 層，落在 $[1,1]$ 上時有 4 層。

總結 Skip List 的特徵:
- 第一層包含所有的元素
- 每一層都是個有序的 linked list
- skip list 是隨機產生，所以即使元素完全相同的 linked list ，最終的生成的 skip list 有可能不一樣
- 如果節點 x 出現在第 i 層，則所有比 i 小的層都包含 x

建立 skip list 的流程:
1. 最底層 (level 1) 是包含所有元素的 linked list
2. 保留第一個和最後一個元素，從其他元素中隨機選出一些元素形成新的一層 linked list
3. 為剛選出的每個元素新增指標，指向下一層和自己相等的元素
4. 重複上述 (2) 和 (3) 步驟，直到不再能選擇出除了第一個和最後一個元素以外的元素

下方動畫展示如何在 Skip List 新增節點:

Google 的開放原始碼 Key-Value storage (可簡稱 KV) 專案 [LevelDB](https://github.com/google/leveldb) 和 Facebook 延伸 LevelDB 而發展出的 [RocksDB](https://rocksdb.org/)，都用到 Skip List 的變形。[Redis](https://redis.io/) 內建一個高效率的 Skip List 實作。

延伸閱讀:
- [Skip 視覺化呈現](https://people.ok.ubc.ca/ylucet/DS/SkipList.html)
- [Skip List](https://www.jianshu.com/p/9d8296562806)

下方程式嘗試實作一個 Skip List，並進行以下變更:
- 將 “coin flip” 改為插入節點前，事先建立
- “coin flip” 原本透過機率，現在取代為特定的雜湊 (hash) 函數，此處選用 [djb2](http://www.cse.yorku.ca/~oz/hash.html)
- Skip List 的高度原本是隨機結果，但透過雜湊函數，得到一個相依於資料分布的實作

此實作以 C99 的前置處理器開發，如下 (`list.h`):

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define LIST_MAX_HEIGHT 32

typedef unsigned long custom_t; /* specify user-defined type */

typedef struct __list_node {
    uint8_t *key;
    size_t key_len;
    uint8_t height;
    custom_t val;
    struct __list_node *next[1];
} list_node_t;

typedef struct {
    uint8_t height;
    uint32_t bits, reset;
    list_node_t *head;
} skiplist;

#define LIST_ALLOC(e, s)               \
    do {                               \
        e = malloc(s);                 \
        assert(e && "out of memory."); \
        memset(e, 0, s);               \
    } while (0)

#define LIST_HEIGHT(d, str, l, z)                                  \
    do {                                                           \
        bool flip = false;                                         \
        for (z = 0; !flip; z++) {                                  \
            if (!d->reset) {                                       \
                d->bits = 5381; /* djb2 hash */                    \
                for (size_t i = 0; i < l; i++)                     \
                    d->bits = ((d->bits << 5) + d->bits) + str[i]; \
                d->reset = LIST_MAX_HEIGHT;                        \
            }                                                      \
            flip = (bool) d->bits & 1;                             \
            d->bits >>= 1;                                         \
            --(d->reset);                                          \
        }                                                          \
    } while (0)

#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)

#define LIST_GET(d, k, l, v) LIST_FIND(d, k, l, v, NULL)

#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)

#define LIST_NODE_INIT(n, k, l, v, h)                                        \
    do {                                                                     \
        LIST_ALLOC(                                                          \
            n, (sizeof(list_node_t) + ((sizeof(list_node_t *)) * (h - 1)))); \
        LIST_ALLOC(n->key, l + 1);                                           \
        memcpy(n->key, k, l);                                                \
        n->val = (custom_t) v, n->height = h, n->key_len = l;                \
    } while (0)

#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)

#define LIST_ITERATE(d, callback)         \
    do {                                  \
        assert(callback);                 \
        list_node_t *iterator = d->head;  \
        while (iterator->next[0]) {       \
            III;                          \
        }                                 \
    } while (0)

#endif

其中 djb2 的作用是產生隨機分佈的的雜湊函數，常見的形式為:

$f(hash)=hash×33+c$

為何選擇 `33` 呢？

1. 乘法易於位移或相加
2. 從位移和加法實作中可見，使用 `33` 可複製雜湊累加器中的大多數輸入位元，並將這些位元相對地分散開來
3. $32=2^5$，32 與位移 5 位元相關，有助於將每個字串的每個位元都用到最終的雜湊數值中

至於為何選用初始的 `5381` 呢？這沒有太大影響，其他質數數也可很好地執行。除了 djb2，可考慮其他雜湊函數，如:
- [MurmurHash](https://en.wikipedia.org/wiki/MurmurHash)
- [xxHash](https://github.com/Cyan4973/xxHash)

針對上述 `list.h` 撰寫的測試程式如下:

#include <stdio.h>
#include "list.h"

static void print_key(list_node_t *n) {
    puts((const char *) n->key);
}

int main()
{
    /* initialize the list */
    skiplist *d;
    LIST_INIT(d);

    /* create a key */
    char *key = malloc(6);
    strncpy(key, "hello", 5);
    key[5] = 0;

    /* create a value */
    char *val = malloc(6);
    strncpy(val, "world", 5);
    val[5] = 0;

    /* insert into the list */
    int l = 5;
    LIST_INSERT(d, key, l, (custom_t) val);

    /* iterate through the list and print */
    LIST_ITERATE(d, print_key);

    /* retrieve from a list */
    custom_t v;
    LIST_GET(d, key, l, v);
    printf("Hello, %s!\n", (char *) v);

    return 0;
}

參考執行輸出:

hello
Hello, world!

請補齊程式碼。

### 程式說明
- LIST_INIT(d)
- 配置一個 `skiplist` 大小的空間給 `d`。
- 配置一個 `list_node_t` 加上 `LIST_MAX_HEIGHT` 個指向 `list_node_t` 指標所需的空間給 `d->head`。
- `d->height` 初始為 0。

- LIST_FIND(d, k, l, v, u)
- 參數說明:
- d: 指向 skiplist 的指標
- k: 鍵值 key
- l: key 的長度
- v: 尋找後的結果。
- u: 指標陣列，紀錄每層中比 `k` 小的最後一個元素，i.e. 待會 `k` 要插入在這個後面
- 從最上層往下找是否已存在鍵值 `k` ，順便更新 `u`。 若有找到鍵值 `k` 相對應的 value，則將之存入 `v`；否則將 0 存入 `v`。

- LIST_HEIGHT(d, k, l, h)
- 利用 `djb2` hash function 去決定 `k` 有多少層節點。

- LIST_NODE_INIT(n, k, l, v, h)
- 建立一個指向新的 `list_node_t` 的指標 `n`，配置空間，並初始化一些變數。

- LIST_INSERT(d, k, l, v)
- 建立一個指標陣列 `u` (與上面提到的 `u` 相同)。
- 呼叫 `LIST_FIND()` 看看鍵值 `k` 是否存在於 skiplist `d` 中。
- 如果存在，則直接結束此次插入。
- 呼叫 `LIST_HEIGHT()` 決定 `k` 有多少層節點。
- 如果決定出來 `k` 的層數 大於 目前 skiplist 擁有的層數，則將 skiplist 向上擴充一層，所以 `HHH 為 h = ++(d->height)` 。此外，還要更新剛擴充這層的 `u`，好讓 `k` 在剛擴充這層找到插入點。
- 呼叫 `LIST_NODE_INIT()` 建立並初始化一個 `list_node_t` 的物件。
- 最後，根據指標陣列 `u` 從最上層往下將含有鍵值 `k` 的物件插入到正確的位置。

- LIST_ITERATE(d, callback)
- 因為各層 `i` 節點的鏈結串列是存在放 `d->head->next[i]` 所指的空間中，因此 `III 為 iterator = iterator->next[0]; callback(iterator)`。

### 延伸問題
#### 1. 探討用 hash 替換 Skip List 裡頭 random 的效益和潛在的議題，並實作 delete 操作

#### 2. 研讀 [Cache-Sensitive Skip List: Efficient Range Queries on modern CPUs](https://www2.informatik.hu-berlin.de/~sprengsz/papers/cssl.pdf)，指出考慮到現代處理器架構的 Skip List 實作，有哪些考量和取捨
> - [簡報檔案](http://www.adms-conf.org/2016/cssl-imdm.pdf)
> - 參考實作: [Cache-Sensitive Skip List (CSSL)](https://github.com/flippingbits/cssl)

#### 3. 練習 LeetCode [1206. Design Skiplist](https://leetcode.com/problems/design-skiplist/)，除了提交 C 語言的實作並通過自動評分系統，也該提供正確性測試和效能分析
> - 參見 [Skip List](https://github.com/yfernandezgou/skip-list-c)