2024q1 Homework2 (quiz1+2)

contributed by<Terry7Wei7>

第一週測驗題

測驗一

解析 Optimized QuickSort — C Implementation (Non-Recursive)

運作原理

選擇樞軸（Pivot）： 一開始，從待排序的數組中選擇一個元素作為樞軸。這個枢軸的選擇可以是隨機的、固定的，或者使用一些特殊的選擇方法。在這個實現中，它選擇了待排序數組的第一個元素。

分割（Partition）： 將數組中的元素分為兩部分，使得樞軸左邊的元素都小於或等於樞軸，右邊的元素都大於或等於樞軸。這是通過左右兩個指針（L和R）的移動實現的，左指針找到一個大於樞軸的元素，右指針找到一個小於樞軸的元素，然後這兩個元素進行交換，重複這個過程直到左右指針相遇。

遞迴： 接下來，分別對樞軸左右兩邊的子數組遞迴地應用相同的排序過程。這就是快速排序的分治策略，將原始問題分解為兩個較小的子問題，然後遞迴解決它們。

結束條件： 遞迴過程中，如果子數組的大小變得足夠小（通常是只有一個元素或沒有元素），則遞迴結束。這時子數組視為已經排序。

繼續遞迴： 遞迴完成後，將所有子數組的結果合併起來，即可得到完全排序的數組。

這個實現中使用了一個額外的數組（beg 和 end）來跟踪每個子數組的起始和結束位置，而不是使用遞迴調用。這樣可以避免函數調用的開銷，並且沒有使用堆疊，這是一個非常基本但高效的實現方式。總的來說，快速排序是一種高效的排序算法，平均時間複雜度為O(n log n)。

改進方法

將節點添加到左邊或右邊時，需要確定左右子鏈表的尾節點。

程式碼

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;

            while (p) {
                node_t *n = p;
                p = n->next; // 補全部分
                list_add(n->value > value ? &right : &left, n);
            }

            // 找到左右子鏈表的尾節點
            node_t *left_tail = list_tail(&left);
            node_t *right_tail = list_tail(&right);

            begin[i] = left;
            end[i] = left_tail; // 更新左子鏈表的尾節點
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = right_tail; // 更新右子鏈表的尾節點

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

使用 Linux 核心風格的 List API 改寫快速排序

隨機選擇 pivot。
使用三值中值分割法（median-of-three partitioning），即在每次分割前，從子序列的頭、尾和中間選擇三個元素，並選擇其中值作為 pivot，以確保 pivot 能夠接近序列的中間值，從而更好地分割序列。

程式碼

// 隨機選擇 pivot
static inline struct node *random_pivot(struct list_head *head)
{
    int length = 0;
    struct list_head *pos;
    list_for_each(pos, head)
    {
        length++;
    }
    int pivot_index = rand() % length;
    struct node *pivot_node = NULL;
    int i = 0;
    list_for_each(pos, head)
    {
        if (i == pivot_index)
        {
            pivot_node = list_entry(pos, struct node, list);
            break;
        }
        i++;
    }
    return pivot_node;
}

// 三值中值分割法選擇 pivot
static inline struct node *median_of_three(struct list_head *head)
{
    struct node *first = list_first_entry(head, struct node, list);
    struct node *last = list_last_entry(head, struct node, list);
    int size = list_length(head);
    int middle_index = size / 2;
    struct node *middle = NULL;
    struct node *middle_node = NULL;

    struct list_head *pos;
    int i = 0;
    list_for_each(pos, head)
    {
        if (i == middle_index)
        {
            middle_node = list_entry(pos, struct node, list);
            middle = middle_node;
            break;
        }
        i++;
    }

    if (first->value <= middle->value && middle->value <= last->value)
        return middle_node;
    else if (first->value <= last->value && last->value <= middle->value)
        return last;
    else
        return first;
}

