# 2024q1 Homework2 (quiz1+2)
contributed by[<Terry7Wei7>](https://github.com/Terry7Wei7)
## 第一週測驗題
### 測驗一
### 解析 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)
#### 運作原理
選擇樞軸（Pivot）： 一開始，從待排序的數組中選擇一個元素作為樞軸。這個枢軸的選擇可以是隨機的、固定的，或者使用一些特殊的選擇方法。在這個實現中，它選擇了待排序數組的第一個元素。
分割（Partition）： 將數組中的元素分為兩部分，使得樞軸左邊的元素都小於或等於樞軸，右邊的元素都大於或等於樞軸。這是通過左右兩個指針（L和R）的移動實現的，左指針找到一個大於樞軸的元素，右指針找到一個小於樞軸的元素，然後這兩個元素進行交換，重複這個過程直到左右指針相遇。
遞迴： 接下來，分別對樞軸左右兩邊的子數組遞迴地應用相同的排序過程。這就是快速排序的分治策略，將原始問題分解為兩個較小的子問題，然後遞迴解決它們。
結束條件： 遞迴過程中，如果子數組的大小變得足夠小（通常是只有一個元素或沒有元素），則遞迴結束。這時子數組視為已經排序。
繼續遞迴： 遞迴完成後，將所有子數組的結果合併起來，即可得到完全排序的數組。
這個實現中使用了一個額外的數組（beg 和 end）來跟踪每個子數組的起始和結束位置，而不是使用遞迴調用。這樣可以避免函數調用的開銷，並且沒有使用堆疊，這是一個非常基本但高效的實現方式。總的來說，快速排序是一種高效的排序算法，平均時間複雜度為O(n log n)。
#### 改進方法
將節點添加到左邊或右邊時，需要確定左右子鏈表的尾節點。
:::spoiler 程式碼
``` c code
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 能夠接近序列的中間值，從而更好地分割序列。
:::spoiler 程式碼
``` c code
// 隨機選擇 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](https://en.wikipedia.org/wiki/Timsort)
#### 運作原理
#### 改進方法
---
## 第二週測驗題
### 測驗一
### 解析[LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/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 結構，不需要存儲值的索引，因為在構建樹的過程中索引已經不再需要
:::spoiler 程式碼
``` c code
#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](https://leetcode.com/problems/lru-cache/description/)
#### 原理解釋
結構定義：
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 函數中，應該檢查是否成功分配了快取結構的內存。如果分配失敗，應該進行適當的錯誤處理。
:::spoiler 程式碼
``` c dode
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 函數](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)
#### 原理解釋
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。
Sign in with Wallet
Connect another wallet