2022q1 Homework1 (quiz1)

contributed by < NOVBobLee >

測驗題目

測驗 1 LeetCode - Two Sum

Two sum 若以暴力法，則時間複雜度為

$O(n^2)$ 。若改以使用湊雜表，可降低時間複雜度到

$O(n)$ 以下。以下為使用 Linux 湊雜表結構的湊雜表實作，拆開解釋，最後利用他來完成 Two sum 。

湊雜表結構宣告

Linux 的湊雜表使用兩種結構，一為 hlist_head ，為湊雜表 bucket 的開頭，是單向鍊結結構，二為 hlist_node ，為 bucket 裡的元素連結，是雙向鍊結結構。為何不使用通用的 list_head ，其原因在湊雜表為減少碰撞發生，會把 bucket 的數量增大，且不少 bucket 是空的，若使用雙向鍊結結構，一個開頭就需要兩個指標的空間。第二是如果碰撞變少，那麼 bucket 裡的元素數量也不多，不需要像環狀雙向鍊結結構可以從尾部或從頭部兩種方向走訪。

為使 hlist_node 的插入刪除方便，其使用雙向鍊結結構。但是 bucket 的開頭與元素連結卻是使用不同的結構，為使雙練鍊結結構與單向鍊結結構結合，且插入刪除不會因為前一個是開頭而需要新的分支， hlist_node 改使用的 pprev ，指標的指標，非常漂亮。

而湊雜表本體為 map_t ，其包含多個 buckets （ ht ），而其數量會使用巨集 MAP_HASH_SIZE 來決定，固定為

$2$ 的冪。為何存 bits 而非實際數量？是因為湊砸函數 hash 頻繁使用到，而實際數量只有在建立和釋放湊雜表的時候用到（ 2 次）而已。

struct hlist_node { struct hlist_node *next, **pprev; };
struct hlist_head { struct hlist_node *first; };
typedef struct { int bits; struct hlist_head *ht; } map_t;

#define MAP_HASH_SIZE(bits) (1 << bits)

建立空湊雜表

輸入為 bits ，代入剛提到的巨集 MAP_HASH_SIZE 會得到湊雜表 bucket 要配置的數量。

map_t *map_init(int bits) {
    /* 湊雜表空間配置 */
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    /* buckets 開頭空間配置 */
    map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));
    if (map->ht) {
        for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
            /* bucket 開頭初始化 */
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}

湊雜表元素與相關巨集

湊雜表元素 hash_key ，包含一個 key ，拿來定位 bucket 的位置，一個 data ，存放資料的地址，和 node ，與湊雜表連結用。

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

如果我們從 bucket 的開頭出發，得到的會是 hlist_node ，這樣要怎麼找到包裝他的容器 hash_key ？其方法是使用下面的巨集 container_of ，在得知 hlist_node 在 hash_key 裡的位移量後，可以反推得到容器的開頭位置。

#define container_of(ptr, type, member)               \
    ({                                                \
        void *__mptr = (void *) (ptr);                \
        ((type *) (__mptr - offsetof(type, member))); \
    })

湊雜函數則是使用以下的函式 hash ，用來取得 key_hash 的 key 值，其使用的是 Fibonacci hashing 。可以看到我們 buckets 的數量用

$2$ 的冪，取 modulo 可以直接使用 bit-shift ，比起使用 modulo 任意數更快。

#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
    /* High bits are more random, so use them. */
    return (val * GOLDEN_RATIO_32) >> (32 - bits);
}

搜尋 hash_key

輸入 key 找尋相對應的 hash_key 。

