Try   HackMD

2022q1 Homework1 (quiz1)

contributed by < blueskyson >

題目連結

測驗 1

給定一個陣列 nums 和一個目標值 target，求找到 nums 的 2 個元素相加會等於 target 的索引值。題目確保必為單一解，且回傳索引的順序沒差異。例如給定輸入 nums = [2, 7, 11, 15], target = 9，相加變成 9 的元素僅有 2 及 7，因此回傳這二個元素的索引值 [0, 1]。

考慮以下 C 語言實作:

#include <stdlib.h>
static int cmp(const void *lhs, const void *rhs) {
    if (*(int *) lhs == *(int *) rhs)
        return 0;
    return *(int *) lhs < *(int *) rhs ? -1 : 1;
}

static int *alloc_wrapper(int a, int b, int *returnSize) {
    *returnSize = 2;
    int *res = (int *) malloc(sizeof(int) * 2);
    res[0] = a, res[1] = b;
    return res;
}

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    *returnSize = 2;
    int arr[numsSize][2];  /* {value, index} pair */
    for (int i = 0; i < numsSize; ++i) {
        arr[i][0] = nums[i];
        arr[i][1] = i;
    }
    qsort(arr, numsSize, sizeof(arr[0]), cmp);
    for (int i = 0, j = numsSize - 1; i < j; ) {
        if (arr[i][0] + arr[j][0] == target)
            return alloc_wrapper(arr[i][1], arr[j][1], returnSize);
        if (arr[i][0] + arr[j][0] < target)
            ++i;
        else
            --j;
    }
    *returnSize = 0;
    return NULL;
}

若用暴力法，時間複雜度為

O(n2)，顯然不符合期待。我們可改用 hash table (以下簡稱 HT) 記錄缺少的那一個值 (即 target - nums[i]) 和對應的索引。考慮以下案例 nums = [2, 11, 7, 15]：

  1. nums[0] 是 2，HT[2] 不存在，於是建立 HT[9 - 2] = 0
  2. nums[1] 是 11，HT[11] 不存在，於是建立 HT[9 - 11] = 1
  3. nums[2] 是 7，HT[7] 存在 (設定於步驟 1)，於是回傳 [2, HT[7]] = [2, 0]

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 →

hlist 用於 hash table 的實作，它的資料結構定義在 include/linux/types.h 中:

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

示意如下：

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 →

hlist 的操作與 list 一樣定義於 include/linux/list.h，以 hlist_ 開頭。hlist_head 和 hlist_node 用於 hash table 中 bucket 的實作，具有相同 hash value 的節點會放在同一條 hlist 中。 為了節省空間，hlist_head 只使用一個 first 指標指向 hlist_node，沒有指向串列尾節點的指標。

hash table 主要是由一個 hlist_head 的動態陣列所構成，每個 entry 指向一個由 struct hlist_node 構成的非環狀 doubly linked list，hash table 長度依照 bits 給定，可知大小為 2 的冪。

而可以發現 struct hlist_head 只有一個 struct hlist_node * 的成員; 而 struct hlist_node 型態卻包含一個 struct hlist_node * 及 struct hlist_node ** ，其中一個原因為 hash table 指向的為非環狀的 linked list ，因此只需指向 list 的一端點，若單純使用 struct hlist_node 當作 head ，無用的 “pprev” 會造成大量的記憶體空間浪費，因此將 head 與 node 分開來實做。

而 struct hlist_node 中的 pprev 為何使用「指標的指標」而非「指標」？ 回答這個問題前可以先參考 Linux 原始碼中 type.h：












struct list_head {
	struct list_head *next, *prev;
};

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

可知在 type.h 中有兩種 list 的結構：

struct list_head 在 Linux 中實作為環狀 doubly-linked list，且可以在行程管理 (process scheduling) 的相關實做上看到，如 sched.h 中有近 20 處使用到此結構，因可快速存取到頭以及尾的節點（時間複雜度

O(1) 故有較好的效能，適用於行程管理這種對時間要求嚴謹的部分做使用。

struct hlist_head 搭配 hlist_node。在 Linux 核心中專門為了 hash table 而使用，hlist_head 的設計也省去了 list 起始端 pprev 的存放空間、在初始狀態就省去了一半的記憶體容量。而且同時 hash table 不會特別需要存取到 list 的尾端，並且走訪 list 相對沒那麼講求效率（因為 hash 的設計理念就是講求 hash collision rate 要低、因此一個 list 若太長比較需要改進的為 hash function 的設計而非改進整個資料結構）。綜合上述所說單向 list 已滿足 hash table 的需求。

pprev 為何是「指標的指標」？ 若和 list_head 一樣使用單純的指標( hlist_node *)，則考慮到 list 有方向性，delete node 時需要額外檢查其是否為 list 的 head 或是 NULL 等等，有較冗餘的程式碼必須實做，因此使用 hlist_node **pprev 直接存取上一個 node 所在的位址。Linux 為求程式碼簡潔故以 pointer to pointer 的方式用 pprev 直接指向前一個元素的記憶體位址本身。

