# 2025q1 Homework2 (quiz1+2)
contributed by < `tyj513` >
## Week 1 Q1
函式 list_insert_before 的目的是在鏈結串列中，將一個新節點 item 插入到 before 指定的節點前面。這個實作使用了 "pointer to pointer" 技巧，通過雙重指標來簡化操作。
完整的函式如下：
```c
void list_insert_before(list_t *list, list_item_t *before, list_item_t *item) {
list_item_t **p;
for (p = &list->head; *p != before; p = &(*p)->next)
;
*p = item;
item->next = before;
}
```
### 運作原理
此函式使用「指標指向指標」技術，透過 list_item_t **p 操作指標的位址，讓插入操作更靈活。步驟如下：
- 初始化：p 指向 list->head 的位址。
- 尋找插入點：迴圈遍歷直到 *p 等於 before。
- 插入新節點：將 *p 設為 item，更新鏈結。
- 連結後續：將 item->next 設為 before。
這個技巧的優點是統一了在開頭插入和在中間插入的邏輯，不需要特別處理鏈結串列為空或在開頭插入的情況。
### Graphviz 視覺化
插入前（head -> 2 -> 3）：
插入 1 到 2 前：
### 實作合併排序 (Merge Sort)
```c
/* 拆分鏈結串列為兩半 */
void list_split(list_item_t *head, list_item_t **front, list_item_t **back) {
list_item_t *fast;
list_item_t *slow;
if (head == NULL || head->next == NULL) {
*front = head;
*back = NULL;
return;
}
slow = head;
fast = head->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*front = head;
*back = slow->next;
slow->next = NULL;
}
/* 合併兩個已排序的鏈結串列 */
list_item_t *list_merge(list_item_t *a, list_item_t *b) {
list_item_t dummy = {0, NULL};
list_item_t *tail = &dummy;
while (a && b) {
if (a->value <= b->value) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = (a) ? a : b;
return dummy.next;
}
/* 合併排序主函式 */
void list_merge_sort(list_item_t **headRef) {
list_item_t *head = *headRef;
list_item_t *a, *b;
if (head == NULL || head->next == NULL)
return;
list_split(head, &a, &b);
list_merge_sort(&a);
list_merge_sort(&b);
*headRef = list_merge(a, b);
}
/* 整合到list操作中 */
void list_sort(list_t *list) {
if (!list || !list->head)
return;
list_merge_sort(&list->head);
}
```
## Week 1 Q2
測驗二要求實作 remove_free_tree 函式，從二元搜尋樹（BST）中移除一個自由記憶體區塊。結構定義如下：
```ｃ
typedef struct block {
size_t size; // 區塊大小
struct block *l; // 左子節點
struct block *r; // 右子節點
} block_t;
```
未完成程式碼處理具有兩個子節點的情況：
```ｃ
if ((*node_ptr)->l && (*node_ptr)->r) {
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
}
```
### 運作原理
二元搜尋樹節點刪除步驟如下：
1. 先找到要刪除的節點在樹中的位置
2. 根據該節點的子節點數量，有不同的處理策略：
- 無子節點：直接移除
- 有一個子節點：用子節點替換當前節點
- 有兩個子節點：找到該節點的中序前驅或後繼替換它
在這個實作中，我們使用中序前驅替換有兩個子節點的目標節點。
中序前驅是指在中序遍歷中，排在目標節點之前的節點，即左子樹中的最大節點。
### Graphviz 視覺化
移除前（根節點 50）：
移除 50 後（由 40 替換）：
### 延伸問題：完整實作
完整的移除函式：
```ｃ
block_t** find_free_tree(block_t **root, block_t *target) {
block_t **p = root;
while (*p && *p != target) {
p = (target->size < (*p)->size) ? &(*p)->l : &(*p)->r;
}
return p;
}
void remove_free_tree(block_t **root, block_t *target) {
block_t **node_ptr = find_free_tree(root, target);
if ((*node_ptr)->l && (*node_ptr)->r) {
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
block_t *pred = *pred_ptr;
block_t *old_left = (*node_ptr)->l;
block_t *old_right = (*node_ptr)->r;
if (pred != old_left) {
remove_free_tree(&old_left, pred);
}
*node_ptr = pred;
pred->l = (pred == old_left) ? NULL : old_left;
pred->r = old_right;
} else {
*node_ptr = (*node_ptr)->l ? (*node_ptr)->l : (*node_ptr)->r;
}
target->l = target->r = NULL;
}
```
時間複雜度：O(log n)，由 BST 高度決定。
## Week 1 Q3
測驗 3 要求我們完成一個非遞迴版本的快速排序法，運用堆疊模擬遞迴呼叫。經過分析，解答為：
```
CCCC: p->next
DDDD: list_tail(&left)
EEEE: list_tail(&right)
```
對於 Linux 核心風格 List API 的改寫：
```
GGGG: head->prev=prev
HHHH: list_entry(pivot,node_t,list)->value
IIII: list_entry(n,node_t,list)->value
JJJJ: pivot
KKKK: right
```
### 運作原理解釋
非遞迴快速排序的基本思想
這個實作使用堆疊來模擬遞迴呼叫。傳統的快速排序法是遞迴實作的，但可能會導致深度遞迴時的堆疊溢位問題。非遞迴版本透過明確管理自己的堆疊來避免這個問題。
主要步驟：
- 初始化一個堆疊儲存待處理的子序列範圍
- 迴圈處理堆疊，每次從堆疊取出一個範圍
- 如果範圍內有多個元素，進行快速排序的分割操作
- 將分割後的子範圍再次壓入堆疊
- 重複直到堆疊為空
這個非遞迴快速排序的關鍵在於如何管理待處理的子序列。程式使用 begin[] 陣列作為堆疊，儲存各個子序列的開始節點。然後使用迴圈不斷從堆疊中取出子序列進行處理，直到堆疊為空。
在每次迴圈中：
1.檢查當前子序列的開始節點( L )和結束節點( R )
2.如果 L≠R，表示子序列有多個元素，需要進行分割：
- 選擇最左邊的元素作為 pivot
- 將剩餘元素分成兩部分：小於等於 pivot 的放入 left，大於的放入 right
- 將 left, pivot, right 三個子序列放回堆疊中
3.如果 L=R，表示子序列僅有一個元素，直接加入結果列表
Linux 核心風格的 List API 採用入侵式鏈結串列設計。入侵式鏈結串列將串列節點結構嵌入到資料結構中，而不是將資料包在節點結構中。這種設計有以下特點：
- 更有效率地使用記憶體，避免過多的記憶體配置與釋放操作
- 可以從鏈結節點（struct list_head）反向找到包含該節點的結構體
- 一個結構體可以同時屬於多個不同的鏈結串列
在這個實作中，list_entry 巨集用於從 struct list_head 指標獲取包含它的 node_t 結構體指標。
### 延伸思考：雙向鏈結串列排序演算法的比較研究
根據《A comparative study of linked list sorting algorithms》論文，針對雙向鏈結串列的排序演算法有以下考量：
雙向鏈結串列排序的主要挑戰與考量
記憶體存取模式：雙向鏈結串列節點在記憶體中通常不連續，導致較差的快取效能
連結操作成本：排序過程需要大量的指標重新連結操作
隨機存取限制：鏈結串列無法高效地隨機存取元素，影響排序演算法的效能
主要排序演算法在鏈結串列上的表現
- 合併排序 (Merge Sort)：
優點：合併操作非常適合鏈結串列，只需要重定向指標而不需要額外空間
缺點：遞迴深度可能較大
- 快速排序 (Quick Sort)：
優點：分割操作可以透過指標調整高效實現
缺點：隨機存取受限，樞紐點選擇較困難
- 插入排序 (Insertion Sort)：
優點：對小規模資料集或接近有序的資料效率高
缺點：對大型隨機資料效率低
```c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "list.h"
typedef struct __node {
long value;
struct list_head list;
} node_t;
static void list_split(struct list_head *head,
struct list_head **front,
struct list_head **back)
{
struct list_head *fast = head->next;
struct list_head *slow = head;
/* 使用快慢指標找到中點 */
while (fast != head) {
fast = fast->next;
if (fast != head) {
slow = slow->next;
fast = fast->next;
}
}
*front = head;
*back = slow->next;
slow->next->prev = slow;
slow->next = head;
head->prev = slow;
}
static struct list_head *list_merge(struct list_head *a,
struct list_head *b,
bool (*cmp)(struct list_head *, struct list_head *))
{
struct list_head dummy;
struct list_head *tail = &dummy;
INIT_LIST_HEAD(&dummy);
while (!list_empty(a) && !list_empty(b)) {
struct list_head *item;
if (cmp(a->next, b->next)) {
item = a->next;
list_del(item);
} else {
item = b->next;
list_del(item);
}
list_add_tail(item, &dummy);
}
if (!list_empty(a))
list_splice_tail(a, &dummy);
else
list_splice_tail(b, &dummy);
return dummy.next;
}
static bool list_value_less(struct list_head *a, struct list_head *b)
{
return list_entry(a, node_t, list)->value <
list_entry(b, node_t, list)->value;
}
void merge_sort(struct list_head *head)
{
struct list_head *a = NULL, *b = NULL;
if (list_empty(head) || list_is_singular(head))
return;
list_split(head, &a, &b);
merge_sort(a);
merge_sort(b);
head->next = list_merge(a, b, list_value_less);
head->next->prev = head;
}
void list_construct(struct list_head *list, int n)
{
node_t *node = malloc(sizeof(node_t));
node->value = n;
list_add_tail(&node->list, list);
}
/* 測試用串列釋放函式 */
void list_free(struct list_head *head)
{
node_t *entry, *safe;
list_for_each_entry_safe(entry, safe, head, list) {
list_del(&entry->list);
free(entry);
}
}
static bool list_is_ordered(struct list_head *head)
{
node_t *prev = NULL, *current;
list_for_each_entry(current, head, list) {
if (prev && current->value < prev->value)
return false;
prev = current;
}
return true;
}
int main(void)
{
struct list_head test_list;
int test_values[] = {5, 3, 8, 1, 7, 2, 6, 4};
int test_size = sizeof(test_values) / sizeof(test_values[0]);
INIT_LIST_HEAD(&test_list);
for (int i = 0; i < test_size; i++) {
list_construct(&test_list, test_values[i]);
}
merge_sort(&test_list);
assert(list_is_ordered(&test_list));
printf("排序結果: ");
node_t *entry;
list_for_each_entry(entry, &test_list, list) {
printf("%ld ", entry->value);
}
printf("\n");
list_free(&test_list);
return 0;
}
```
## Week 2 Q1
在測驗 1 中，我們需要完成 Linux 核心風格的快速排序函式 list_quicksort，該函式使用 Linux 核心的雙向鏈結串列 API 操作。函式骨架已經提供，需要填入適當的巨集或內聯函式
```c
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
// 如果串列為空或只有一個元素，不需排序
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
// 遍歷串列，根據大小將元素分配到兩個子串列
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
// 遞迴排序兩個子串列
list_quicksort(&list_less);
list_quicksort(&list_greater);
// 重新組合排序完的串列
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
### 運作原理解釋
這個快速排序演算法的實作基於 Linux 核心的雙向鏈結串列 API，主要步驟如下：
1.基本檢查：如果串列為空或只有一個元素，則無需排序
2.選擇樞紐：使用 list_first_entry 取得串列的第一個元素作為樞紐(pivot)
3.分割串列：
- 移除樞紐節點，使用 list_del 將它從原串列中斷開
- 遍歷原串列中的其餘元素，將小於樞紐的元素放入 list_less，大於等於樞紐的元素放入 list_greater
- 使用 list_move_tail 操作確保元素在子串列中保持原來的相對順序
4.遞迴排序：對 list_less 和 list_greater 遞迴應用快速排序
5.重組串列：
- 先用 list_add 將樞紐節點加入目標串列的開頭
- 用 list_splice 將 list_less（所有小於樞紐的元素）添加到目標串列的開頭
- 用 list_splice_tail 將 list_greater（所有大於等於樞紐的元素）添加到目標串列的末尾
```
digraph G {
rankdir=TD;
node [shape=box];
subgraph cluster_0 {
label="Using list_move_tail (Stable Sort)";
orig1 [label="Original List: A1=5, B1=5, C1=5"];
step11 [label="Process A1"];
less11 [label="list_less: A1"];
step12 [label="Process B1"];
less12 [label="list_less: A1, B1"];
step13 [label="Process C1"];
less13 [label="list_less: A1, B1, C1"];
result1 [label="Result: Maintains original order A1, B1, C1"];
orig1 -> step11 -> less11;
step11 -> step12 -> less12;
step12 -> step13 -> less13;
step13 -> result1;
}
subgraph cluster_1 {
label="Using list_move (Unstable Sort)";
orig2 [label="Original List: A2=5, B2=5, C2=5"];
step21 [label="Process A2"];
less21 [label="list_less: A2"];
step22 [label="Process B2"];
less22 [label="list_less: B2, A2"];
step23 [label="Process C2"];
less23 [label="list_less: C2, B2, A2"];
result2 [label="Result: Reversed order C2, B2, A2"];
orig2 -> step21 -> less21;
step21 -> step22 -> less22;
step22 -> step23 -> less23;
step23 -> result2;
}
}
```
### 隨機洗牌函式的分析與改進
#### 原始random_shuffle_array 函式的問題
原始的 `random_shuffle_array` 函式存在兩個主要問題：
##### 1. 洗牌有偏見（Biased Shuffling）
- **問題描述**：
在每一輪迭代中，隨機索引 `j` 是透過 `get_unsigned16() % (i + 1)` 計算的，其中 `get_unsigned16()` 返回 0 到 65535 的隨機數。當 `(i + 1)` 無法整除 65536 時，取模操作導致 `j` 的分佈不均勻。
- **範例分析**：
當 `i = 2` 時，`(i + 1) = 3`，`get_unsigned16() % 3` 將 0 到 65535 映射到 0、1、2：
- `j = 0`：出現 21846 次（0, 3, 6, ..., 65535）。
- `j = 1` 和 `j = 2`：各出現 21845 次。
- 機率：
- `P(j=0) = 21846/65536 ≈ 0.3334`
- `P(j=1) = 21845/65536 ≈ 0.3333`
- `P(j=2) = 21845/65536 ≈ 0.3333`
- **結論**：`j = 0` 的機率略高，導致洗牌結果偏向某些特定排列。
##### 2. 更新陣列的方式不正確
- **問題描述**：
程式碼使用 `operations[i] = operations[j]; operations[j] = i;` 更新陣列，這不是標準的交換操作。它將 `operations[j]` 的值複製到 `operations[i]`，然後將索引 `i` 賦值給 `operations[j]`，而不是交換兩者的值。這會破壞陣列元素的完整性。
- **錯誤範例**：
假設陣列初始為 `[10, 20, 30]`，長度 `len = 3`：
- **i = 0**:
- `j = get_unsigned16() % 1 = 0`
- `operations[0] = operations[0] = 10`（無變化）
- `operations[0] = i = 0`
- 結果：`[0, 20, 30]`
- **i = 1**:
- 假設 `get_unsigned16() = 3`，`j = 3 % 2 = 1`
- `operations[1] = operations[1] = 20`（無變化）
- `operations[1] = i = 1`
- 結果：`[0, 1, 30]`
- **i = 2**:
- 假設 `get_unsigned16() = 4`，`j = 4 % 3 = 1`
- `operations[2] = operations[1] = 1`
- `operations[1] = i = 2`
- 結果：`[0, 2, 1]`
- **問題總結**：
最終結果 `[0, 2, 1]` 不是原始陣列 `[10, 20, 30]` 的排列，原始元素被索引值替換，且由於 `j` 的偏見，某些排列出現機率更高。
---
#### 改進後的函式
改進後的函式採用 **Fisher-Yates 洗牌演算法**，程式碼如下：
```c
/* Fisher-Yates 洗牌算法的改進版本 */
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = 0; i < len; i++) {
uint16_t range = len - i;
uint16_t j = i + (get_unsigned16() % range);
uint16_t temp = operations[i];
operations[i] = operations[j];
operations[j] = temp;
}
}
```
#### 改進之處
##### 1. 使用標準 Fisher-Yates 演算法
- **原理**：
從索引 `i` 開始，隨機選擇一個位置 `j`（範圍從 `i` 到 `len - 1`），然後交換 `operations[i]` 和 `operations[j]`。
- **實現細節**：
- `range = len - i` 表示剩餘未處理的元素數量。
- `j = i + (get_unsigned16() % range)` 從當前位置到末尾均勻隨機選取。
- **優勢**：
每個元素有均等機會被交換到當前位置，所有排列的機率幾乎相等。
##### 2. 正確的交換操作
- **方法**：
使用臨時變數 `temp` 實現 `operations[i]` 和 `operations[j]` 的交換。
- **效果**：
保留原始陣列的所有元素，僅改變它們的位置。
##### 3. 減少偏見
- **分析**：
雖然 `get_unsigned16() % range` 在 `range` 不整除 65536 時仍有微小偏見，但由於 `range` 通常遠小於 65536，且 Fisher-Yates 的結構分散了這種影響，偏見幾乎可忽略。
##### 改進後範例
假設陣列初始為 `[10, 20, 30]`，長度 `len = 3`：
- **i = 0**:
- `range = 3`，假設 `get_unsigned16() = 4`，`j = 0 + (4 % 3) = 1`
- 交換 `operations[0]` 和 `operations[1]`：`[20, 10, 30]`
- **i = 1**:
- `range = 2`，假設 `get_unsigned16() = 3`，`j = 1 + (3 % 2) = 2`
- 交換 `operations[1]` 和 `operations[2]`：`[20, 30, 10]`
- **i = 2**:
- `range = 1`，`j = 2 + (get_unsigned16() % 1) = 2`
- 交換 `operations[2]` 和 `operations[2]`（無變化）：`[20, 30, 10]`
- **結果**：
`[20, 30, 10]` 是 `[10, 20, 30]` 的一個有效排列，每個排列的機率近似為 1/6。
### 為何使用 list_move 取代 list_move_tail 時無法滿足 stable sort？
list_move_tail 會將元素移到目標串列的尾部，保持了元素的相對順序
若改用 list_move，元素會被移到目標串列的頭部，導致原本的相對順序被反轉
在排序中，如果兩個元素的比較鍵值相同，穩定排序要求它們的相對順序保持不變
## Week 2 Q2
在測驗 2 中，我們需要分析並補完整數開平方根的實作。首先補完 clz2 函式中的空缺部分：
```c
static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {0, 1, 0, 2};
unsigned clz2(uint32_t x, int c)
{
if (!x && !c)
return 32;
uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));
if (c == 3)
return upper ? magic[upper] : 4 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}
```
對於 sqrti 函式，需要填入的表達式為：
```c
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
int shift = (total_bits - 1 - clz64(x)) & ~1;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
GGGG: 14
HHHH: 0
IIII: 2
JJJJ: 3
KKKK: 4
LLLL: 1
MMMM: ~1
NNNN: 1
PPPP: 2
運作原理解釋
整個實作包含兩個核心功能：計算前導零和整數開平方根。
1. clz2 函式：計算前導零
這個函式使用分治法遞迴計算 32 位元整數中的前導零數量：
基本情況：如果輸入為 0 且 c 為 0，則返回 32（表示全為零）
分割：將輸入 x 分為高位（upper）和低位（lower）部分
遞迴：
如果 upper 不為 0，則遞迴處理 upper 部分
如果 upper 為 0，則將 (16 >> c) 加到結果中，並遞迴處理 lower 部分
終止條件：當 c 達到 3（分割到最小單位）時停止遞迴
mask 和 magic 陣列用於在遞迴過程中處理位元操作和結果轉換。
2. sqrti 函式：計算整數開平方根
這個實作基於牛頓方法的變體，使用二進位數位一個一個尋找：
初始化：
找到輸入 x 的最高設置位，並將其向下取整到偶數位（shift = (total_bits - 1 - clz64(x)) & ~1）
設置 m = 2^shift，作為第一個測試位
初始化結果 y = 0
迭代：
計算 b = y + m
將 y 右移 1 位
如果 x ≥ b，則 x -= b 且 y += m
將 m 右移 2 位（測試下一個二進位位置）
重複直到 m 變為 0
結果：返回 y，即 x 的整數平方根
## Week 2 Q3
Sign in with Wallet
Connect another wallet