static struct hash_key *find_key(map_t *map, int key) {
    /* bucket 開頭位置 */
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    /* 走訪該 bucket 的元素 */
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        /* 找到了 */
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

取得 key 對應的資料

用 find_key 搜尋 hash_key 湊砸表元素，找到則返回裡面存的資料 data ，否則返回 NULL 。

void *map_get(map_t *map, int key)
{
    struct hash_key *kn = find_key(map, key);
    return kn ? kn->data : NULL;
}

加入湊砸表元素

此函式為插入新的湊雜表元素用，若 key 值已經被使用，則失敗，必須使用沒使用過的 key 值。

void map_add(map_t *map, int key, void *data)
{
    /* 檢查是否 key 值重複 */
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    /* 建立新的湊雜表元素 */
    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    /* 插入到湊雜表對應的 bucket 裡 */
    struct hlist_head *h = &map->ht[hash(key, map->bits)];
    struct hlist_node *n = &kn->node, *first = h->first;
    AAA;
    if (first)
        first->pprev = &n->next;
    h->first = n;
    BBB;
}

這邊出現 AAA 與 BBB 填空，在建立新的湊雜表元素後，我們要將其加入到湊雜表中，可以看到 h 是湊雜表的 bucket ， n 是剛建立的湊雜表元素的連結 node ，也就是說要把 n 加入 h 中。

要幫 n 作連結卻沒看到 n->next 與 n->pprev 的賦值，所以這兩個填空應該與剛提的兩個賦值相關。

然後 first 是 bucket 的第一個元素，加上第 18 行 h->first = n ，所以 n 是要插在 bucket 第一個的位置。又在第 17 行 first->pprev = &n->next 會使用到 n->next 的值，所以 AAA 應該是 n->next = first。

那麼剩下的 BBB 就是要完整雙向鍊結結構，將 n->pprev 指到 h->first 的位置上，即 n->pprev = &h->first 。

刪除湊雜表

遍歷湊雜表的 buckets 和 bucket 裡的元素，一一釋放空間。

void map_deinit(map_t *map)
{
    if (!map)
        return;

    /* 走訪湊雜表的 buckets */
    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
        struct hlist_head *head = &map->ht[i];
        /* 走訪 bucket 裡的元素 */
        for (struct hlist_node *p = head->first; p;) {
            struct hash_key *kn = container_of(p, struct hash_key, node);
            struct hlist_node *n = p;
            p = p->next;

            if (!n->pprev) /* unhashed */
                goto bail;

            struct hlist_node *next = n->next, **pprev = n->pprev;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

        bail:
            free(kn->data);
            free(kn);
        }
    }
    free(map);
}

看了一下插入刪除元素的操作，沒看到會有 if (!n->pprev) 為真的情況。待查。

Two sum

給定一數 target ，在給定數列 nums 中找尋兩個數相加的和為 target 的組合。

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    /* 建立空湊雜表 */
    map_t *map = map_init(10);
    *returnSize = 0;
    int *ret = malloc(sizeof(int) * 2);
    if (!ret)
        goto bail;

    /* 一邊插入湊雜表元素，一邊找尋是否有剛好配對的數，在剛才插入的湊雜表元素中 */
    for (int i = 0; i < numsSize; i++) {
        int *p = map_get(map, target - nums[i]);
        if (p) { /* found */
            ret[0] = i, ret[1] = *p;
            *returnSize = 2;
            break;
        }

        p = malloc(sizeof(int));
        *p = i;
        map_add(map, nums[i], p);
    }

bail:
    map_deinit(map);
    return ret;
}

延伸問題：

1. 解釋程式碼運作原理
2. 研讀 Linux 核心原始程式碼 include/linux/hashtable.h 及對應的文件 How does the kernel implements Hashtables?，解釋 hash table 的設計和實作手法，並留意到 tools/include/linux/hash.h 的 GOLDEN_RATIO_PRIME，探討其實作考量

測驗 2 LeetCode - Remove Duplicates from Sorted List II

給定一個已排序過的單向鍊結結構，移除重複值的元素，如 1-1-2-3 變成 2-3 。

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (!head)
        return NULL;

    if (COND1) {
        /* Remove all duplicate numbers */
        while (COND2)
            head = head->next;
        return deleteDuplicates(head->next);
    }

    head->next = deleteDuplicates(head->next);
    return head;
}

程式碼可以看出是使用遞迴，然後遞迴的結束是回傳 NULL 或者返回 head 。再來看第二個 if ，若 COND1 為真，則會進入 remove all duplicate numbers 的區域，所以可以推測出 COND1 應該跟檢查重複值有關，而且檢查重複值元素的第一個，所以 COND1 應該是 head->next && head->val == head->next->val 。

然後繼續推測他是如何移除重複值元素，試想一個例子， 1-2-2-3 會變成 1-3 ，其中 1, 3 要作連結。在將這例子套進程式碼， 1->next 會進入 2 的遞迴，等待回傳 3 的指標。而 2 的遞迴會進入 COND1 的區塊，這時要把 head 要移到哪裡，代入 head->next 才可以返回 3 的指標？因為返回只有兩種， NULL 和 head ，所以剛才要帶入的 head->next 應該就是 3 的指標。也就是說 head 應該要移到 3 的前一個元素， 2 ，那麼 COND2 區塊就是要把 head 移到重複元素的最後一個，那麼應該填 head->next && head->val == head->next->val 。