// 帶有改進策略的快速排序實現
void improved_quick_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head)) // 如果鏈結串列為空或只有一個節點，則已經排序好了
        return;

    // 隨機選擇 pivot
    struct node *pivot_node = random_pivot(head);

    // 三值中值分割法選擇 pivot
    // struct node *pivot_node = median_of_three(head);

    int pivot_value = pivot_node->value;

    // 初始化左右子串列
    struct list_head left, right;
    INIT_LIST_HEAD(&left);
    INIT_LIST_HEAD(&right);

    // 分割鏈結串列為左右兩部分
    struct list_head *pos, *tmp;
    list_for_each_safe(pos, tmp, head)
    {
        struct node *current_node = list_entry(pos, struct node, list);
        if (current_node->value < pivot_value)
            list_move_tail(pos, &left); // 將節點移動到左子串列
        else
            list_move_tail(pos, &right); // 將節點移動到右子串列
    }

    // 遞迴地對左右子串列進行快速排序
    improved_quick_sort(&left);
    improved_quick_sort(&right);

    // 將左子串列、pivot 節點和右子串列連接起來
    list_splice_tail(&right, head);
    list_splice_tail(&left, head);
}

測驗二

解析Timsort

運作原理

改進方法

---

第二週測驗題

測驗一

解析LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

原理解釋

struct hlist_node：這是一個雜湊表節點結構，它包含指向下一個節點的指標 next，以及指向前一個節點的指標 pprev。
struct hlist_head：這是一個雜湊表頭結構，它包含指向第一個節點的指標 first。
INIT_HLIST_HEAD 函數用於初始化雜湊表頭結構，將 first 指標設置為 NULL，表示鏈表為空。
hlist_add_head 函數用於將節點添加到雜湊表中。它將新節點插入到雜湊表的頭部，即 first 指標指向新節點，並更新新節點的 next 和 pprev 指標，以及原來頭部節點的 pprev 指標。
find 函數用於在給定雜湊表中查找特定值的節點索引。它使用雜湊函數計算值的雜湊值，並遍歷對應雜湊槽中的節點，直到找到值相等的節點，然後返回該節點的索引。如果未找到，則返回 -1。
dfs 函數是一個遞歸函數，用於根據前序遍歷和中序遍歷序列建立二元樹。它首先創建當前根節點，然後根據根節點在中序遍歷序列中的位置，遞歸建立左子樹和右子樹，並將其連接到根節點上。
node_add 函數用於創建並添加一個新節點到雜湊表中。它首先分配內存以存儲新節點，然後計算節點值的雜湊值，並將新節點添加到雜湊表的對應槽中。
buildTree 函數是入口函數，用於初始化雜湊表並調用深度優先搜索函數 dfs 來建立二元樹。

實作測試程式

使用指標而不是索引：在哈希表中查找值時，可以將哈希表的頭指標直接傳遞給 find 函數，而不是傳遞整個哈希表。這樣可以減少參數傳遞的開銷。

釋放節點內存：在構建樹的過程中，應該在適當的時候釋放節點的內存，避免內存泄漏。

錯誤處理：在節點添加到哈希表時，應該檢查內存分配是否成功，並在失敗時進行適當的錯誤處理。

簡化節點結構：可以簡化 order_node 結構，不需要存儲值的索引，因為在構建樹的過程中索引已經不再需要

程式碼

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

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) - (size_t) & (((type *) 0)->member)))

#define list_entry(ptr, type, member) container_of(ptr, type, member)

#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos; pos = pos->next)

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

static inline void INIT_HLIST_HEAD(struct hlist_head *h)
{
    h->first = NULL;
}

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first;
    n->pprev = &h->first;
    h->first = n;
}

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};

struct order_node {
    struct hlist_node node;
    int val;
};

static struct order_node *find(int num, struct hlist_head *heads, int size)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each(p, &heads[hash]) {
        struct order_node *on = container_of(p, struct order_node, node);
        if (num == on->val)
            return on;
    }
    return NULL;
}

static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    struct order_node *on = find(preorder[pre_low], in_heads, size);
    int idx = on->val;
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}

static inline void node_add(int val,
                            struct hlist_head *heads,
                            int size)
{
    struct order_node *on = malloc(sizeof(*on));
    if (!on) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    on->val = val;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &heads[hash]);
}

static struct TreeNode *buildTree(int *preorder,
                                  int preorderSize,
                                  int *inorder,
                                  int inorderSize)
{
    struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
    if (!in_heads) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < inorderSize; i++)
        INIT_HLIST_HEAD(&in_heads[i]);
    for (int i = 0; i < inorderSize; i++)
        node_add(inorder[i], in_heads, inorderSize);

    struct TreeNode *root = dfs(preorder, 0, preorderSize - 1, inorder, 0,
                                inorderSize - 1, in_heads, inorderSize);

    // 釋放哈希表分配的內存
    free(in_heads);

    return root;
}

