Try   HackMD

2022q1 Homework1 (quiz1)

contributed by < Chao-Shun-Cheng >

測驗 1

程式碼解釋

map_init

map_init 會建立

2n 個大小的雜湊表，如下圖所示。其中 ht 會指向 2^n * sizeof(struct hlist_head) 的連續記憶體空間。







feature



struct0

map



struct1

bits

ht



struct0->struct1:bits





struct2

first

first

first

...

first



struct1:ht->struct2:one






















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

首先第七行用 malloc 建立 hashtable 所需要的連續記憶體空間，空間大小為

2b 個 sizeof(struct hlist_head)

map->ht = malloc(sizeof(struct hlist_head) * MAP_HASH_SIZE(map->bits));

再來就是進行初始化的部分，使得 hashtalbe 都沒指向任何內容。



for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++)
    (map->ht)[i].first = NULL;

find_key

find_key 有兩個輸入參數，分別是 map 跟 key ，會從 map 去尋找有沒有符合的 key ，有找到就會回傳對應的 hash_key ，否則就回傳 NULL。










static struct hash_key *find_key(map_t *map, int key) {
    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];
    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;
}

首先可以看到第二行，hash 是雜湊函式，會利用 key 去找到 hash table 中對應的 hlist_head

    struct hlist_head *head = &(map->ht)[hash(key, map->bits)];

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

不同的 key 經過雜湊函式計算後可能得到同樣的結果，所以會在用一個 for 迴圈去看每個結果的 key 是不是跟 input 的 key 一樣，一樣的話就代表有找到，會回傳找到的 hash_key。第三到第七行就是在進行這個功能。






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

其中 container_of 可以從一個結構體中的每個成員，去得到結構體的最前面的地址，詳細可以參考Linux 核心原始程式碼巨集: container_of

map_get

map_get 搭配 find_key 去使用，目的是用來查看是否已經存在。






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

map_add

map_add 會將資料存進 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 當中，就不用再加進去 hash_table。




    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

如果找不到則會利用 malloc 分配一個 hash_key 的空間，並且初始化。



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

接著利用雜湊函式 hash 找出要放置在 hash_table 的位置，並用 h 指著 hlist_head。另外 n 指向剛剛建立的 hash_key 當中的 node 、first 則指向 h 當中的第一個 node。



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

緊接著要將剛剛建立的 node 插入進 list 的頭，以下是對應的操作。n->next 要指向原本的 first ，所以 AAA 是 n->next = first ；再來要去要去看原本到底有沒有 first ，如果本來有，則要調整原本 first 的 pprev (13、14 行)；最後要將插入的 node 的 pprev 指回去 list ，所以 BBB 是 n->pprev = &h->first。






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

twoSum

twoSum 利用上面所建立的 hash table 的操作來進行實作。


























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

首先利用 map_init 初始化 map 所需要的空間 (第 3 行)，以及用 malloc 建立回傳答案所需要的空間 (第 5 行)。




    map_t *map = map_init(10);
    *returnSize = 0;
    int *ret = malloc(sizeof(int) * 2);

接下來是利用一個 for 迴圈去建立 hash_table 與查找 key。如果 key 可以從 hash table 中找到就回傳答案，如果找不到，就將 key 加進去 hash_table 當中。













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

hash table 如何使用在 twoSum 可以參考 2022q1 第 1 週測驗題之說明。

測驗 2

程式碼解釋

deleteDuplicates

deleteDuplicates 要可以將所以重複出現的 Node 都 delete 掉，以下是實作方式。
















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

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

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

首先可以注意到我們需要去比較下一個 node 與現在的 node 是不是一樣的值，所以要先確定有下一個 node ，再去看下一個 node 的值，因此 COND1 就會是 head->next && head->val == head->next->val ；緊接著可以看到有提示 /* Remove all duplicate numbers */ ，因此可以知道 while 迴圈會去把相同的 node 都 delete 掉。因此 while 的條件就會是要有下一個 node 並且值是一樣的，因此 COND2 就是 head->next && head->val == head->next->val。

測驗 3

程式碼解釋

lRUCacheCreate

lRUCacheCreate 會依據 capacity 的大小，建立出相對應的空間，並且將 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;
}

其中在第三行的 sizeof(*obj) 其實與 sizeof(LRUCache) 是一樣的。

lRUCacheFree

lRUCacheFree 會將 obj->dhead 之所有 Node 給釋放掉。因此 MM1 會是 list_for_each_entry_safe 用來去歷遍所有的 Node entry。










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

lRUCacheGet

lRUCacheGet 會利用 key 去看目前的 hheads 當中有無一樣的 key ，如果有就代表有存在 cache 當中。因此 MM2 是要用來歷遍 bucket 的，所以會是 list_for_each_entry。













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

lRUCachePut

lRUCachePut 可以分成三個部分，首先是已經存在 cache 當中，要把 node 更新到 list 最前面；再來就是如果 cache 容量已經滿了，要把最舊的 node 移除，並且放進新的 node；最後就是還有空間，可以直接放進去新的 node。


























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

可以發現這邊就是要找尋是不是已經在 cache 當中，因此要歷遍 bucket 去看有沒有符合的 key。因此 MM3 是 list_for_each_entry。假如有找到就會進行第七行，將這個 node 移至 list 最前方。








    MMM3 (lru, &obj->hheads[hash], hlink) {
        if (lru->key == key) {
            list_move(&lru->dlink, &obj->dhead);
            lru->value = value;
            return;
        }
    }

這邊則是判斷還有沒有容量，假如容量不夠，就要移除最舊的 node，所以 MM4 會是 list_last_entry ，用來移除 list 中最後面的 node。









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

測驗 4

程式碼解釋

find

find 會去從 bucket 當中去尋找是否有對應的數字 num。











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

longestConsecutive

longestConsecutive 是利用 hash table 將資料先分成不同 bucket 再找出最長的連續數字。













































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

首先看到這個 for 迴圈，會把每個數字經過 hash fuction 計算後，放進對應的 bucket 當中。









    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 迴圈去看每個 node。第 23 ~ 26 行會把 node 的 num 提出來並且移出 bucket；緊接在再往 num + 1 與 num - 1 去尋找是否有對應的 node，有的話就繼續找，直到不連續為止。因此可以得知 LLL 是 --num 而 RRR 是 ++num。
























    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;
        }
    }
Last changed by 
 
Kenny Cheng
Linux Kernel Develop | Android Performance Tuning | BSP System Debugging | ARMv8 | RISC-V
0
204
Published on HackMD