遞迴方式：走訪每一個元素，若有重複值的元素，則尋找下一個不重複值的元素，傳回其指標，跟第一個重複值元素的前一個元素相接。若沒遇到重複值元素，則照原連結方式連接。

改寫成迭代方式，原理跟上面方法一樣，只是我們不能用遞迴的 stack 紀錄前一個不重複值元素的指標，所以加入間接指標 dup_pprev 代替。

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    struct ListNode *orig_head, **dup_pprev;
    
    if (!head || !head->next)
        return head;

    orig_head = head;
    /* 初始化 */
    dup_pprev = &head;

    do {
        /* 發現有重複值元素 */
        if (head->next && head->val == head->next->val) {
            /* 直到找到不重複值元素 */
            while (head->next && head->val == head->next->val)
                head = head->next;
            /* 前一個不重複值元素跨過重複值元素，跟找到的不重複值元素連接 */
            *dup_pprev = head->next;
        } else {
            dup_pprev = &(*dup_pprev)->next;
        }
        
        head = head->next;
    } while (head); /* 走訪所有元素 */

    return orig_head;
}

延伸問題：

1. 嘗試避免遞迴，寫出同樣作用的程式碼
2. 以類似 Linux 核心的 circular doubly-linked list 改寫，撰寫遞迴和迭代 (iterative) 的程式碼
   • 迭代
   • 遞迴

使用類似 Linux list_head 雙向循環鍊結結構的版本（假設 head 沒有 val 值，只作雙向鍊結結構的開頭）：

struct ListNode {
    int val;
    struct ListNode *next, *prev;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    struct ListNode *orig_head, *next;
    int found_dup = 0;
    /* 若 head 為 NULL, 空的或只有 1 個元素 */
    if (!head || head->next == head || head->next = head->prev)
        return head;
    orig_head = head;

    /* 走訪每一個元素，用 next 暫存下一個元素 */
    for (head = head->next, next = head->next;
         head != orig_head;
         head = next, next = next->next) {
        int cmp_result =
            (head->next != orig_head) && (head->val != next->value);
        /* 若與下一個元素重複值，或前一個元素為重複值元素 */
        if (cmp_result || found_dup) {
            /* 移除 head */
            head->prev->next = next;
            next->prev = head->prev;
            /* 紀錄是否為重複值元素 */
            found_dup = cmp_result;
        }
    }
    return orig_head;
}

測驗 3 LeetCode - LRU Cache

在 cache 上的管理，因為空間是有限的，所以我們會希望有方法可以符合需求和效率，知道哪些 cache 該留，哪些該捨棄。而 Least Recently Used, LRU 為其中一種，若某一個 cache 很久沒有使用了，那可能之後也不會再使用了。

結構宣告

從結構上看來， LRUCache 有一個湊雜表 hheads 和一個雙向陣列結構的開頭 dhead ，有 cache 的上限數量 capacity 和已使用的數量 count 。而 LRUNode 則是 cache 的單元，包括拿來湊雜搜尋用的 key 和 cache 儲存的內容 value ，還有分別對應 hheads 和 dhead 用的元素 hlink, dlink ，其連結方式如上圖。

typedef struct {
    int capacity, count;             
    struct list_head dhead, hheads[];
} LRUCache;
    
typedef struct {
    int key, value;
    struct list_head hlink, dlink;
} LRUNode;

建立與移除 cache

給定 cache 得容量 capacity ，然後依照其值配置對應的記憶體。最初還沒有使用 cache ，所以 count 會是零， dhead, hheads 分別指向自己，代表還是空的。

LRUCache *lRUCacheCreate(int capacity)
{   
    LRUCache *obj = malloc(sizeof(*obj) + capacity * sizeof(struct list_head));
    obj->count = 0;
    obj->capacity = capacity;
    INIT_LIST_HEAD(&obj->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_LIST_HEAD(&obj->hheads[i]);
    return obj;
}
    
void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}

