2024q1 Homework2 (quiz1+2)

contributed by < yutingshih >

程式碼：linux2024-quiz on GitHub

第一週測驗題

測驗 1

程式運作原理

測驗題中提供的程式參考 Optimized QuickSort — C Implementation (Non-Recursive) 所實作的非遞迴 (non-recursive; iterative) 快速排序法，以堆疊取代遞迴函式呼叫，避免後者所帶來的額外開銷。

其中以 begin 和 end 兩個堆疊記錄串列中尚未排序好的部分，在每一輪迭代當中，會先選定 pivot 為串列首個節點，然後將整個串列分成比 pivot 小的左半部分、pivot 本身以及比 pivot 大的右半部分，並依序將其各自的起點及終點推入 begin 及 end 堆疊當中。

例如：左半部分有 A、B、C、D 四個節點，pivot 為 D 節點，右半部分則有 F、G、H 三個節點

left  : A -> B -> C -> D
pivot : E
right : F -> G -> H

接著將三者的起點和終點各自推入堆疊

index | 0  1  2  3  4 ... 7
------+---------------------
begin | A  E  D
end   | D  E  H

在下一輪迭代則從堆疊中拿取其中的半邊，也就是子串列 D 到 H 繼續進行排序

改進實作

測驗 2

程式運作原理

先解釋 Timsort 實作中重要的函式功能及重點：

• find_run 會從串列的開頭開始切出一段單調 (monotonic) 的子序列，若為遞減序列，則會將其調整為遞增序列後回傳
• merge_at 依照給定的比較函式 cmp，合併堆疊最上層的的兩個 runs
• merge_collapse 則會檢查堆疊 tp 中最上層的三個 runs 是否滿足以下條件，若不滿足則挑選 tp->prev->prev 及 tp 中較短者與中間的 tp->prev 進行合併，用來確保被合併的兩個 runs 長度盡可能接近
  • tp->prev->prev 長度大於 tp->prev 和 tp 的總和
  • tp->prev 長度大於 `tp
• merge_force_collapse 則不做上述條件的檢查，直接挑選 tp->prev->prev 及 tp 中較短者與中間的 tp->prev 進行合併
• merge 將兩串列合併後回傳
• merge 將兩串列合併後使用 build_prev_link 重建雙向環轉鏈結串列的鏈結

改進實作

整合

第二週測驗題

測驗 1

程式運作原理

測試程式

測驗 2

程式運作原理

測試程式

測驗 3

程式運作原理

find_nth_bit 的功能是找到第 n 個為 1 的位元，回傳其為整個搜尋範圍中的第幾個位元，並 LSB (least significant bit) 定義為第 0 個位元，若找不到，則回傳搜尋範圍的大小 size。

find_nth_bit 使用到 FIND_NTH_BIT 巨集及 fns 函式

fns 函式透過重複呼叫 __ffs n 次來尋找一個字節 (word) 中第 n 個為 1 的位元的位置，每次呼叫 __ffs 後都會將該位元清空，連續呼叫 n 次就相當於尋找第 n 個為 1 的位元。

GENMASK 巨集產生自第 l 到第 h 位元為 1 的遮罩 (mask)，其中最低位編號為 0

small_const_nbits 檢查 nbits 是否為大於 0 且小於等於 BITS_PER_LONG 的常數

__const_hweight8、__const_hweight16、__const_hweight32 以及 __const_hweight64 分別計算最低數個位元當中有多少個為 1 的位元，hweight_long 則和 __const_hweight64 行為相同

FIND_NTH_BIT 首先逐字節判斷是否存在第 num 個位元為 1，若目標存在於當前字節，則呼叫 fns 函式尋找第 n 個為 1 的位元，找不到則直接回傳 size。