2020q3 第 8 週測驗題

tags: `sysprog2020`

目的: 檢驗學員對 dynamic programming, bitwise 操作, linked list 和非連續記憶體操作的認知

測驗 `1`

在講解題目之前，先看經典的 Coin Problem: 給予一組硬幣

{1, 2, 5, 10, 20, 50, 100, 200}

，若金額

n = 520

，如何找出最少的硬幣組成呢？硬幣可重複選取。
最佳解為:

n = 520 = 200 + 200 + 100 + 20

貪婪演算法 (greedy algorithm) 的做法是從最大硬幣開始選取，直到 520 被湊出來，其中

1, 5, 10, 50, 100

僅會在最佳解出現一次。

dynamic programming 的本質是暴力法 (brute force; complete search)，但因它採用表格欄位去紀錄答案 (memorization)，所以每個 subproblem 僅運算一次即可。

簡化問題，給定

coins = {1, 3, 4}

及

solve (10) = 3

，因為至少需要 3 種硬幣才能得到總和 10，於是最佳解為

3 + 3 + 4 = 10

\begin{array}{lcl} solve (0) & = & 0 \\ solve (1) & = & 1 \\ solve (2) & = & 2 \\ solve (3) & = & 1 \\ solve (4) & = & 1 \\ solve (5) & = & 2 \\ solve (6) & = & 2 \\ solve (7) & = & 2 \\ solve (8) & = & 2 \\ solve (9) & = & 3 \\ solve (10) & = & 3 \end{array}

我們可依據條件寫成等式 :

\begin{aligned} solve (x) = min ( & solve (x - 1) + 1, \\ solve (x - 3) + 1, \\ solve (x - 4) + 1) . \end{aligned}

擴展成通式:

solve (x) = {\begin{cases} \infty & x < 0 \\ 0 & x = 0 \\ min_{c \in coins} solve (x - c) + 1 & x > 0 \end{cases}

對應的遞迴求解程式如下: (C++)

int solve(int x) {
    if(x < 0) return INF; // infinity
    if(x == 0) return 0;
    int best = INF;
    
    for (auto c:C)
        best = min(best, solve(x - c) + 1);
    return best;
}

注: 此處的 INF 可用 INT_MAX 實作

上述程式碼會耗費指數時間 (exponential time) 以計算

x

，於是我們可利用

m e m o i z a t i o n

手法，將把子問題 (subproblem) 的解保存下來，避免每次都要重算，如此我們可建構 recursion + memoziation 的程式碼，如下:

int solve(int x) {
    if (x < 0) return INF; 
    if (x == 0) return 0;
    if (ready[x]) return value[x]; /* if slove(x) is ready, stop to compute it. */
    
    int best = INF;
    for (auto c:C)
        best = min(best, solve(x - c) + 1);
    
    /* save subproblem solution of slove(x) */
    value[x] = best;
    ready[x] = true;
    
    return best;
}

可改寫為迴圈形式的程式碼，從而避免遞迴:

bool ready[N] = {0};

int value[N] = {0};
value[0] = 0;

/* caculate slove(x) from 1 to n */
for (int x = 1; x <= n; x++) {
    value[x] = INF;
    for (auto c : coins) {
        /* check index boundary */
        if (x-c >= 0) {
            //       don't take c    take c
            value[x] = min(value[x], value[x - c] + 1);
        }
    }
}

倘若我們想輸出

s o l v e (10) = 4 + 3 + 3

，該如何做？
我們可用一個陣列去記錄每個最佳子問題的第一個硬幣為何，依據貪婪演算法，第一個硬幣也會是最大的硬幣，因此拼湊出來即是最佳解的全部硬幣組合。將 value[x-c]+1 < value[x] 這條件從 min() 搬移到 if 敘述:

int first[N];

value[0] = 0;
for (int x = 1; x <= n; x++) {
    value[x] = INF;
    for (auto c : coins) {
        // value[x-c]+1 < value[x]
        if ((x - c >= 0) && (value[x - c] + 1 < value[x]) {
            value[x] = value[x - c] + 1;
            first[x] = c;
        }
    }
}

隨後我們再將組合印出:

while (n > 0) {
    printf("%d\n", first[n]);
    n -= first[n];
}

接著我們又可擴充題目，計算出 solve(x) 有多少種硬幣組合方式，以 solve(5) 為例，可能的組合如下:

$1 + 1 + 1 + 1 + 1$
$1 + 1 + 3$
$1 + 3 + 1$
$3 + 1 + 1$
$1 + 4$
$4 + 1$

用上述的條件，令

coins = {1, 3, 4}

，則

solve (5) = 6

對應的遞迴表示如下:

\begin{aligned} solve (x) = & solve (x - 1) + \\ solve (x - 3) + \\ solve (x - 4) . \end{aligned}

通式如下，要留意到「不放」也算是其中一種方法:

solve (x) = {\begin{cases} 0 & x < 0 \\ 1 & x = 0 \\ \sum_{c \in coins} solve (x - c) & x > 0 \end{cases}

對應的程式碼如下:

/* There is only one way to form an empty sum */
count[0] = 1;

int solve(x) {
    for (int x = 1; x <= n ; x++)
        for (auto c : Coins)
            if (x - c >= 0) count[x] += count[x - c];
}

若我們不想算出全部 solve(x) 的解，可運用模數運算 (modulo) 來化簡。舉例來說，令

m = 10^{9} + 7

，在 count[x] += count[x - c] 敘述增加模數運算，如:

count[x] += count[x - c];
count[x] %= m;

參考資訊:

Why we like Modulo
$10^{9} + 7$ (1000000007)

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
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 →

給定輸入:

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

預期輸出: 3

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

範例 2
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 →

給定輸入:

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]$
題目輸入的圖是個有向無環圖 (Directed acyclic graph)

注意本題是 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));
    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];
}

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