以下是引入 hash table 的實作，學習 Linux 核心程式碼風格:

#include <stddef.h>
#include <stdlib.h>

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)

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

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

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

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

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

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

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

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

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

解題

觀察 AAA 下方的

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

可以推論 n 會成為該 list 的第一個 node，讓原本的第一個 node 變成第二個。把執行 AAA 前的狀況概括成以下圖示：







g2



1

pprev

next



2

pprev

next



1:ref->2:val





3

...



2:ref->3:val





4

pprev

next



head

 

first



head->1





n
n



n->4:val





h
h



h->head





first
first



first->1:n

我們的目的是讓 h->first 指向 n、把 n->next 指向當前的 first、把 first 的 pprev 更新為 &n->next、把 n->pprev 指向 &head->first。因此得到 AAA 為 n->next = first;，BBB 為 n->pprev = &h->first;。

解釋上述程式碼運作原理

  • map_init: 根據傳入的 bits 來 malloc 長度為
    2bits     的 hash table entry (每個 entry 對應一個 hash 後的值)，並把所有 entry 初始化為 NULL。
  • find_key: 一開始透過 head = &(map->ht)[hash(key, map->bits)] 定位到 key 在 hash table 中對應的 entry。接下來透過 for 迴圈走訪這個 entry 底下的 list，確認該 key 是否已經存在 hash table，如果存在就回傳對應的 bucket，否則回傳 NULL。
  • map_get: 呼叫 find_key 取得 bucket，然後回傳 bucket 中儲存的 val。
  • map_add: 呼叫 find_key 檢查給定的 key 是否已經存在 hash table，若否就 malloc 一個新的 bucket 儲存 key 和 val，並將此 bucket 作為 entry 的第一個 bucket。
  • map_deinit: 釋放 hash table 的所有資源。

測驗 2

針對 LeetCode 82. Remove Duplicates from Sorted List II，以下是可能的合法 C 程式實作：

#include <stddef.h>

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

解題

因為刪除 Node 的條件為 node 的 val 重複，所以直覺的推論出 COND1 是檢查當前的 Node 的 val 是否與下個 Node 一樣，若是，就透過 while 迴圈跳過所有 val 相同的 Node，然後進入下一層遞迴。故 COND1 為 head->next && head->val == head->next->val。

在 while 迴圈中，要跳過所有重複的 Node，所以 COND2 恰好與 COND1 相同，為 head->next && head->val == head->next->val。

測驗 3

針對 LeetCode 146. LRU Cache，以下是 Least Recently Used (LRU) 可能的合法 C 程式實作：

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

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

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

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

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

解題

在 MMM1 中要走訪所有 list entry 並且 free 掉 container，所以 MMM1 為 list_for_each_entry_safe。

MMM2 和 MMM3 只是移動 Node 在 list 的位置，並沒有 free 掉把 container，用 list_for_each_entry 即可。

MMM4 待補

測驗 4

針對 LeetCode 128. Longest Consecutive Sequence，以下是可能的合法 C 程式實作：

































































#include <stdio.h>
#include <stdlib.h>
#include "list.h"

struct seq_node {
    int num;
    struct list_head link;
};                                                                                                                                                            
            
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;
}

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 迴圈中，left 與 right 的用途為以 num 為基準，在 hash table 中往左與往右尋找連續整數，並且從 hash table 中移除找到的連續數。

在上方程式碼中的第 46 行的 list_del(&node->link) 已經從 hash table 中刪除 num 了，所以在往後的 while 迴圈中應該要刪除 …, num - 1, num + 1, …，故要先增/減 right 與 left 再呼叫 find。因此 LLL 與 RRR 為 --left 與 ++right。

Last changed by 
 
Lin Cheng-Chieh
https://jacklinweb.github.io/ https://www.linkedin.com/in/blueskyson/ https://dev.to/blueskyson
0
355

Read more

2020_OS_Fall_HW3 Key Value Storage

學號： F74076027姓名： 林政傑系級： 資訊 111

Jul 27, 2024
2022q1 Homework3 (fibdrv)

contributed by &lt; blueskyson &gt;

Mar 17, 2024
學習 Ansible

Ansible 是一個容易上手的 IT 自動化引擎，可自動執行雲端配置、應用程式部署和許多其他 IT 需求。存放 yml 描述檔並執行 ansible-playbook 的機器稱為 Control Node，遠端的所有參與佈署的機器稱為 Managed Node。Ansible 這個詞起源於科幻小說 Ender’s Game 中的一種超光速通訊裝置，用來控制遠方的星際戰艦。

Sep 14, 2023
分析 .NET MVC 官方教學 MvcMovie

官方教學網址: https://docs.microsoft.com/en-us/aspnet/core/tutorials/first-mvc-app/start-mvc

Jul 17, 2023
Read more from Lin Cheng-Chieh
Published on HackMD