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 的冪」，不是「冪次」

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^{bits}$ 的 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}{\phi })$ 的近似值 （

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

TODO: 以

$LATEX$ 語法重新排版數學表示式
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;
}

步驟解析：

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

TODO: 延伸題目2

---

測驗2 ： 實作 LeetCode 82.

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

架構宣告

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

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

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

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-1. 不存在則回傳 NULL
   1-2. 存在則繼續 2.
2. 判斷 COND1 有沒有發生
   2-1. 若沒有則往 4.
   2-2. 若有則往 3.
3. 若 COND2 存在則 head 繼續往後移動，然後對 head->next 繼續進行一次 deleteDuplicates()
4. 對 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;
}

步驟解析：

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

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

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

$\to$ II. 下一個結點不存在

3. 令 dup 為當前結點，並判斷後續 list 中有多少與之重複的值(當然也還是要判斷下一個結點是否存在)
4. 判斷以下兩種狀況
   
   $\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;
}

步驟解析:

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

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

$\to$ LLL = --left

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

$\to$ RRR = ++right

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