從結構上來看，要移除 cache LRUCache 需要先移除其元素 LRUNode ，其連接方式有兩種，若要找到所有元素最快的方法是從 dhead 遍歷。而 dhead 與 dlink 相連，利用 list_entry 可以找到對應的 LRUNode ，且我們會移除 dlink ，所以 MMM1 要使用 list_for_each_entry_safe 。

讀取 cache

當要讀取某特定的 cache 的時候，需要給該 cache 的 key 值，使用湊雜表快速搜尋該 cache 的位置，找到則回傳 cache 儲存的內容 value ，否則回傳

$-1$ 。過程中因為要使用 LRU 方法，所以會需要排列雙向鍊結結構的順序，

int lRUCacheGet(LRUCache *obj, int key)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM2 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            return lru->value;
        }
    }
    return -1;
}

找到 bucket 位置，然後遍歷該 bucket ，依照 LRU 的規則，遍歷方向是 next 的方向。遍歷的變數是 lru ，型態為 LRUNode ，加上只要查看，沒有要移除節點，所以 MMM2 應該為 list_for_each_entry 。

存入 cache

輸入資料 value 和對應的 key 值，將這些內容存入或更新對應 key 值的 cache 的元素 LRUNode 。但是就如剛才所提的，這些元素是有限的，所以當我們是存入（沒有對應 key 值的 cache 元素），遇到已使用的元素數量 count 到達上限 capacity 時，我們需要利用 LRU 的規則，把最久沒有使用的 cache 元素給移除，然後再插入新的元素。而如果是更新，那只需要移動其元素在雙向鍊結結構裡的位置，以符合 LRU 要求。

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *lru;
    int hash = key % obj->capacity;
    MMM3 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

    if (obj->count == obj->capacity) {
        lru = MMM4(&obj->dhead, LRUNode, dlink);
        list_del(&lru->dlink);
        list_del(&lru->hlink);
    } else {
        lru = malloc(sizeof(LRUNode));
        obj->count++;
    }
    lru->key = key;
    list_add(&lru->dlink, &obj->dhead);
    list_add(&lru->hlink, &obj->hheads[hash]);
    lru->value = value;
}

就上述所說， MMM3 的區塊是更新元素的區塊，所以會遍歷對應 bucket 裡的元素，依照 LRU 規則，方向為 next 。而 lru 為 LRUNode 結構，移動完元素位置後就停止遍歷，所以 MMM3 為 list_for_each_entry 。

而下一個區塊會檢查 count 與 capacity ，可以知道是要存入元素。而如果相同，根據 LRU 的規則，那就要先移除最久沒有使用的元素，在雙向鍊結結構的末尾，所以 MMM4 應該為 list_last_entry 。移除後將要存入的資料更新上去，然後在加回到 lRUCache 中。

延伸問題：

1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 在 Linux 核心找出 LRU 相關程式碼並探討

測驗 4 LeetCode - Longest Consecutive Sequence

給定一未排序陣列，找出最長連續數列的長度，比如 1-2-5-3-7-8 ，最長連續數列為 1-2-3 ，所以長度是 3 。此處使用湊雜表，在建立完湊雜表（時間複雜度

$O(n)$ ）後，要搜尋數列下一個元素的時間複雜度變為

$O(1)$ ，總時間複雜度為

$O(n)$ 。

結構宣告

此為湊雜表的元素， num 是陣列的某一位置的數值， link 是與湊雜表和湊雜表元素連結的成員。

struct seq_node {
    int num;
    struct list_head link;
};

湊雜表元素搜尋

搜尋湊雜表元素，湊砸函數使用到陣列的數值 num 和大小 size ，得到湊雜值 hash 後在對應的 bucket 裡（ heads[hash] ）找尋元素，找到則回傳該指標，否則回傳 NULL 。