void inorderTraversal(struct TreeNode *root)
{
    if (root == NULL)
        return;

    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main()
{
    int preorder[] = {3, 9, 20, 15, 7};
    int inorder[] = {9, 3, 15, 20, 7};
    int preorderSize = sizeof(preorder) / sizeof(preorder[0]);
    int inorderSize = sizeof(inorder) / sizeof(inorder[0]);

    struct TreeNode *root = buildTree(preorder, preorderSize, inorder,
                                      inorderSize);

    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

測驗二

LeetCode 146. LRU Cache

原理解釋

結構定義：

struct hlist_node 和 struct hlist_head：這些結構定義了雜湊表的節點和表頭。
struct list_head：這是一個雙向鏈表的結構。
初始化函數：

INIT_HLIST_HEAD 和 INIT_LIST_HEAD 函數用於初始化雜湊表和鏈表的表頭。
添加函數：

hlist_add_head 函數用於將節點添加到雜湊表中。
list_add 函數用於將節點添加到鏈表中。
刪除函數：

hlist_del 函數用於從雜湊表中刪除節點。
list_del 函數用於從鏈表中刪除節點。
獲取函數：

lRUCacheGet 函數用於從快取中獲取特定鍵的值。它首先計算鍵的雜湊值，然後遍歷對應的雜湊槽，找到對應的節點，並將其移動到鏈表頭部，以表示最近使用。如果找到鍵，則返回其值，否則返回 -1。
放置函數：

lRUCachePut 函數用於將鍵值對放入快取中。它首先計算鍵的雜湊值，然後遍歷對應的雜湊槽，查找是否存在相同的鍵。如果存在，則將其移動到鏈表頭部；否則，如果快取已滿，則淘汰最近最少使用的項目，並添加新的節點；如果快取未滿，則直接添加新的節點。最後，更新鍵對應的值。
釋放函數：

lRUCacheFree 函數用於釋放整個快取的內存。它遍歷快取中的每個節點，從鏈表中刪除節點並釋放內存。
這樣，通過使用雜湊表來實現快取的查找功能，並使用雙向鏈表來實現最近最少使用的淘汰策略，從而實現了 LRU 快取的功能。

改進方法並實作

釋放函數的改進：在 lRUCacheFree 函數中，釋放每個節點的內存後，將應該將節點從雜湊表中刪除。否則，快取的雜湊表可能會保留對已經釋放的節點的引用，這可能導致未定義的行為或記憶體泄漏。

更好的錯誤處理：在 lRUCacheCreate 函數中，應該檢查是否成功分配了快取結構的內存。如果分配失敗，應該進行適當的錯誤處理。

程式碼

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    int i;
    list_for_each_safe(pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, link);
        list_del(&cache->link);
        hlist_del(&cache->node);
        free(cache);
    }
    free(obj);
}

LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = malloc(sizeof(LRUCache) + capacity * sizeof(struct hlist_head));
    if (!cache) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    cache->capacity = capacity;
    cache->count = 0;
    INIT_LIST_HEAD(&cache->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_HLIST_HEAD(&cache->hhead[i]);
    return cache;
}

測驗三

實作 find_nth_bit 函數

原理解釋

find_nth_bit 函數是這段程式碼的主體。該函數接受三個參數：記憶體空間的起始地址 addr、記憶體空間的大小 size 和要找到的第 N 個設定的位元位置 n。
如果 n 大於或等於 size，則表示要找的位元超出了記憶體空間的範圍，因此直接返回 size。
如果 size 是一個小於等於 BITS_PER_LONG 的常數，則使用位元掩碼 GENMASK 取出相關的位元組，然後調用 fns 函數在這些位元組中尋找第 N 個設定的位元位置。
如果 size 大於 BITS_PER_LONG，則使用迴圈遍歷記憶體空間中的每個字，計算該字中設定的位元數量，並與要找的位元位置 n 進行比較，以確定要找的位元位於哪個字中。接著，使用 fns 函數在該字中尋找第 N 個設定的位元位置。
最終，返回第 N 個設定的位元位置，如果找不到，則返回 size。
內部輔助函數 __ffs 和 __clear_bit：

__ffs 函數用於在一個字中尋找第一個設定的位元位置，即從右邊數起第一個為 1 的位元的位置。
__clear_bit 函數用於清除指定位元的值，將其設置為 0。