2024q1 Homework2 (quiz1+2)

contributed by < ollieni >

第一周測驗題

測驗一

這題是想透過非遞迴的方式實作 quick sort。
根據參考資料: Optimized QuickSort — C Implementation (Non-Recursive) ，作者提到想改進維基百科的做法，其中原因如下 :

避免函式呼叫，因為進出函式是耗時的。
不使用堆疊儲存資料，避免遞迴函數的性能慢且可能引起堆疊溢位。
交換變數只在每輪中傳遞一個項目，降低效能成本。
每輪中元素只移動到列表中的新位置一次，減少不必要的移動。
當元素在 pivots 目的地正確一側，避免不必要的移動。
避免在每輪中有50％的機會將列表中的元素與自身交換，降低性能成本。

這裡發現了一個問題，作者提到不使用堆疊儲存資料，但老師的測驗中提到"這份程式碼嘗試用堆疊模擬原本的遞迴呼叫"。
目前還沒想出這之間的關係。

本題的鏈結串列結構體如下:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

重新回答題目

要我們填空的程式碼如下:
首先是list_tail()，依據函式名稱可以推論出此函式的功能是找到鍊結串列的尾端。

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA);
    return *left;
}

可以看到 while 迴圈的停止條件是 *left 和 (*left)->next，其中之一為 NULL ，因此當 *left 指向尾端時，此迴圈就會停止，接著函式就會回傳 *left ，也就是尾端。
因此若是要找到尾端， left = &(AAAA); ，應為不斷往下一格移動。
所以 AAAA 的答案是 (*left)->next。

根據 list_length() 的函式名稱，我們可以得知此程式的目的是回傳鍊結串列的長度。

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(BBBB);
    }
    return n;
}

依據現有的程式碼可以得知，此函式會在 *left 不為 NULL 時，持續將 n 加一，當 *left 為 NULL 時停止(也就達到尾端)。
因此可以推論出 BBBB 會讓 *left 持續往尾端移動。
答案為 (*left)->next。

以下程式碼為 quick sort 實作的一部份。

.
.
.
    while (p) {
        node_t *n = p;
        p = CCCC;
        list_add(n->value > value ? &right : &left, n);
    }
    begin[i] = left;
    end[i] = DDDD;
    begin[i + 1] = pivot;
    end[i + 1] = pivot;
    begin[i + 2] = right;
    end[i + 2] = EEEE;

    left = right = NULL;
    i += 2;
.
.
.

CCCC 在一個 while 迴圈中，這個迴圈會根據 n->value 是否大於 value，將節點 n 添加到名為 right 或 left 的鍊結串列中，此迴圈目的是在將鍊結串列依據大小分成 pivot 左右兩邊的串列。
因此需要走過每一個節點， CCCC 為 p->next。
begin 和 end 分別是在記錄左右兩邊串列的頭尾，因此 DDDD 應為 begin[i] 的尾端，我們可以用 list_tail() 來找尾端， DDDD 的答案就會是 list_tail(left)。
EEEE 會是 begin[i+2] 的尾端，答案會是 list_tail(right)。

測驗二

請補完 Timsort 程式碼，使其運作符合預期。
Timsort 為合併排序和插入排序的組合算法。
將數列分成數個 run (比較小的數列)以 insertion sort 將 run 裡的數字排序，再將所有 run 用 merge sort 的方式合併在一起。
分 run 時，有幾點需注意

run 的長度不宜超過 64，因為 insertion sort 的效果會變差
run 最好是二的次方， merge 合併效率才會比較好

第二周測驗題

測驗一

LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
用前序 (preorder) 和中序 (inorder) 重構二元樹。

Preorder Traversal 前序遍歷:
用Depth-first Search走訪整棵樹，順序是：根、左子樹、右子樹。根排在最前面。

Inorder Traversal 中序遍歷:
也是採用Depth-first Search，走訪順序是：左子樹、根、右子樹。根排在中間。

Key point :

preorder 和 inorder ，可以用根的位置，用 Divide-and-Conquer 的概念，建立唯一二元樹。