static struct seq_node *find(int num, int size, struct list_head *heads)
{   
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

主函式

首先先建立湊雜表，並將陣列數值放入湊雜表中。在來依序取陣列的數值，找尋包含該數值之最長連續數列長度 len ，若找到的長度比 length 更長，則更新最終最長長度 length 。

int longestConsecutive(int *nums, int n_size)
{
    int hash, length = 0;
    struct seq_node *node;
    struct list_head *heads = malloc(n_size * sizeof(*heads));

    /* 初始化湊雜表 */
    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    /* 將陣列的數值放進去，重複的數值略過 */
    for (int i = 0; i < n_size; i++) {
        if (!find(nums[i], n_size, heads)) {
            hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
            node = malloc(sizeof(*node));
            node->num = nums[i];
            list_add(&node->link, &heads[hash]);
        }
    }

    /* 依序取陣列的數值，找尋包含該數值最長連續數列長度
     * 若找到長度比 length 更長，則更新 length
     * 在找尋的過程中，造訪過得元素會被移除，可以避免無謂的重複找尋 */
    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int num;
        node = find(nums[i], n_size, heads);
        while (node) {
            len++;
            num = node->num;
            list_del(&node->link);

            int left = num, right = num;
            while ((node = find(LLL, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            while ((node = find(RRR, n_size, heads))) {
                len++;
                list_del(&node->link);
            }

            length = len > length ? len : length;
        }
    }

    return length;
}

兩個填空 LLL, RRR 剛好是在對稱的位置上，從第 31 行看到 node 被移除，也就是 num 已經造訪過了，之後應該要往數值的兩邊作找尋，也就是第 34, 39 行。從第 33 行得知 left 與 right 是 num ，所以兩填空應該要為 --left 與 ++right 才會進入迴圈。

延伸問題：

1. 解釋上述程式碼的運作，撰寫完整的測試程式，指出其中可改進之處並實作
2. 嘗試用 Linux 核心風格的 hash table 重新實作上述程式碼

使用 Linux 核心風格的 hash table 改寫

在 Linux 裡湊雜表元素是使用 sturct hlist_node ，這裡替換原本的 struct list_head 。

struct seq_node {
    int num;
    struct hlist_node link;
};

在 Linux 裡的湊雜函數是使用 Fibonacci hasing ，輸入一個 key 然後得到 bucket 的位置，這裡我們直接使用 num 當 key 值。 hash_for_each_possible 會遍歷對應 key 值的 bucket ，這裡替換原本的 list_for_each_entry 和 hash 計算。

static struct seq_node *find(int num, struct hlist_head *heads)
{
    struct seq_node *node;
    /* use nums[i] as key directly */
    hash_for_each_possible (heads, node, link, num) {
        if (num == node->num)
            return node;
    }
    return NULL;
}

最後是主函式，需要建立一個空湊雜表，原本是用迴圈和 INIT_LIST_HEAD 初始化，在 Linux 裡則是有 __hash_init 可以使用，其湊雜表的大小固定為

$2$ 的冪，所以要先算一下湊雜表的大小，至少是大於 n_size 的。補充說明一下，為何不用 HASH_SIZE 巨集，因為我們要使用動態配置記憶，這樣導致 heads 不是陣列，所以無法使用。另外因為同樣的理由，沒有使用 hash_init 和 DEFINE_HASHTABLE 。

int longestConsecutive(int *nums, int n_size)
{
    int length = 0, bits = 4, ht_size;
    struct seq_node *node;
    struct hlist_head *heads;

    /* hashtable with size 2^bits */
    while (n_size > (1 << bits))
        ++bits;
    ht_size = 1 << bits;
    heads = malloc(sizeof(struct hlist_head) * ht_size);
    __hash_init(heads, ht_size);
    

    for (int i = 0; i < n_size; ++i) {
        /* if not found, create and add it in */
        if (!find(nums[i], heads)) {
            node = malloc(sizeof(struct seq_node));
            node->num = nums[i];
            /* use nums[i] as key directly */
            hash_add(heads, &node->link, nums[i]);
        }
    }

    for (int i = 0; i < n_size; ++i) {
        int num, len = 0;
        node = find(nums[i], heads);
        while (node) {
            ++len;
            num = node->num;
            hash_del(&node->link);

            int left = num, right = num;
            /* search leftward */
            while (node = find(--left, heads)) {
                ++len;
                hash_del(&node->link);
            }

            /* search rightward */
            while (node = find(++right, heads)) {
                ++len;
                hash_del(&node->link);
            }
            length = len > length ? len : length;
        }
    }

    return length;
}

剩下的部份有兩個函式有替換，第一個是 list_add 插入湊雜表元素，這裡換為 hash_add ，不一樣的地方是要多輸入 key 值，也就是他會在裡面算對應的 bucket 位置。而另一個函式是 list_del ，利用雙向連結結構， hash_del 一樣只需要輸入要移除的元素即可。