2024q1 Homework2 (quiz1+2)

contributed by < LULser0204 >

第一週測驗題

測驗1

前言

參考 Optimized QuickSort — C Implementation (Non-Recursive)，實作非遞迴 (non-recursive; iterative) 的快速排序法。作者是用了一個明確的堆疊( beg[] 和 end[] )取代了遞迴呼叫使用，減少了函式調用的開銷。

除此之外，作者在每一輪中只通過 swap 交換一次軸心點，避免了重複的移動開銷，減少了元素與自身交換的情況。

分析此題鍊結串列的運作

結構

自定義一個鍊結串列結構體:

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

在 node_t 結構中，他有一個指標 next 指向下一個節點，而 left 和 right 並沒有在 quicksort中特別著墨，猜測此為單向鍊結串列。

quick sort 程式碼

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 = p->next;
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = list_tail(&left);
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = list_tail(&right);

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

在這個函式的迴圈中，有幾個重要的步驟:
1.選擇軸心點 (pivot) 並將其從鍊表中分離。
2.遍歷練表，根據截點值與軸心點值得比較結果，將截點添加到 left 或 right 鍊表中
3.更新 begin 、 end 陣列以反映新的子鍊表界線。
4.重設 left 和 right 為 NULL 並增加i 以處理下一層
過程如下圖:

可改進之處

我認為可行的改進之處:
1.由於 quick sort 的效率很大程度依賴於軸心點的選擇。使用第一個作為軸心點在 worst case 下會導致很差的性能。

可以考慮使用"三數取中"策略，即從鍊表的(首部、中部和尾部)選擇三個元素，然後將這三個元素的中間值作為軸心點

測驗2

前言

