2022q1 Homework1 (quiz1)

contributed by < jim12312321 >

測驗題目

測驗1 ：
利用 linux kernel 風格的 hash table 實作 Leecode No.1 Two Sum

首先我們先將測驗 1 中的題目程式碼，依照函式拆程若干個部份並分別解釋。

結構宣告

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)

hlsit_node
在 hlist_node 結構中可以看到有提供兩子結構，分別為 next 和 pprev 。其中 next 是 hlist_node 的指標，所以他應該指向下一個 hlist_node ；而 pprev 是指標的指標，所以他應該指向前一個 hlist_node * ，也就是前一個 hlist_node 的指標。
hlist_head
而 hlist_head 就比較簡單了，裡面只有一個子結構 first 用以指向第一個節點。
map_t
裡面的 bits 用來初始化 hash table 的大小
MAP_HASH_SIZE
用來指定該初始化多大的雜湊表（以 2 的冪作為初始大小）

power of 2 的翻譯是「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 →

jserv

架構示意圖

hash table 初始化

map_t *map_init(int bits) {
    map_t *map = malloc(sizeof(map_t));
    if (!map)
        return NULL;

    map->bits = bits;
    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++)
            (map->ht)[i].first = NULL;
    } else {
        free(map);
        map = NULL;
    }
    return map;
}

根據 bits 的大小，將 hash table 初始化成長度為

2^{b i t s}

的 hash table 。

hash key, 一些 marco 和 hash function





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

這段程式用來描述一個 hash_key 的結構，其中 key 用來儲存對應的 hash key ， data 用來儲存資料（在這題中就是準備用來找兩數之和的數字的索引值）， hlist_node 則是用以提供各式操作的結構。





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

container_of 用以透過子結構提取上層結構

#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 利用 val * GOLDEN_RATIO_32 製造雜湊值，又因如老師在註解提到的高位較具隨機性，因此 shift 32 bits 後回傳成雜湊值。

無聊去查了一下 GOLDEN_RATIO_32 為什麼要設定成那個值，明明 1640531527 (0x61C88647 轉成 10 進位後的值) 看起來跟黃金比例沒什麼關係呀？
原來這是

2^{32} \times (1 - \frac{1}{φ})

的近似值（

φ

就是黃金比例），而且在 linux kernel 中也是用他來實作 hash 呢。
Link: linux code

TODO: 以
$L A T E X$ 語法重新排版數學表示式

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 →

jserv

取得 hash_key 中的 data

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

若 map 中存在對應的 key ，則將 hash_key 中的 data 回傳，否則回傳 NULL 。

將新的值加入 hash table

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    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;
}

首先要先找到這個 key 所對應的 hash table 位置，並設定該位置中的第一個節點

struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;

接著先做 AAA ，然後如果 first 不是 NULL ，則將該 hash 值的 linked list 做成雙向鏈結串列，之後將原先的 first 替換成 n ，最後做 BBB 。

AAA;
if (first)
    first->pprev = &n->next;
h->first = n;
BBB;

因此可以知道我們還缺乏設定新節點的 pprev 和 next

所以可知
AAA : n->next = first
BBB : n->pprev = &h->first

清除 hash table

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

    for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
        struct hlist_head *head = &map->ht[i];
        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);
}

將 hash table 中所有佔用的記憶體空間釋放

重看 Two Sum

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;
}

步驟解析：

初始化 hash table
初始化一個空間儲存要回傳的索引值
依序找尋數字陣列
3-1.
若某數字和目標之差值 target - nums[i] 已經存在於 hash table ，則將當前數字與存於 hash table 中的索引值取出，並且離開 for-loop
3-2.
若沒有找到則將當前數字，當前數字的索引值加入 hash table
釋放 hash table 所佔之記憶體除存空間並回傳找到的答案

TODO: 延伸題目2

測驗2 ：實作 LeetCode 82.

本測驗為實做 LeetCode 82 的程式碼填空
LeetCode 82 中要答題者將重複的節點全部移除

架構宣告

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

該架構裡面存有一個屬性( val 用來儲存該結點的值)和另一個架構( next 用來指向下一個 ListNode )

什麼叫做「子架構」？用語要精準

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 →

jserv

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;
}

步驟解析：

判斷陣列是否存在
1-1. 不存在則回傳 NULL
1-2. 存在則繼續 2.
判斷 COND1 有沒有發生
2-1. 若沒有則往 4.
2-2. 若有則往 3.
若 COND2 存在則 head 繼續往後移動，然後對 head->next 繼續進行一次 deleteDuplicates()
對 head->next 進行一次 deleteDuplicates() ，然後回傳 head