在 preorder 之中，最左端一定是根節點。 inorder 中，根的兩側是左子樹和右子樹。因為子樹也是樹，可以用相同方式遞迴下去，求出整棵樹的架構。

hlist_node

Tree_Node 結構:

order_node 結構:

這是一個經典的問題，接下來我會以我的理解，解釋這題的程式。

函式解釋:
find
找出 value = num 的節點。
這個函數的目的是在 hash 串列中查找特定數值 num 的索引。
使用 hash 值計算，確保索引落在 hash 表範圍內。
透過 hlist_for_each 循環遍歷 hash 鏈表，並使用 container_of 將節點轉換為 order_node 結構。
若找到相應的數值，則返回對應的索引；否則返回 -1。

dfs
使用遞迴的方式做深度優先搜尋。
用於構建二元樹。
接收前序和中序走訪的區間，以及相應的 hash 串列等參數。
透過遞迴方式，根據前序遍歷的順序，建立二元樹的每個節點。
利用 find 函數找到中序走訪中該節點的索引，並分別遞迴建立左右子樹。

buildTree
使用 inorder 和 preorder 來建立一個唯一的樹。
這個函數是用於建立二元樹。
一開始配置 hash 串列的內存，並初始化每個 hash 串列。
使用前序遍歷的數組建立 hash 串列，同時調用 dfs 遞迴函式構建整個二元樹。
返回指向根節點的指標。

測驗二

程式目的 : 實作 Least Recently Used (LRU) Cache
在清除快取中的資料時，將上一次使用時間離現在最遠的資料清除。

LRUNode 結構：

LRUCache 結構

函式解釋 :
lRUCacheCreate
創建一個空的 lRU cache ，並根據 capacity 配置記憶體。

lRUCacheFree
將 lRUCache 清空，並釋放記憶體。
使用 list_for_each_safe 走訪全部節點，並將結點記憶體釋放。

lRUCacheGet
根據 key ，從快取中取出相對應的值。
將 key 除餘 capacity ，得到 key 的 hash 值，再用 hlist_for_each走訪，若在LRUCache->hhead[hash] 的每個節點中，有找到 key 的值，將該節點放到 obj->dhead，也就是最前面。

lRUCachePut
將 key-value 放入快取中。
先查詢 key 是否存在，若存在就將其放到最前面的位置。若不存在，先檢查 cache 是否滿了，若沒滿則直接將 key-value 插入。若 cache 已滿，將最後的 key-value 刪除，並將要插入的 key-value 放到最前面。

測驗三

程式目的 : 找到第 n 個為1的 bit 。
ffs :
此函式功能為找出第一個是 1 的 bit。
其運作原理和 find_leading_zero 很相似。

...
///如果最低的16位都为0，将 num 加上16，然后将 word 右移16位
if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
///如果最低的8位都为0，将 num 加上8，然后将 word 右移8位。
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
///如果最低的4位都为0，将 num 加上4，然后将 word 右移4位。
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
///如果最低的2位都为0，将 num 加上2，然后将 word 右移2位。
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
///如果最低的1位为0，将 num 加上1
    if ((word & 0x1) == 0)
        num += 1;
    return num;
...

clear_bit :
將特定區塊的 bits 刪除。
用 BIT_MASK(nr) 產生一個在 nr 位置是1，其他位置皆為0的 mask ，可用於清除特定 bit。
找到包含要刪除 bit 的 word 記憶體位置的 pointer。
對pointer 用 ~mask 做 bit-wise and 將 bit 刪除。

fns :
用 __ffs 去找第一個是1的 bit，用 __clear_bit 刪除，重複 n 次，即可找到第 n 個是 1 的 bit。

2024q1 Homework2 (quiz1+2)

第一周測驗題

測驗一

重新回答題目

測驗二

第二周測驗題

測驗一

Key point :

測驗二

測驗三

Read more

2024 Linux 核心實作期末專題 ：Pub/Sub 模擬

2024q1 Homework4 (quiz3+4)

2024q1 Homework5 (assessment)

2024q1 Homework6 (integration)

2024 Linux 核心實作期末專題：Pub/Sub 模擬