我們可改寫為非遞迴的形式。先計算出每個數在二進位表示中有幾個 1，亦即選修幾門課，保存於陣列 count[] 中，共有

2^{n}

種狀態。陣列 pre[] 表示特定的狀態所需要的前導課程。對應的程式碼如下: (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];
}

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

我們可改良上述的非遞迴的實作，如下: (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];
}

:angel: interative-nos2.c 在 LeetCode 提交後的執行結果
Runtime: 44 ms
Memory Usage: 6.1 MB
:warning: 作答時請務必考慮到相對的效能表現

請考慮到程式碼的正確和效率表現，補完程式碼。

INIT = ?

(a) 0x5F
(b) 0
(c) 1
(c) 2
(d) 4
(e) 8

COND = ?

(a) 1
(b) !(i & (1 << j))
(c) (i | (1 << j)
(d) (i & (1 << j)
(e) (i ^ (1 << j)

參考資訊:

LeetCode 1494. Parallel Courses II 解說和答題錄影

延伸問題:

解釋上述程式碼運作原理，為何 interative-nos2.c 會比 interative-nos1.c 有更短的執行時間呢？interative-nos2.c 可如何改進？
嘗試實作不同上述的程式碼 (限制為 C99/C11 + GNU extensions)，應比較遞迴和非遞迴的形式在效能的落差
分析上述 (包含你的改作練習) 程式碼的時間和空間複雜度
練習 LeetCode 1595. Minimum Cost to Connect Two Groups of Points

測驗 `2`

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" 一詞在英語的意思很多，這裡取韋伯字典提出的解釋: "to bound off one point after another"

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

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

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

換個視角，呈現如下:

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

Skip List 示意圖

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

O (\log n)

。

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

O (N)

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

O (\log N)

Know Thy Complexities!

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

從 level 4 (圖中左上方) 比對，因 1 <= 7 得知 level 4 不存在 7，但其他 level 可能具備。於是跳到 level 3 繼續找
從 level 3 比對，因 4 <= 7 且 6 <= 7 得知 level 3 一樣不存在 7，於是跳到 level 2 繼續找
從 level 2 比對，因 9 >= 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}{2}

的事件發生時，該元素有 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.h 程式碼，使測試程式執行符合預期。我們假設所有記憶體配置都可成功。

作答區

HHH = ?

(a) h = d->height
(b) h = (d->height)++
(c) h = (d->height)--
(d) h = ++(d->height)
(e) h = --(d->height)

III = ?

(a) iterator = iterator->next[0]; callback(iterator)
(b) callback(iterator); iterator = iterator->next[0]
(c) if (callback) callback(iterator)

延伸問題:

解釋上述程式碼運作原理，探討用 hash 替換 Skip List 裡頭 random 的效益和潛在的議題，並實作 delete 操作
研讀 Cache-Sensitive Skip List: Efficient Range Queries on modern CPUs，指出考慮到現代處理器架構的 Skip List 實作，有哪些考量和取捨
- 簡報檔案
- 參考實作: Cache-Sensitive Skip List (CSSL)
練習 LeetCode 1206. Design Skiplist，除了提交 C 語言的實作並通過自動評分系統，也該提供正確性測試和效能分析
- 參見 Skip List

2020q3 第 8 週測驗題

tags: sysprog2020

測驗 1

測驗 2

Read more

2025 年 Linux 核心設計課程期末專題

2024 年 Linux 核心設計/實作課程期末專題

2025 年春季「Linux 核心設計」第 6 週測驗題

Linux 核心設計: Timer 及其管理機制

tags: `sysprog2020`

測驗 `1`

測驗 `2`