# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 8 週測驗題
###### tags: `sysprog2020`
:::info
目的: 檢驗學員對 [dynamic programming](https://en.wikipedia.org/wiki/Dynamic_programming), [bitwise 操作](https://hackmd.io/@sysprog/c-bitwise), [linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list) 的認知
:::
==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSdlE1HdhJZDyO-rDwcA7GbzS5aN1yoACrObEaEpGT7sBZ3piA/viewform)==
### 測驗 `1`
在講解題目之前，先看經典的 [Coin Problem](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Dynamic_programming) 的本質是暴力法 (brute force; complete search)，但因它採用表格欄位去紀錄答案 (memorization)，所以每個 subproblem 僅運算一次即可。
簡化問題，給定 $\texttt{coins} = \{1,3,4\}$ 及 $\texttt{solve}(10)=3$，因為至少需要 3 種硬幣才能得到總和 `10`，於是最佳解為 $3 + 3 + 4 = 10$.
\begin{array}{lcl}
\texttt{solve}(0) & = & 0 \\
\texttt{solve}(1) & = & 1 \\
\texttt{solve}(2) & = & 2 \\
\texttt{solve}(3) & = & 1 \\
\texttt{solve}(4) & = & 1 \\
\texttt{solve}(5) & = & 2 \\
\texttt{solve}(6) & = & 2 \\
\texttt{solve}(7) & = & 2 \\
\texttt{solve}(8) & = & 2 \\
\texttt{solve}(9) & = & 3 \\
\texttt{solve}(10) & = & 3 \\
\end{array}
我們可依據條件寫成等式 :
\begin{equation*}
\begin{split}
\texttt{solve}(x) = \min( & \texttt{solve}(x-1)+1, \\
& \texttt{solve}(x-3)+1, \\
& \texttt{solve}(x-4)+1).
\end{split}
\end{equation*}
擴展成通式:
\begin{equation*}
\texttt{solve}(x) = \begin{cases}
\infty & x < 0\\
0 & x = 0\\
\min_{c \in \texttt{coins}} \texttt{solve}(x-c)+1 & x > 0 \\
\end{cases}
\end{equation*}
對應的遞迴求解程式如下: (`C++`)
```cpp
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$，於是我們可利用 $memoization$ 手法，將把子問題 (subproblem) 的解保存下來，避免每次都要重算，如此我們可建構 recursion + memoziation 的程式碼，如下:
```cpp
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;
}
```
可改寫為迴圈形式的程式碼，從而避免遞迴:
```cpp
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);
}
}
}
```
倘若我們想輸出 $solve(10) = 4+3+3$，該如何做？
我們可用一個陣列去記錄每個最佳子問題的第一個硬幣為何，依據貪婪演算法，第一個硬幣也會是最大的硬幣，因此拼湊出來即是最佳解的全部硬幣組合。將 `value[x-c]+1 < value[x]` 這條件從 `min()` 搬移到 `if` 敘述:
```cpp
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;
}
}
}
```
隨後我們再將組合印出:
```cpp
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$
用上述的條件，令 $\texttt{coins}=\{1,3,4\}$，則 $\texttt{solve}(5)=6$ 對應的遞迴表示如下:
\begin{equation*}
\begin{split}
\texttt{solve}(x) = & \texttt{solve}(x-1) + \\
& \texttt{solve}(x-3) + \\
& \texttt{solve}(x-4) .
\end{split}
\end{equation*}
通式如下，要留意到「不放」也算是其中一種方法:
\begin{equation*}
\texttt{solve}(x) = \begin{cases}
0 & x < 0\\
1 & x = 0\\
\sum_{c \in \texttt{coins}} \texttt{solve}(x-c) & x > 0 \\
\end{cases}
\end{equation*}
對應的程式碼如下:
```cpp
/* 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]` 敘述增加模數運算，如:
```cpp
count[x] += count[x - c];
count[x] %= m;
```
參考資訊:
* [Why we like Modulo $10^9 + 7$ (`1000000007`)](https://www.geeksforgeeks.org/modulo-1097-1000000007/)
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`。
- [ ] 範例 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 dependencies.length \leq \frac{n \times (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]$
* 題目輸入的圖是個有向無環圖 ([Directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph))
注意本題是 [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 \lor S) = min(f(S_0 \lor S), f(S_0) + 1)$。
5. 最終解為 $f((1 \ll n)−1)$
對應的遞迴程式碼如下: (`recursive-nos1.c`)
```cpp
#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];
}
```
:::info
:angel: `recursive-nos1.c` 在 LeetCode 提交後的執行結果
Runtime: 124 ms
Memory Usage: 6.2 MB
:::
我們可改寫為非遞迴的形式。先計算出每個數在二進位表示中有幾個 `1`，亦即選修幾門課，保存於陣列 `count[]` 中，共有 $2^n$ 種狀態。陣列 `pre[]` 表示特定的狀態所需要的前導課程。對應的程式碼如下: (`iterative-nos1.c`)
```cpp
#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: `interative-nos1.c` 在 LeetCode 提交後的執行結果
Runtime: 80 ms
Memory Usage: 6.1 MB
:::
我們可改良上述的非遞迴的實作，如下: (`iterative-nos2.c`)
```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];
}
```
:::info
: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 解說和答題錄影](https://youtu.be/p0wmkvWY_uE)
:::success
延伸問題:
1. 解釋上述程式碼運作原理，為何 `interative-nos2.c` 會比 `interative-nos1.c` 有更短的執行時間呢？`interative-nos2.c` 可如何改進？
2. 嘗試實作不同上述的程式碼 (限制為 C99/C11 + GNU extensions)，應比較遞迴和非遞迴的形式在效能的落差
3. 分析上述 (包含你的改作練習) 程式碼的時間和空間複雜度
4. 練習 LeetCode [1595. Minimum Cost to Connect Two Groups of Points](https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/)
:::
---
### 測驗 `2`
Linked list (鏈結串列) 允許時間複雜度為 $O(1)$ 的隨機插入 (insert) 及隨機移去 (remove) 節點，但搜尋卻需要 $O(n)$ 時間複雜度。假設一個 linked list 內容如下:
$$
HEAD \to 1 \to 10 \to 18 \to 38 \to 22 \to 39 \to 47 \to 59 \to next
$$
從開頭 (即上方 `HEAD`) 找起，`59` 這個節點需要存取或比對 7 次才能找到，你直覺可能想到[二分法](https://en.wikipedia.org/wiki/Binary_search_algorithm)，但對於 linked list 來說，隨機存取節點的時間複雜度仍是 $O(n)$，也就是說，二分法無法帶來效益。
我們可在鏈結串列中，增加額外的 "skip" (作用是提供資料存取的捷徑) 節點，如下：
> "skip" 一詞在英語的意思很多，這裡取[韋伯字典](https://www.merriam-webster.com/dictionary/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**](https://en.wikipedia.org/wiki/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 <= 7` 得知 level 4 不存在 `7`，但其他 level 可能具備。於是跳到 level 3 繼續找
2. 從 level 3 比對，因 `4 <= 7` 且 `6 <= 7` 得知 level 3 一樣不存在 `7`，於是跳到 level 2 繼續找
3. 從 level 2 比對，因 `9 >= 7` 表示此 level 不存在 `7`，跳去 level 1
4. 在 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 的流程:
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`):
```cpp
#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](http://www.cse.yorku.ca/~oz/hash.html) 的作用是產生隨機分佈的的雜湊函數，常見的形式為:
$$
f（hash）= hash \times 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` 撰寫的測試程式如下:
```cpp
#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)`
:::success
延伸問題:
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)
:::
---
Sign in with Wallet
Connect another wallet