2020q3 Homework8 (quiz8)

contributed by < JimmyLiu0530 >

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

測驗一: LeetCode 1494. Parallel Courses II

給定一整數

n

表示某所大學裡課程的數目，編號為

1

到

n

，給定陣列 dependencies，使得

d e p e n d e n c i e s [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。

範例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。

本題的限制:

$1 \leq n \leq 15$
$1 \leq k \leq n$
$0 \leq$
$d e p e n d e n c i e s . l e n g t h$
$\leq \frac{n \times (n - 1)}{2}$
$d e p e n d e n c i e s [i] . l e n g t h = 2$
$1 \leq x_{i}, y_{i} \leq n$
$x_{i} \neq y_{i}$
所有先修關係都不同，也就是說
$d e p e n d e n c i e s [i] \neq d e p e n d e n c i e s [j]$
題目輸入的圖是個有向無環圖

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

以本題來說，

n

至多為

15

，而且一門課「選」或者「不選」即可運用二進位的位元表示，符合上述的狀態壓縮技巧。演算法如下:

計算每個課程的直接相依課程的 bit mask (位元遮罩)，記為 pre
令狀態
$f (S)$ 表示完成位元遮罩
$S$ 的課程所需要的最少學期數
在初始階段，
$f (0) = 0$ ，其餘為位元遮罩有效範圍以外的數值
狀態移轉時，從某個已修過的課程位元遮罩
$S_{0}$ ，嘗試求出
$S_{1}$ ，後者表示目前可選擇的新課程（新課程也該滿足相依條件)，再從
$S_{1}$ 逐次找出小於等於
$k$ 門課程，其位元遮罩記作
$S$ ，移轉關係為
$f (S_{0} \lor S) = m i n (f (S_{0} \lor S), f (S_{0}) + 1)$
最終解為
$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];
}

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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[] 用來儲存修過某些課程所需的最少學期數。舉例來說，

d p [5 = (101)_{2}]

2

，代表最少需要 2 個學期才能修完課程 1 跟 3。 line 19-21 在做 dp[] 的宣告以及初始化，要注意的是初始化的值至少要大於總課程數 n，又

1 \leq n \leq 15

，因此，INIT = 0x5F。

接著，line 31 的 for 迴圈中的 i 代表之前修過的課的二進位表示法，透過窮舉去看所有課程

之前是否已經修過以及
他們的先修課是否已修過

來決定這學期可以修哪些課，並儲存在 b (line 37-40)。因此，COND = !(i & (1 << j))，用來檢查是否已修過此堂課。

NOTE: 前兩個程式碼都將此步驟(i.e. 將修過的課移除) 移到 for 迴圈外面去做

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

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

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

測驗二: Skip List

Linked list (鏈結串列) 允許時間複雜度為

O (1)

的隨機插入 (insert) 及隨機移去 (remove) 節點，但搜尋卻需要

O (n)

時間複雜度。假設一個 linked list 內容如下:

H E A D \to 1 \to 10 \to 18 \to 38 \to 22 \to 39 \to 47 \to 59 \to n e x t

從開頭 (即上方 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 (l o g n)

。

一般的 linked list 搜尋時必須從第一個開始，按照順序一個一個搜尋，因此不論是搜尋或存取的時間複雜度皆為

O (n)

，而 Skip list 可將存取、搜尋、新增和刪除等操作的平均時間複雜度降到

O (l o g n)

Know Thy Complexities!

Skip list 是種針對 sorted linked list 的資料結構，透過不同 level 做出不同的 linked list 達到加速搜尋。
舉例來說，當我們想在上方 Skip List 示意圖中搜尋 7，步驟如下:

從 level 4 (圖中左上方) 比對，因
$1 \leq 7$ 得知 level 4 不存在 7，但其他 level 可能具備。於是跳到 level 3 繼續找
從 level 3 比對，因
$4 \leq 7$ 且
$6 \leq 7$ 得知 level 3 一樣不存在 7，於是跳到 level 2 繼續找
從 level 2 比對，因
$9 \geq 7$ 表示此 level 不存在 7，跳去 level 1
在 level 1 比對，發現 7

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

如之前所及，skip list 是具有分層結構的鏈結串列，那麼每層的節點該如何產生呢？
我們可在新增元素時，使用隨機方法 (稱作 “coin flip”，也就是「擲硬幣看正反面結果」) 決定這個元素有幾層節點。設定該元素僅有 1 層節點機率為

\frac{1}{2}

，且有 2 層節點機率為

\frac{1}{4}

，僅有 3 層節點機率為

\frac{1}{8}

，以此類推。
然後觸發隨機事件，當機率為

\frac{1}{2}

的事件發生時，該元素有 1 層節點; 機率為

\frac{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 的流程:

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

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

Google 的開放原始碼 Key-Value storage (可簡稱 KV) 專案 LevelDB 和 Facebook 延伸 LevelDB 而發展出的 RocksDB，都用到 Skip List 的變形。Redis 內建一個高效率的 Skip List 實作。

延伸閱讀:

下方程式嘗試實作一個 Skip List，並進行以下變更:

將 “coin flip” 改為插入節點前，事先建立
“coin flip” 原本透過機率，現在取代為特定的雜湊 (hash) 函數，此處選用 djb2
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 (h a s h) = h a s h \times 33 + c

為何選擇 33 呢？

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

至於為何選用初始的 5381 呢？這沒有太大影響，其他質數數也可很好地執行。除了 djb2，可考慮其他雜湊函數，如:

針對上述 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，指出考慮到現代處理器架構的 Skip List 實作，有哪些考量和取捨

簡報檔案

參考實作: Cache-Sensitive Skip List (CSSL)

3. 練習 LeetCode 1206. Design Skiplist，除了提交 C 語言的實作並通過自動評分系統，也該提供正確性測試和效能分析

參見 Skip List

2020q3 Homework8 (quiz8)

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

測驗一: LeetCode 1494. Parallel Courses II

程式說明

延伸問題

1. interative-nos2.c 可如何改進？

2. 實作上述不同的程式碼 (限制為 C99/C11 + GNU extensions)，應比較遞迴和非遞迴的形式在效能的落差

3. LeetCode 1595. Minimum Cost to Connect Two Groups of Points

測驗二: Skip List

程式說明

延伸問題

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

2. 研讀 Cache-Sensitive Skip List: Efficient Range Queries on modern CPUs，指出考慮到現代處理器架構的 Skip List 實作，有哪些考量和取捨

3. 練習 LeetCode 1206. Design Skiplist，除了提交 C 語言的實作並通過自動評分系統，也該提供正確性測試和效能分析

Read more

台灣萬萬稅

CS:APP 第一章重點整理 - Introduction

GDB介紹

Ubuntu 20.04 wifi 選項消失之解決方法

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

1. `interative-nos2.c` 可如何改進？