Tim Peter 他結合合併排序和插入排序的特點，提出 Timsort。在現實世界中，許多資料往往是由一些已經部分排序的序列組合而成，於是他的策略是首先識別出資料中已排序的子序列 (這些子序列稱為 run），然後透過不斷合併這些 run 來達成全資料範圍的排序。

分析此題鍊結串列的運作

結構

雙向鏈結串列

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

鏈結串列元素

typedef struct {
    struct list_head list;
    int val;
    int seq;
} element_t;

完成程式碼

程式碼

AAAA 應該要填 &head 。因為要初始化 tail 指標的位址，使其指向鍊結串列的 head 位址。這樣 *tail 就可以被賦值為第一個節點，即合併後鍊節串節的頭節點。
BBBB 和 CCCC 應該要填 &(a->next) 和 &(b->next) 從上面可以得知 *tail 要放入的是下一個節點，故要更新 tail 值使其指向下一個節點的 next 。這麼做是為了在下一次跌代中，將下一個節點插入鍊結串列。
DDDD 和 EEEE 應該要填 head->prev 和 tail->next 完成雙向鍊結串列的循環。
FFFF 應該填 1 ，因為如果大於1代表鍊結串列還可以被合併

運作原理

run_size :根據鍊結串列的頭節點計算當前運行的大小。
merge :合併兩個已排序的鍊結串列。
build_prev_link :重新連接鍊結串列的 prev 指針。
find_run :在鍊結串列中找到一個遞增或是遞減的序列，並且翻轉遞減的序列使其成為遞增序列。
merge_at 、 merge_force_collapse 、 merge_collapse :這些函式負責串列的合併操作。
merge_final :所有的 runs 都通過上面的 merge 函式合併後，負責將最後兩個 runs 合併成一個完全有序的串列，以及重建雙向鍊結。

而主函式 timsort:

1.初始化和準備:將雙向鍊結串列轉換為以 NULL 為結尾的單向鍊結串列。
2.尋找並合併 runs :通過 find_run 尋找 runs，然後利用 merge_collapse 或 merge_force_collapse 根據特定規則來合併runs。後者是在排序過程接近完成時使用。
3.最終合併:當輸入的鍊結串列完全轉化為 runs 後，使用 merge_force_collapse 強制合併剩餘的所有 runs ，最後通過 merge_final 或 build_prev_link 重建整個串列的雙向鍊結。

改進方案

待補…

第二週測驗題

測驗1

前言

LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal 題意：

給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹。

Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

完成程式碼

先觀察hash table 實作中，用以處理 hash 數值碰撞的 hlist_node，注意他的 pprev 是 pointer to pointer

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

示意圖

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

AAAA 應該填 h->first 。因為要將新節點 n 插入 hash table 的頭部， n->next 應該指向原鍊結串列的第一個節點，即目前的 h->first
BBBB 應該填 &heads[hash] 。使用 hlist_for_each 遍歷特定的 hlist 。而 &heads[hash] 是該 hlist 的頭。
CCCC 應該填 list_entry 。從括號內的參數剛好對應 list_entry 的 (ptr, type, member) 推測。
DDDD 應該填 &heads[hash] 。在 node_add 函式中，其功能為將一個新的節點加入到 hash table 。 DDDD 應該指向我們想要增加新節點的鍊節串列的頭。

說明特定函式的功能

hlist_add_head :將一個新節點 n 加到指定的 hash table 頭部 h
find :根據給定的數字 num 和 hash table 大小 size ，在 hash table 中尋找對應的 order_node ，返回找到的節點其索引值。
dfs :首先通過 preorder 結果找到當節的根節點，然後在 inorder 結果中找到該節點，從而分隔出左右子樹，然後遞迴構建左右子樹。
node_add :將中序遍歷中的一個節點和索引加入到 hash table 中 dfs 函式快速找到任何節點在中序遍歷中的位置。
buildTree :使用前序和中序遍歷的結果來重建二元樹。首先使用 in_heads 紀錄中序遍歷中每個元素的 hlist 頭部。接下來，在迴圈內使用 node_add 進行中序遍歷，並且將其中的每個元素和對應的索引加到 hash table 。最後通過使用 dfs 函式構建二元樹，並返回構建好的二元樹根節點

運作原理

構建一個 hash table ，儲存 inorder 遍歷結果中每個元素，方便查詢以及之後建造二元樹
使用 dfs 函式深度優先方式尋找根節點，利用 find 函式回傳索引值(根節點位置)。
以根節點為中心，分為左右子樹，在遞迴乎叫 dfs 函式完成整棵二元樹。

可改進之處

待補…

測驗2

前言

針對 LeetCode 146. LRU Cache

題目說明:有一個 LRU Cache 其有一定的容量 (capcity) ，然後使用 put 放入 Cache 裡面，如果放入時 Cache 已滿，則把 LRU (Least Recently Used) key 拋棄，並把新的 key 放入 Cache ;而 get 則是看當下 Cache 裡面是否有對應的 key ，有則返回其值，並將對應的 key 更新，沒有則返回 -1 。

說明&完成程式碼

結構:
LRUCache :LRU 主要結構，包含容量 (capcity) 、當前數據量 (count) 、雙向鏈結的頭用於實現 LRU 功能 (dhead) 、hash table 陣列 (hhead) 用於快速查詢
LRUNode :存放在 LRUCache 中的節點結構，包含 key、value、hash table 節點、雙向鏈結串列節點 link

主要函式:
lRUCacheCreate :創建一件新的 LRU Cache 物件，初始化其 capcity、count、dhead、hhead
lRUCacheFree :釋放LRU Cache 中所占用的記憶體空間，包括所有 LRUNode 節點
lRUCacheGet: 從 Cache 中獲取一個元素的值。如果找到，將其移至雙向鏈結串列的頭，代表最近被使用。
lRUCachePut: 往 Cache 中放入一個新元素或更新現有元素的值。如果 Cache 已滿，則先移除 LRU 元素，然後在鏈結串列頭部放入新元素

EEEE :在 hlist_del 函式中，應該填入" next->pprev "。舉例:假設現在有 A->B->C 的串列，現在要刪除節點 B。
刪除前:

A 的 next 指向 B ， B 的 pprev 指向 A 的 next
B 的 next 指向 C ， C 的 pprev 指向 B 的 next
執行刪除動作:
將 B 的 pprev (即 A 的 next )更新為 B 的 next (即 C )，此時 A 直接指向 C
如果 B 的 next (即 C )存在，更新 C 的 pprev 為指向 A 的 next
刪除後:
A 的 next 現在指向 C ，C 的 pprev 指向 A 的 next (從串列中移除 B )
FFFF :要填入 link ，因為這是 LRUNode 結構中連接到 list_head 的 member 名。
GGGG :要填入 &cache->link 。這裡要傳遞一個指向 list_head 的 pointer 到 list_del 函式中刪除節點。
HHHH :要填入 node ，因為 lRUCacheGet 函式是基於 hlist_node 所指向的物件。
IIII :要填入 &cache->link 指向 list_head 結構的 pointer 。
JJJJ :要填入 node ，其原因一樣是基於 hlist_node 所指向的物件。
KKKK :要填入 &c->link ，在 lRUCachePut 函式的功能就是將剛使用到的節點移到鏈結串列的頭部。

運作流程

由 lRUCacheGet 進行查詢的動作，通過鍵的 hash table 值定位到位置，如果找到，則將對應的節點移到頭部，並返回值;反之，找不到則返回 -1 。
由 lRUCachePut 進行更新的動作，通樣先定位，檢查元素是否存在。如果存在，更新其值並移至頭部。如果不存在，檢查 Cache 是否已滿。滿了，去除掉 LRU 元素，增加新的元素在串列頭部;沒滿，直接增加新元素在串列頭部。

延伸問題

待補…

測驗3

前言

在指定的記憶體空間找出第 N 個設定的位元(即 1

解釋程式碼&完成程式碼

主要函式:
FIND_NTH_BIT :找到第 n 個 bit的位置。
_ffs : Find First Set 找到第一個 bit 位置。返回給定的無號整數最小有效位置的 index 。
__clear_bit :清除再給定位址中特定位。
fns :在一個常整數中找到第n個設置位的位置。通常迴圈使用 __ffs 來找到並清除最低設置位，直到找到第 n 個為止。

AAAA : 要填 0xffffffff 。根據下面判斷式中( 0x1、0x3、0xf…)的規律推導出來的
BBBB : 要填 ~mask 。 __clear_bit 函式主要功能是對於特定 bit 進行清除。要清除一個位元需要通過 AND 操作。
CCCC : 要填 % 。用於尋找第 n 個 bit 為 1 的索引。

運作主要原理

find_nth_bit 是整個核心。通過遍歷數組中每個字，使用 hweight_long 快速跳過完全為 0 的字，直到找到包含目標位置 bit 。然後再使用 fns 函式定位出確切的位置。

延伸問題

待補

第一週測驗題

測驗1

前言

分析此題鍊結串列的運作

結構

可改進之處

測驗2

前言

分析此題鍊結串列的運作

結構

完成程式碼

運作原理

改進方案

第二週測驗題

測驗1

前言

完成程式碼

說明特定函式的功能

運作原理

可改進之處

測驗2

前言

說明&完成程式碼

運作流程

延伸問題

測驗3

前言

解釋程式碼&完成程式碼

運作主要原理

延伸問題

Read more

2024q1 Homework5 (assessment)

2024q1 Homework4 (quiz 3+4)

2024q1 Homework1(lab0)