可知在第2點中， COND1 應該要可以判斷是否要發生重複的情況（當然重複的前提就是下個節點還存在），因此可得知

$\to$ COND1 = head->next && head->val == head->next->val

然後由於所有重複的都必須移除，因此在 COND2 終須判斷是否下下一個仍然存在且為同一個值，因此可推斷

$\to$ COND2 = head->next->next && head->next->val == head->next->next->val
但由於題目要求要最精簡程式碼，而只要將 head = head->next 就能用 COND1 的解法取代掉原本我認為的 COND2 的解法，因此可知

$\to$ COND2 = head->next && head->val == head->next->val

嘗試不用遞迴寫出 LeetCode 82

廢話不多說，先貼程式碼
















struct ListNode* deleteDuplicates(struct ListNode* head){
    struct ListNode **indirect = &head,*dup;
    while((*indirect) && (*indirect)->next){
        while((*indirect)->next && (*indirect)->val != (*indirect)->next->val)
            indirect = &(*indirect)->next;
        dup = (*indirect);
        while(dup->next && dup->val == dup->next->val)
            dup = dup->next;
        if(dup->next){
            *indirect = dup->next;
        }else if(*indirect != dup){
            *indirect = NULL;
        }        
    }    
    return head;
}

步驟解析：

判斷 *indirect (就是 head) 以及 *indrect->next 是否存在，若有其中有一者不存在，則跳出迴圈，回傳 head ；否則繼續步驟 2
當目前 node 中的值與下一個 node 中的值不相同時，則繼續走訪 list (當然也要判斷下一個 node 是否還存在)

離開步驟 2 時有兩種情況，但在步驟 3 中沒有先對這兩種情況判斷

\to

I. 下一個結點中的值與目前結點中的值不相同

\to

II. 下一個結點不存在

令 dup 為當前結點，並判斷後續 list 中有多少與之重複的值(當然也還是要判斷下一個結點是否存在)
判斷以下兩種狀況
$\to$ I. 若下一個結點存在，則表示還需繼續往後檢查且此時重複的那個節點並不是 list 中的最後一個結點，因此將 *indirect 指向 dup->next
$\to$ II. 若下一個結點不存在且 *indirect != dup (這樣的情況就代表最後一個結點與前面有相同值，需移除， e.g. [1,2,3,3]) ，則將 *indirect 指向 NULL

雜記:
這算是真正第一次自己利用a pointer of a pointer 做出題目。
還蠻開心的，不過最後還是躲不掉要進行步驟 4. 的判斷，不知道還能不能更簡化，但是目前想不到了，先這樣。

TODO: 延伸問題2

測驗3 ：實作 LeetCode 146.

本測驗為結合 lab0-c 所提供的 list.h 實作 linux 風格的 LRU Cache

題目簡述

這題希望建構一個實作一個 LRU Cache ，建構結構體 LRUCache 並提供以下函式

lRUCacheCreate(int capacity)
建立一個有大小為 capacity 的 LRU Cache
lRUCacheFree(LRUCache *obj)
將 LRU Cache 中所有空間釋放
lRUCacheGet(LRUCache *obj, int key)
搜尋 LRU Cache 中是否有指定的 key ，若有則回傳該值，沒有則回傳 -1
lRUCachePut(LRUCache *obj, int key, int value)
用特定的 key 將 value 插入 LRU Cache 中，若 key 已存在則更新 LRU Cache 中同樣 key 中的值，若沒有則將最少使用的 key 移除，再將這對 key-value pair 加入 LRU Cache 。

架構宣告









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

LRUCache
- capacity: 用以紀錄 LRU Cache 中有多少 hhead 的儲存空間
- count: 用以記錄目前 LRU Cache 中有多少 hlink
- dhead: 用以紀錄 key 之間最近一次被使用次序的 linked list 的 head
- hheads: 用以紀錄不同 hash 值的 linked list 的 head
LRUNode
- key: 用以紀錄結點中的 key
- value: 用以紀錄結點中的 value
- dlink: 加在 dhead 後的 linked list 結點，排序排在越前面代表越近期被使用
- hlink: 加在 hhead 後的 linked list 結點，會依照 key 值所分配到的 hash 值加在對應的 hhead 後。

e.g.

建置新的 LRU Cache

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;
}

初始化新的 LRU Cache 並為其配置記憶體空間，配置好的新結點 (list_head) 也要進行初始化，將其變成雙向鏈結 linked list 。

釋放 LRU Cache 所佔據的記憶體空間









