# 2020q3 Quiz 15
contributed by < `Veternal1226` >
###### tags: `sysprog2020`

---
[TOC]

---
[quiz15 原題目連結](https://hackmd.io/@sysprog/2020-quiz15)

---
# 測驗 `1`
LeetCode [835. Image Overlap](https://leetcode.com/problems/image-overlap/) 給定二個影像 A 和 B，二者皆為大小相同的二維正方形矩陣，內部以二進位表示。我們轉換其中一個影像，向左、右、上，或下滑動任意數量的單位，並將其置於另一個影像之上，隨後，該轉換的重疊 (overlap) 指二個影像都有 1 的位置數量，注意：轉換不包含向任一方向旋轉。於是，最大可能的重疊為何？

範例一:


範例 1:

- 輸入
$A=\begin{pmatrix}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 1 & 0 \\
\end{pmatrix}$
$B=\begin{pmatrix}
0 & 0 & 0 \\
0 & 1 & 1 \\
0 & 1 & 0 \\
\end{pmatrix}$

- 輸出:
- 3
- 解釋
- 將 A 向右移動 1 個單位，然後向下移動 1 個單位
- 二張影像中都存在 1 的位置總數為 3，見下圖紅色標記

思路：找出所有 1 的位置，對兩個矩陣的所有這些位置進行求差，再統計這些差出現最多的次數。兩個坐標的差表示什麼？即是將其中一個坐標移動到另一個坐標需要移動的向量。於是，在走訪個別單元的過程中，我們找出 A 中所有值為 1 的坐標，移動到 B 中所有值為 1 的坐標需要移動的向量。於是乎，在這些向量中出現次數最多的向量，就是我們要求的整個矩陣應該移動的向量。

以下程式碼針對 LeetCode [835. Image Overlap](https://leetcode.com/problems/image-overlap/)，提出可能的解法：

#include <string.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))

static inline int overlap_count(unsigned int *AA, unsigned int *BB, int size)
{
    int res = 0;
    for (int i = 0; i < size; ++i)
        res += __builtin_popcount(AA[i] & BB[i]);
    return res;
}

static void translate(unsigned int *v,
                      int vsize,
                      int i,
                      int j,
                      unsigned int *res)
{
    memcpy(res, v, sizeof(unsigned int) * vsize);
    int mask[32];
    for (int k = 0; k < 32; k++)
        mask[k] = (1U << k) - 1;
    int n = vsize;
    if (i >= 0) {
        for (int k = 0; k < n; k++)
            res[k] >>= i;
    } else {
        i = -i;
        for (int k = 0; k < n; k++)
            res[k] = ((res[k] << i) & mask[n]);
    }

    if (j >= 0) {
        ITER1;
        for (int k = 0; k < j; k++)
            res[k] = 0;
    } else {
        j = -j;
        ITER2;
        for (int k = n - j; k < n; k++)
            res[k] = 0;
    }
}

int largestOverlap(int **img1, int img1Size, int *img1ColSize,
                   int **img2, int img2Size, int *img2ColSize)
{
    int n = img1Size;
    unsigned int A[n], B[n];
    memset(A, 0, sizeof(unsigned int) * n);
    memset(B, 0, sizeof(unsigned int) * n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (img1[i][j] == 1)
                A[i] |= 1 << j;
            if (img2[i][j] == 1)
                B[i] |= 1 << j;
        }
    }

    int res = 0;
    for (int i = -(n - 1); i <= (n - 1); ++i) {
        for (int j = -(n - 1); j <= (n - 1); ++j) {
            unsigned int AA[n];
            translate(A, n, i, j, AA);
            res = max(res, overlap_count(AA, B, n));
        }
    }
    return res;
}

請補完程式碼，使其符合 LeetCode 題目要求。

參考資料:
- [LeetCode 835. Image Overlap](https://www.cnblogs.com/grandyang/p/10355589.html)

作答區

ITER1 = (c\)

`(a)` `for (int k = 0; k < n - j; k++) res[k + j] = res[k]`
`(b)` `for (int k = 0; k <= n - j; k++) res[k + j] = res[k]`
`(c)` `for (int k = n - j - 1; k >= 0; k--) res[k + j] = res[k]`
`(d)` `for (int k = n - j; k >= 0; k--) res[k + j] = res[k]`

ITER2 = (b)

`(a)` `for (int k = j; k < n; k++) res[k + j] = res[k]`
`(b)` `for (int k = j; k < n; k++) res[k - j] = res[k]`
`(c)` `for (int k = j - 1; k < n; k++) res[k + j] = res[k]`
`(d)` `for (int k = j - 1; k < n; k++) res[k - j] = res[k]`

## 程式碼運作
:::success
延伸題目:
1. 解釋上述程式碼運作原理
:::

- int largestOverlap()
47~50 行為初始化
51~58 行將原本題目提供的 bitmap 轉成一維的陣列，將 bitmap 以 int 格式儲存
60~67 行測試所有平移結果，找出重疊的最大值
64 行的 `translate()` 將原本的陣列做平移
65 行的 `overlap_count()` 用來算出重疊量，並檢查是否需更新最大值

- static void translate()
21 行的 `mask` 用來取出右移後真正位於比較空間內的 bits，比較空間外的會被 `mask` 清為 0
23~30 行進行左右平移 (x軸)
32~41 行進行上下平移 (y軸)

y軸範圍參考此圖
`j >= 0` :
因此在 `j >= 0` 的情況下
範圍為 (n-1-j) ~ 0
搬移方式為 res[k + j] = res[k]

所以 ITER1 = ==`(c)` `for (int k = n - j - 1; k >= 0; k--) res[k + j] = res[k]`==

`j < 0` :
因此在 `j < 0` 的情況下
範圍為 (-j) ~ (n-1)
搬移方式為 res[k + j] = res[k]
但因題目先將 `j = -j`
因此範圍改為 j ~ (n-1)
搬移方式為 res[k - j] = res[k]

所以 ITER2 = ==`(b)` `for (int k = j; k < n; k++) res[k - j] = res[k]`==

- static inline int overlap_count()
7~8 行用於計算兩圖重疊量，先進行 AND 疊合，在使用 `popcount()` 方式計算 `1` 的數量，計算行數與原矩陣 _大小相同_ 。 (此處即為可優化的部分)

## 優化
:::success
延伸題目:
2. 提出效率更高，且空間佔用更少的 C 程式碼實作
:::
主要更改處為取消 34、35、39、40 行的補0行為，把 37 行的 -j 改成 j 方便理解，並將 overlap_count 的比較範圍縮小。

舉例圖解:
>藍色陣列為平移前，紅色陣列為平移後，綠框表有興趣之區域 ( 搬移基準點或比較範圍 )。

以 `n = 8, i = 2, j = 2` 為例:
搬移過程:
搬移順序為從 y = n-j-1 行開始至 y= 0 (方向往上)，往右移2單位、下移2單位

比較範圍:

優化後比較範圍:

以 n=8, i=-2, j=-2 為例:
搬移過程:
搬移順序為從 y = 0-j (同義於 -j ) 行開始至 y= n-1 (方向往下)，往左移2單位、上移2單位

比較範圍:

優化後比較範圍:

原本方法記憶體占用:

優化比較範圍後記憶體占用:

優化後程式碼:

#include <string.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))

static inline int overlap_count(unsigned int *AA, unsigned int *BB, int size, int j)
{
    int res = 0;
    if(j>=0){
        for (int k = j; k < size; ++k)
        res += __builtin_popcount(AA[k] & BB[k]);
    }
    else{
        for (int k = 0; k < size+j; ++k)
        res += __builtin_popcount(AA[k] & BB[k]);
    }
    return res;
}

static void translate(unsigned int *v,
                      int vsize,
                      int i,
                      int j,
                      unsigned int *res)
{
    memcpy(res, v, sizeof(unsigned int) * vsize);
    int mask[32];
    for (int k = 0; k < 32; k++)
        mask[k] = (1U << k) - 1;
    int n = vsize;
    if (i >= 0) {
        for (int k = 0; k < n; k++)
            res[k] >>= i;
    } else {
        i = -i;
        for (int k = 0; k < n; k++)
            res[k] = ((res[k] << i) & mask[n]);
    }

    if (j >= 0) {
        for (int k = n - j - 1; k >= 0; k--) 
            res[k + j] = res[k];
    } else {
        for (int k = -j ; k < n; k++)
            res[k + j] = res[k];

    }
}

int largestOverlap(int **img1, int img1Size, int *img1ColSize,
                   int **img2, int img2Size, int *img2ColSize)
{
    int n = img1Size;
    unsigned int A[n], B[n];
    memset(A, 0, sizeof(unsigned int) * n);
    memset(B, 0, sizeof(unsigned int) * n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (img1[i][j] == 1)
                A[i] |= 1 << j;
            if (img2[i][j] == 1)
                B[i] |= 1 << j;
        }
    }

    int res = 0;
    for (int i = -(n - 1); i <= (n - 1); ++i) {
        for (int j = -(n - 1); j <= (n - 1); ++j) {
            unsigned int AA[n];
            translate(A, n, i, j, AA);
            res = max(res, overlap_count(AA, B, n, j));
        }
    }
    return res;
}

---
# 測驗`2`
LeetCode [1569. Number of Ways to Reorder Array to Get Same BST](https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/) 給定一個陣列 nums 表示 $1$ 到 $n$ 的排列，依據元素在 `nums` 中的順序，依次插入一個初始為空的二元搜尋樹 (BST)。請你統計將 `nums` 重新排序後，滿足以下條件的個數：
- 重排後得到的 BST 與 nums 原本數值順序得到的 BST 相同。

例如，給定
$nums=[2,1,3]$，我們得到一棵 `2` 為 root、`1` 為 left 及 `3` 為 right 的樹。
陣列 $[2,3,1]$ 也能得到相同的 BST，但 $[3,2,1]$ 會得到一棵不同的 BST 。

由於答案可能會很大，請將結果對 $10^9+7$ 取餘數。

- 為何是 $10^9+7$ 呢？請見 [Modulo 10^9+7 (1000000007)](https://www.geeksforgeeks.org/modulo-1097-1000000007/)

範例 1

- 輸入
- $nums=[2,1,3]$
- 輸出
- `1`
- 解釋
- 我們將 `nums` 重排，$[2,3,1]$ 可得到相同的 BST
- 沒有其他得到相同 BST 的方法

範例 2

- 輸入
- $nums=[3,4,5,1,2]$
- 輸出
- `5`
- 解釋
- 下面 5 個陣列可得到相同的 BST
- $[3,1,2,4,5]$
- $[3,1,4,2,5]$
- $[3,1,4,5,2]$
- $[3,4,1,2,5]$
- $[3,4,1,5,2]$

範例 3

- 輸入
- $nums=[1,2,3]$
- 輸出
- `0`
- 解釋
- 沒有其他排列順序能得到相同的 BST

範例 4

- 輸入
- $nums=[3,1,2,5,4,6]$
- 輸出
- `19`

範例 5

- 輸入
- $nums=[9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]$
- 輸出
- `216212978`
- 解釋
- 得到相同 BST 的個數是 `3216212999`
- 將其對 $10^9+7$ 取餘後得到 `216212978`

根節點是陣列第一個數，分為左右兩個子樹，左右子樹之間的順序若不變即可
假設左子樹 $L$ 長度 $nL$，右子樹 $R$ 長度 $nR$，則有效組合數為 $C^{nL}_{nL+nR}×f(L)×f(R)$

#include <string.h>

static const int MOD = 1e9 + 7; /* prime */

static int recursive(int *nums, int nums_size, int N, DECL)
{
    if (nums_size <= 2)
        return 1;
    int left[N + 1], left_size = 0, right[N + 1], right_size = 0;
    for (int i = 1; i < nums_size; i++)
        nums[i] > nums[0] ? (right[right_size++] = nums[i])
                          : (left[left_size++] = nums[i]);
    int l = recursive(left, left_size, N, cache),
        r = recursive(right, right_size, N, cache);
    return (((long) cache[nums_size - 1][left_size] * l % MOD) * r) % MOD;
}

int numOfWays(int *nums, int N)
{
    int comb[N + 1][N + 1]; /* combination table */
    memset(comb, 0, sizeof(comb));

    comb[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= N; j++)
            INIT;
    }
    return recursive(nums, N, N, comb) - 1;
}

DECL = (d)

`(a)` `int cache[N][N]`
`(b)` `int cache[N - 1][N - 1]`
`(c)` `int cache[N + 1][N]`
`(d)` `int (*cache)[N + 1]`
`(e)` `int (*cache)[N]`

INIT = (a)
`(a)` `comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD`
`(b)` `comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1])`
`(c)` `comb[i][j] = (comb[i][j] + comb[i - 1][j - 1]) % MOD`
`(d)` `comb[i][j] = (comb[i][j] + comb[i - 1][j - 1])`
`(e)` `comb[i][j] = (comb[i][j - 1] + comb[i - 1][j - 1]) % MOD`
`(f)` `comb[i][j] = (comb[i][j - 1] + comb[i - 1][j - 1])`

## 解題想法
從提示與[花花醬](https://zxi.mytechroad.com/blog/recursion/leetcode-1569-number-of-ways-to-reorder-array-to-get-same-bst/)的教學中，可了解此題的解題關鍵為:

>根節點是陣列第一個數，分為左右兩個子樹，左右子樹之間的順序若不變即可
>假設左子樹 $L$ 長度 $nL$，右子樹 $R$ 長度 $nR$，則有效組合數為 $C^{nL}_{nL+nR}×f(L)×f(R)$

題目所挖空的部分為取組合的部分 ($C^{nL}_{nL+nR}$)
目的為先把組合的結果算出並建好表格，使每次取組合時不用重算

## 程式碼運作
:::success
延伸題目:
1. 解釋上述程式碼運作原理
:::
- int numOfWays()
23~28 行: 建立組合表，之後可直接查表，可以不用重複計算相同的組合結果

    comb[0][0] = 1;
    for (int i = 1; i <= N; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= N; j++)
            INIT;
    }

根據花花醬的教學，此表格是算出 pascal's triangle 中各元素的值。
因此 INIT 應選 ==(a) comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD==

29 行: 進入 recursive() 遞迴函式，進入遞迴時，將組合表表一起傳入，從 20 行可看出組合表的大小為 [N+1][N+1]
DECL選項中只有 ==`(d)` `int (*cache)[N + 1]`== 符合，故選 (d)

- static int recursive()
7~8 行: 終止條件:`size<=2`
9 行: 初始化
10~12 行: 將大於當前 nums[0] 的值放入右子樹，將小於 nums[0] 的值放入左子樹
13~14 行: 進入遞迴，回傳結果為子樹可能的組合數
15 行: 回傳值應為 $C^{nL}_{nL+nR}×f(L)×f(R)$，組合數使用查表方式得到值；為了避免相乘結果數值太大，每次相乘均需對 $10^9+7$ 取餘數。

>對$10^9+7$取餘數原因:
hash成本太高，不想太複雜操作 (需考慮碰撞、hash function 等)
單純取餘數會有不夠分散的問題 (ex: 360%2=0，結果集中在小數值不夠分散)
因此採用對大質數取餘數的方式實作

## 優化
:::success
延伸題目:
2. 提出效率更高，且空間佔用更少的 C 程式碼實作
:::
從花花醬的教學中得知建立組合表方式是算出 pascal's triangle 中各元素的值，而 pascal's triangle 並不會用到右上方的三角形。
comb在矩陣中的儲存方式:

右上角紅色三角形表示不會使用到的位置

原本建表過程中的第 26 行如下

	for (int j = 1; j <= N; j++)

可看出其計算了整張表的值，將 j 的範圍改成 `j <= i` 能夠節省計算右上三角形的值花費的計算成本。實際改動如下列程式碼。

	for (int j = 1; j <= i; j++)

優化前執行時間:

優化後執行時間:

---
# 測驗`3`
在 Ubuntu/Debian Linux 中，可執行 sudo apt install dictionaries-common 以安裝辭典套件，於是可得到 /usr/share/dict/words 檔案，後者包含超過 10 萬個單字/詞:

$ wc -l /usr/share/dict/words

考慮以下 C 程式 (strsearch.c) 可從給定的詞典中檢索:

/*
 * Hash table is represented as `htable` array of size N (N = number of lines in
 * dict), where each element either points to the end of a singly-linked list or
 * is equal to zero. Lists are stored in pre-allocated array `clist` of size N.
 *
 * This implementation is memory-efficient and cache-friendly, requiring only
 * 12N + O(1) bytes of "real" memory which can be smaller than the size of
 * dict, sacrificing however for request processing speed, which is
 * O(req_size) in most cases, but may be up to O(dict_size) due to hash collision.
 */

#include <fcntl.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

/* 2 additional bytes for '\n' and '\0' */
#define MAX_REQUEST_SIZE (128 * 1024 * 1024 + 2)

struct htable_entry {
    uint32_t ptr;
};

struct collision_list {
    uint32_t fpos;
    uint32_t len;
    uint32_t prev;
};

struct compr_collision_list {
    uint32_t fpos;
    uint32_t len;
};

typedef struct htable_entry htable_entry_t;
typedef struct collision_list collision_list_t;
typedef struct compr_collision_list compr_collision_list_t;

static char *dict;
static htable_entry_t *htable;
static collision_list_t *clist;
static compr_collision_list_t *cclist;
static size_t num_of_bytes, num_of_lines;
static size_t num_of_buckets;
static int clist_size = 1;

static uint32_t hash(char *s, size_t len)
{
    uint32_t hash = 5381;
    for (size_t i = 0; i < len; i++)
        hash = ((hash << 5) + hash) + (s[i] - 32);
    return hash % num_of_buckets;
}

static void htable_insert(size_t fpos, size_t len)
{
    uint32_t h = hash(dict + fpos, len);
    clist[clist_size].fpos = fpos;
    clist[clist_size].len = len;
    clist[clist_size].prev = htable[h].ptr;
    htable[h].ptr = clist_size;
    ++clist_size;
}

static bool htable_lookup(char *s, size_t len)
{
    uint32_t h = hash(s, len);
    uint32_t ptr = htable[h].ptr;
    uint32_t nextptr = htable[h + 1].ptr;
    for (; ptr < nextptr; ptr++) {
        if ((len == cclist[ptr].len) &&
            !memcmp(s, dict + cclist[ptr].fpos, len))
            return true;
    }
    return false;
}

int main(int argc, char **argv)
{
    if (argc != 2) {
        printf("usage: %s dictionary_file\n", argv[0]);
        return 2;
    }

    /* Map dictionary file directly to memory for easier access from program */
    int dictfd;
    if ((dictfd = open(argv[1], O_RDONLY)) < 0)
        return 1;

    struct stat st;
    fstat(dictfd, &st);
    num_of_bytes = st.st_size;
    if ((dict = mmap(0, num_of_bytes, PROT_READ, MAP_PRIVATE, dictfd, 0)) ==
        MAP_FAILED)
        return 1;

    /* Count number of lines in file */
    for (size_t i = 0; i < num_of_bytes; i++) {
        if (dict[i] == '\n')
            num_of_lines++;
    }
    num_of_lines++;

    num_of_buckets = num_of_lines;
    htable = calloc(num_of_buckets + 1, sizeof(htable_entry_t));
    clist = malloc((num_of_lines + 1) * sizeof(collision_list_t));

    size_t prev_start = 0;
    for (size_t i = 0; i < num_of_bytes; i++) {
        if (dict[i] == '\n') {
            htable_insert(prev_start, P1);
            prev_start = P2;
        }
    }

    /* Compress collision list and update ptrs in htable accordingly */
    htable[num_of_buckets].ptr = num_of_lines;
    cclist = malloc((num_of_lines + 1) * sizeof(compr_collision_list_t));
    size_t clines = 0;
    for (size_t i = 0; i < num_of_buckets; i++) {
        uint32_t ptr = htable[i].ptr;
        htable[i].ptr = clines;
        while (ptr) {
            cclist[clines].fpos = clist[ptr].fpos;
            cclist[clines].len = clist[ptr].len;
            ptr = clist[ptr].prev;
            clines++;
        }
    }
    free(clist);

    /* Ready to accept requests */
    char *req_buf = malloc(MAX_REQUEST_SIZE);

    while (!feof(stdin)) {
        fgets(req_buf, MAX_REQUEST_SIZE, stdin);
        size_t len = strlen(req_buf);
        /* Exit on "exit" command */
        if (!strncmp(req_buf, "exit\n", len))
            break;
        printf("%s: %s\n", req_buf, htable_lookup(req_buf, len) ? "YES" : "NO");
    }

    free(req_buf);
    free(htable);
    free(cclist);
    munmap(dict, num_of_bytes);
    close(dictfd);
    return 0;
}

給定測試輸入 (檔名: inputs) 如下:

gnu
linux
kernel
X
XX
exit

測試方式:

$ ./strsearch /usr/share/dict/words < inputs

預期執行結果:

gnu
: YES
linux
: NO
kernel
: YES
X
: YES
XX
: NO

請補完程式碼。
P1 = (d)

`(a)` `prev_start + i`
`(b)` `prev_start + i + 1`
`(c)` `i - prev_start`
`(d)` `i - prev_start + 1`

P2 = (b)

`(a)` `i`
`(b)` `i + 1`
`(c)` `i - 1`

## 解題想法

    size_t prev_start = 0;
    for (size_t i = 0; i < num_of_bytes; i++) {
        if (dict[i] == '\n') {
            htable_insert(prev_start, P1);
            prev_start = P2;
        }
    }

static void htable_insert(size_t fpos, size_t len)
{
    uint32_t h = hash(dict + fpos, len);
    clist[clist_size].fpos = fpos;
    clist[clist_size].len = len;
    clist[clist_size].prev = htable[h].ptr;
    htable[h].ptr = clist_size;
    ++clist_size;
}

可從這兩段程式碼中得知
116行的行為為: 將起始點 prev_start 與長度 P1 傳入 htable_insert
117行的行為為: 更新起始點 prev_start

圖解：

將起始位址 `prev_start - 0` 與長度 `i - prev_start +1` 作為參數輸入 `htable_insert` 中，再將 `prev_start` 更新到 `i+1` 的位址，所以題目要求的程式碼應如下：

htable_insert(prev_start, i - prev_start + 1);
prev_start = i + 1;

因此，P1應選 ==`(d)` `i - prev_start + 1`== ， P2應選 ==`(b)` `i + 1`== 。

## 程式碼運作原理
:::success
延伸題目:
1. 解釋上述程式碼運作原理
:::

- static uint32_t hash()
使用 DJB Hash Function
回傳值為 hash值 除以 詞的總數量
參考來源:
>1. [algorithm - Reason for 5381 number in DJB hash function? - Stack Overflow](https://stackoverflow.com/questions/10696223/reason-for-5381-number-in-djb-hash-function)
>2. [hash](http://www.cse.yorku.ca/~oz/hash.html)

- static void htable_insert()
將新的詞輸入至 htable 與 clist 中以方便查詢與比較
62 行: 取得 hash 值
63 行: 記錄該詞的開頭位置，放入 clist.fpos
64 行: 計算該詞的長度放入 clist.len
65 行: 記錄 htable 中該詞位置的原有指標，使用 link list 的方式處理碰撞
66 行: 更新 htable 該詞位置上的 list 長度

- static bool htable_lookup()
查詢 htable 中是否存在輸入的詞
72 行: 取得 hash 值
73 行: 取得 htable 中記錄的指標
74 行: 取得 htable 中下個記錄的指標
75~80 行: 查詢 cclist 中是否有輸入的詞出現，並回傳結果

- int main()
85~88 行: 檢查參數格式是否正確
91~93 行: 開啟 `argv[1]` 代表的檔案以作為辭典檔輸入
95~100 行: 將開啟檔案的 file descriptor轉成 stat 格式，利用 stat 資訊使用 `mmap()` 將辭典檔映射到記憶體，把檔案操作變成記憶體操作。
>使用mmap原因: I/O最佳化
>把檔案操作變成記憶體操作
>檔案操作 (fopen): 詞典檔案太大時啟動時要讀很久，但只需開啟檔案一次。
>記憶體操作 (mmap): 對應到記憶體，發生page fault時才需要讀取成本，但讀取次數隨 page fault 次數增加。

103~107 行: 計算辭典檔行數
109~111 行: 宣告空間放置 htable 與 clist
113~119 行: 利用 `\n` 做斷詞依據，將每個字放入 htable 中，放入 htable 位置的依據為 hash function (此題使用 DJB Hash Function)
122~134 行: 使用 collision list方式處理碰撞
138 行: 初始化 fgetd 需要的 buffer 空間
140~147 行: 從標準輸入查詢各字串段是否位於 hash function 中
141 行: 從標準輸入輸入至 req_buf 中
142 行: 計算輸入的字串長度
144~146 行: 查詢 htable 內能不能查詢到輸入的詞

附註:
hash 存在的原因是為了減少重複查詢的查詢成本。
有驗證過在 ubuntu 20 環境下此程式可正確執行。

:::success
延伸題目:
2. 提出效率更高，且空間佔用更少的 C 程式碼實作
:::

//TODO