2020q3 Quiz 15

contributed by < Veternal1226 >

tags: `sysprog2020`

2020q3 Quiz 15
測驗 1
- 程式碼運作
- 優化
測驗2
測驗3
- 解題想法
- 程式碼運作原理

測驗 `1`

LeetCode 835. Image Overlap 給定二個影像 A 和 B，二者皆為大小相同的二維正方形矩陣，內部以二進位表示。我們轉換其中一個影像，向左、右、上，或下滑動任意數量的單位，並將其置於另一個影像之上，隨後，該轉換的重疊 (overlap) 指二個影像都有 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 →

範例 1:

輸入

$A = (\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix})$

$B = (\begin{matrix} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{matrix})$
輸出:
- 3
解釋
- 將 A 向右移動 1 個單位，然後向下移動 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 →
- 二張影像中都存在 1 的位置總數為 3，見下圖紅色標記
  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 →

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

以下程式碼針對 LeetCode 835. 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

作答區

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]

程式碼運作

延伸題目:

解釋上述程式碼運作原理

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 的數量，計算行數與原矩陣 大小相同 。 (此處即為可優化的部分)

優化

延伸題目:
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 給定一個陣列 nums 表示

1

到

n

的排列，依據元素在 nums 中的順序，依次插入一個初始為空的二元搜尋樹 (BST)。請你統計將 nums 重新排序後，滿足以下條件的個數：

重排後得到的 BST 與 nums 原本數值順序得到的 BST 相同。

例如，給定

n u m s = [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)

範例 1

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

範例 2

輸入
- $n u m s = [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

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

範例 4

輸入
- $n u m s = [3, 1, 2, 5, 4, 6]$
輸出
- 19

範例 5

輸入
- $n u m s = [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

長度

n L

，右子樹

R

長度

n R

，則有效組合數為

C_{n L + n R}^{n L} \times f (L) \times 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])

解題想法

從提示與花花醬的教學中，可了解此題的解題關鍵為:

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

題目所挖空的部分為取組合的部分 (

C_{n L + n R}^{n L}

)
目的為先把組合的結果算出並建好表格，使每次取組合時不用重算

程式碼運作

延伸題目:

解釋上述程式碼運作原理

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_{n L + n R}^{n L} \times f (L) \times f (R)$ ，組合數使用查表方式得到值；為了避免相乘結果數值太大，每次相乘均需對
$10^{9} + 7$ 取餘數。

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

優化

延伸題目:
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 。

程式碼運作原理

延伸題目:

解釋上述程式碼運作原理

static uint32_t hash()
使用 DJB Hash Function
回傳值為 hash值除以詞的總數量
參考來源:

algorithm - Reason for 5381 number in DJB hash function? - Stack Overflow

hash

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 環境下此程式可正確執行。

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

//TODO

2020q3 Quiz 15

tags: sysprog2020

測驗 1

程式碼運作

優化

測驗2

解題想法

程式碼運作

優化

測驗3

解題想法

程式碼運作原理

Read more

Sony X Performance (F8132) ROOT 筆記

Android (2021 summer)

2020q3 Homework2 (quiz2)

2020q3 Homework6 (quiz6)

tags: `sysprog2020`

測驗 `1`

測驗`2`

測驗`3`