void lRUCacheFree(LRUCache *obj)
{       
    LRUNode *lru, *n;
    MMM1 (lru, n, &obj->dhead, dlink) {
        list_del(&lru->dlink);
        free(lru);
    }
    free(obj); 
}

釋放架構空間時要走訪所有結點並逐一釋放，最終再釋放 Cache 本身。
因為要走訪 linked list 中所有結點且在這個過程中要釋放該結點，因此我們可以知道必須使用 safe 模式的 linked list 走訪

\to

MMM1 = list_for_each_entry_safe

取得 Cache 中的特定值












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;
}

依照特定的 hash 值走訪 Cache 中相對應的 hheads[hash] 並將該結點移到 dhead 的第一個結點。

e.g. 找 key2

將 Node2 的 dlink 移到 dhead 的最前面。

因為要走訪 linked list 中所有結點但不需要在這個過程中釋放該結點，因此可以不用使用 safe 模式的 linked list 走訪

\to

MMM2 = list_for_each_entry

將特定的值依據 key 放進 Cache

























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;
}

依照特定的 key 放進 Cache 中。若該 key 已經存在，則更新 key 中的值並返回。若不存在則將最沒被使用的值移除 (dhead 中的最後一個結點)並將新結點放進對應的 hheads[hash] 中與 dhead 中的第一個。

e.g. put(key3,value3)

將最沒有被使用的 Node 移除。

在 MMM3 所在的那一段中，需要走訪對應 hash 的 linked list(hheads[hash]) 並尋找 key 是否已經存在。

因此我們可以知道需要走訪 linked list 並且不需要在這個過程中移除結點，因此可以使用非 safe 的走訪版本

\to

MMM3 = list_for_each_entry

在 MMM4 所在的那一段中，需要走訪對應 hash 的 linked list(hheads[hash]) 的最後一個結點並將其移除。

因此我們可以知道需要走訪 linked list 中的最後一個結點

\to

MMM4 = list_last_entry

TODO: 延伸問題 1 中的改進與測試、2

測驗4：實作 LeetCode 128.

本測驗為結合 lab0-c 所提供的 list.h 實作 linux 風格的 Find Longest Consecutive Sequence

題目簡述

在一個未被排序過的 array 中尋找最長的連續序列( e.g. [1,2,3]

\to

連續序列)

架構宣告




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

seq_node
- num: 紀錄該結點中的數值
- link: 該結點中用以形成 linked list 的架構

尋找特定值










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;
}

在 linked list 中尋找特定的 num 若存在就回傳他所在的結點，若無則回傳 NULL。

找最長的連續序列












































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]);
        }
    }

    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;
}

步驟解析:

根據 n_size 設立一個 heads 並初始化其中所有 head
走訪 nums 中的所有值，並且如果該值並未在 heads 中的任一 head 找到，就將該值新增進對應的 head
走訪 nums 中的所有值，並且尋找該值在 heads 中有沒有形成連續序列，首先先往當前的 head 的左側(較小側)走訪，若遇到不連續則終止。接著對右邊也進行相同的事情，最後存取當前找到最長的長度

我們可以知道在 LLL 中，應該要往當前數值的左側(比當前數值還小的那側)走訪，且應該先 -1 (因為 left = num)

\to

LLL = --left

我們可以知道在 RRR 中，應該要往當前數值的右側(比當前數值還大的那側)走訪，且應該先 +1 (因為 right = num)

\to

RRR = ++right

TODO: 延伸問題 1 中的改進與測試、2

2022q1 Homework1 (quiz1)

測驗1 ： 利用 linux kernel 風格的 hash table 實作 Leecode No.1 Two Sum

結構宣告

hash table 初始化

hash key, 一些 marco 和 hash function

取得 hash_key 中的 data

將新的值加入 hash table

清除 hash table

重看 Two Sum

測驗2 ： 實作 LeetCode 82.

架構宣告

嘗試不用遞迴寫出 LeetCode 82

測驗3 ： 實作 LeetCode 146.

題目簡述

架構宣告

建置新的 LRU Cache

釋放 LRU Cache 所佔據的記憶體空間

取得 Cache 中的特定值

將特定的值依據 key 放進 Cache

測驗4： 實作 LeetCode 128.

題目簡述

架構宣告

尋找特定值

找最長的連續序列

測驗1 ：
利用 linux kernel 風格的 hash table 實作 Leecode No.1 Two Sum

測驗2 ：實作 LeetCode 82.

測驗3 ：實作 LeetCode 146.

測驗4：實作 LeetCode 128.