Try   HackMD

2024q1 Homework2 (quiz1+2)

contributed by < devarajabc >

第一週測驗 1

參考 Optimized QuickSort — C Implementation (Non-Recursive),實作非遞迴 (non-recursive; iterative) 的快速排序法

1.解釋上述程式碼的運作原理。

參考 csotaku0926, chloe0919
利用指標陣列 beginend 來模擬堆疊
從堆疊中取出索引值對應的指標 begin[i]end[i]並將值存在LR 之中
並將 pivot 設定為 L

node_t *L = begin[i], *R = end[i];

示意圖如下







graphname



A

4



B

1



A->B





C

3



B->C





D

5



C->D





E

2



D->E





F

7



E->F





G

8



F->G





NULL
NULL



G->NULL





L
L



L->A





pivot
pivot



pivot->L





R
R



R->G





L 不等於 R 時,
將大於 pivot 的節點加入 right ,反之則加入 left







%0



A
left



2

2



A->2





B
right



8

8



B->8





C
pivot



4

4



C->4





7

7



8->7





5

5



7->5





3

3



2->3





1

1



3->1





接著分別用指標 begin[i]end[i] 來記錄 left 的開頭與結尾、begin[i+2]end[i+2] 來記錄 right 的開頭與結尾,而 pivot 則同時用 begin[i+1]end[i+1] 來記錄
最後將堆疊的索引 i 更新為 i+=2
(取出一層又放回三層)
是意圖如下:

改進你的漢語表達。







graphname



p
pivot



4

4



p->4





p1
begin[i+1]



p1->4





p2
end[i+1]



p2->4





A

8



B

7



A->B





C

5



B->C





D

2



E

3



D->E





F

1



E->F





R
end[i]



R->F





right
right



right->A





left
left



left->D





L
begin[i+2]



L->A





L1
begin[i]



L1->D





R1
end[i+2]



R1->C











graphname


cluster_0

begin


cluster_1

end



begin[i+2]

begin[i+2]



begin[i+1]

begin[i+1]



begin[i]

begin[i]



end[i+2]

end[i+2]



end[i+1]

end[i+1]



end[i]

end[i]



可以想像成這樣:







graphname



map

stack

begin[i+2] end[i+2]

begin[i+1] end[i+1]

begin[i] end[i]



反之當 L 等於 R 時,代表走訪到 pivot ,也就是「位置正確」的節點,所以使用 list_add 來將該節點加入 result 並將 i--

2.提出改進方案並予以實作

  1. 選擇 povit 的方式
  2. max_lengh 的大小

3.使用 Linux 核心風格的 List API 改寫上述程式碼,並針對鏈結串列,提出可避免最差狀況的快速排序實作,應設計效能評比的測試程式。

參考 list.h

第一週測驗 2

Timsort 的實作,刻意不額外配置記憶體空間

1.解釋上述程式碼的運作原理,提出改進方案並予以實作。

參考 jimmylu890303
程式執行可以分成以下幾個階段

  1. 將原本的串列的最後一個節點解除環狀佇列,並將它指向 NULL
  2. 利用 find_run 將從 list 分割出一個 run ,並將該 run 的開頭的 prev 設為上一個 run 的開頭,示意圖如下 :






%0



tp
tp



8

8



tp->8





A
Z



1

1



A->1





B
Y



5

5



B->5





C
X



C->8





9

9



8->9





8->5


   tp->prev



6

6



5->6





5->1


   tp->prev->prev



7

7



6->7





2

2



1->2





3

3



2->3





4

4



3->4





上圖修改自 jimmylu0303

  1. stk_size >= 2 時,利用 merge_collapse 來保堆疊上的 run 長度保持平衡
  2. 利用merge_force_collapse 使 stk_size 長度小於 3
  3. 將 linked-list 恢復成 circular doubly-linked list
  4. stk_size 為 2 則需要利用 merge_final 合併最後兩個 run

以下是對 timsort 會用到的函式進行細部的解釋

create_sample

space 是指向「一大串可用且連續的記體空間」的指標,藉由 element_t *elem = space + i 來配置一段記體空間給 element_t 並用區域變數 elem 指向它,隨後使用 rand() 來將 elem->val 設成一個隨機數,最後利用list_add_tail(&elem->list, head)將 element_t 加入鏈接 head 。

copy_list

利用 element_t *copy = space++ 來獲得「指向可使用的記憶體空間」的指標,並在隨後的 list_for_each_entry 中不斷將鏈接 from 中每個的 entry 的資訊如 val, seq 複製到該記憶體空間 , 最後再將該記憶體空間加入鏈接 to 之中。

compare

比較鏈接 a 和鏈接 bval 並輸出相減的結果,跟 strcmp 很像
void *priv 的功能是,窩不知道

check_lis

用來檢查是否有以下三種錯誤情況

  1. Wrong order
  2. unstable
  3. inconsistance

run_size

一開始看不懂為何 (size_t) (head->next->prev) 就是 runsize ?,一直到參考了 HotMercury 的解釋才知道 run 的被以指標的型態儲存在head->next->prev 之中,最後用 (size_t) 來轉換型態並輸出。

merge

使用逐對合併 (one-pair-at-a-time) 合併兩個單向的鏈接( null-terminated singly-linked list )。

tail 是「指向尾端的指標」的指標,並在 for loop 中不斷更新,最後回傳指向「合併好的鏈結串列 」的指標。
(TODO : 補圖片)

將單向鏈結串列恢復成雙向鏈結串列。
但我不懂最後兩行程式碼為何可以讓其回復成雙向鏈結串列

/* And the final links to make a circular doubly-linked list */
	tail->next = head;
	head->prev = tail;
merge_final

內容與 merge 相似
不同之處在於:

  1. 使用 Parameter head 來當記錄「合併好的鏈結串列」
  2. 在函式最後使用 build_prev_link 來將單向鏈結串列恢復成雙向鏈結串列
  3. 輸出為 void
find_run

參考 HotMercury

輸出為 pair ,裡面包含了兩個指標 nexthead
head 為指向當前 run 的指標,而 next 為指向下一個 run 的指標。
在走訪鏈接的過程中會遇到以下兩種情況:

  1. 遇到連續的遞減的節點 -> 計算長度 len 並將其反轉,直到遇到比當前節點還大的節點
  2. 遇到連續的遞增的節點 -> 計算長度 len ,直到遇到比當前節點小的節點-> 將最後一個節點的 next 設為 NULL 。

最後透過 head->next->prev = (struct list_head *) len巧妙地將長度 len 藏在 prev

程式碼註解以美式英語書寫,不該存在漢語。
用清晰的漢語解釋程式行為後,再搭配程式碼驗證,避免「舉燭」。

merge_at

合併 atat->prev 再用指標 list 指向合併的結果且利用 list->prev = prev 來維護鏈接的順序同時減少 stk_size 的值
(推測是在處理 stack 內的合併)
並利用 list->next->prev = (struct list_head *) len 更新合併後的 run 長度,最後再回傳 合併後的 run 。

merge_collapse

參考 維基百科jimmylu890303

Representation_of_stack_for_merge_memory_in_Timsort

The runs are inserted in a stack. If |Z| ≤ |Y| + |X|, then X and Y are merged and replaced on the stack. In this way, merging is continued until all runs satisfy :
i. |Z| > |Y| + |X|
ii. |Y| > |X|.

在本例子中,X 是 tp , Y 是 tp->prev , Z 是 tp->prev->prev
而要合併的形況分成以下 3 種

  1. |Z| <= |Y|+|X| 且 |Z| < |X|
YZ 合併
tp->prev = merge_at(priv, cmp, tp->prev);
  1. |Z| <= |Y|+|X| 且 |Z| >= |X|
XY 合併
tp = merge_at(priv, cmp, tp);
  1. |Y| <= |X|
XY合併
tp = merge_at(priv, cmp, tp);
merge_force_collapse

merge_collapse 不同之處在於 merge_force_collapse 會不斷進行以下兩種合併直到run_size 小於 3

  1. |Z|<|X|
YZ合併
tp->prev = merge_at(priv, cmp, tp->prev);
  1. 其他
XY合併
tp = merge_at(priv, cmp, tp);

merge_collapse 只要遇到以下兩種情況就會離開 while loop

1. |Z| > |Y| + |X| 
2. |Y| > |X|

2.提出改進方案並予以實作

1. merge 裡面重複的部分太多,且沒有使用 Galloping mode

考慮到 A 和 B 都是已排序好的數列,我們可持續改進:首先尋找 B 的首個元素(即)在 A 中的排序位置,從而確定 A 中有一段是小於者,可將這部分元素放回 A。接著,尋找剩餘 A 的首個元素在 B 中的位置,如此反覆進行,直到完成排序。

參考 yanjiew

然而有關「重複部分太多」 的改進方案再參考 第一次嘗試貢獻 Linux 核心 所提供的結果後發現小丑竟是我自己。

2. find_run 沒有遵守 2 的冪的原則也沒有確保每個run 的長度不小於 minrun

  1. 選擇 minrun 的策略是 Timsort 的關鍵,我打算使用 2024q1 第 1 週測驗題 裡面提到的方法:

取資料長度的前 6 位,若剩餘位中任何一位被設置,則加 1。
這主要是為了在處理隨機數列時,使得能夠被 minrun 切分成 2 的冪的 run,以便在合併時達到最佳平衡。

原本看不懂敘述,直到翻閱了 Wikipedia: Timsort 中的描述才知道是取陣列長度的「二進位表示法」的前六位為 minrun ,若剩餘位中任何一位被設置(剩餘位中有任何一位是1),則 minrun 要再加 1。

minrun 具體具體流程如下:

  1. 找到前六位
    在 while loop 中不斷將 n 除以 2 直到其值小於等於 63 (111111,六位皆為1)
  2. 檢查剩餘位數是否有被設置(有 1 )
    使用 n & 1 來取得最後一位 (LSB) 的值 ,並用 | 來更新 r 的值
size_t calculate_minrun_naive(size_t n) {
    size_t r = 0; 
    while (n >= 64) {
        r |= n & 1;
        n >>= 1;
    }
    return n + r;
}

考慮 compute_minrun 的實作,以 CLZ 加速與算,善用 GCC 的 __builtin_clz

了解

參考 compute_minrun
步驟如下:

  1. 利用 CLZ 來計算 top_bit , size 轉換成二進位後的位數
  2. 計算 shift ,要向右移的大小,若 size 不足六位則為零
  3. 做出 mask ,來判斷剩餘位數是否有被設置(1)
  4. minrun = size 的前六位,若有被設置則再加 1

2.改寫 find_run

Timsort 為了使合併過程更加均衡,需要儘量控制每個 run 的長度,定義一個 minrun (最小運行長度),用以表示每個 run 的最小長度,若長度太短,就用二分插入排序,將 run 後面的元素插入到前面的 run 裡面。

若對鏈結串列使用 binary_insert 的話時間複雜度會很糟糕(TODO:原因補充)

今天一整天都卡在無法用鏈結串列實作出 binary_insert 而沒有思考為何要使用 binary_insert 以及是否非使用 binary_insert 不可,就埋頭亂寫一通,浪費一堆時間,下不為例。

naive:每個 run 的長度固定為 minrun

2.將改進過的 Timsort 實作整合進 sysprog21/lab0-c,作為另一個有效的排序命令,應設計效能評比的測試程式,確保測試案例符合 Timsort 設想的資料分布樣式。


第二週測驗 1

運用 Linux 核心的 hash table 實作 來完成 LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

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

解釋程式碼的運作,撰寫完整的測試程式,指出其中可改進之處並實作

參考 jimmylu890303

Hash table 中的元素為 hlist_head ,而 Hash table 中各個 bucket 的節點為 hlist_node

在結構 hlist_node 之中, pprev 為「指向自己的指標」的指標







G



list_head

list_head

first



node_1

hlist_node_1

pprev

next




list_head:n->node_1:m





node_1:p->list_head:n





node_2

hlist_node_2

pprev

next




node_1:n->node_2:m





node_2:p->node_1:n





node_3

hlist_node_3

pprev

next




node_2:n->node_3:m





node_3:p->node_2:n





NULL
NULL



node_3:n->NULL





程式的執行可以分成以下幾個步驟

  1. INIT_HLIST_HEAD
  2. node_add
  3. dfs

可改進之處

  1. 在原本的程式中,只使用了 hash = (num < 0 ? -num : num) % size 當作雜湊函數
    故想改使用在 hash.h 中提到的
    h(K)=K×2w×A>>(wp)

3.在 Linux 核心的 cgroups 相關原始程式碼,找出 pre-order walk 程式碼並探討


第二週測驗 2

LeetCode 146. LRU Cache

2.解釋上述程式碼的運作,撰寫完整的測試程式,指出其中可改進之處並實作

本題新增了兩個新的結構

typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;






G



LRUCache

LRUCache

capacity

count

dhead

hhead[]



LRUNode

LRUNode

key

value

node

link




參考 jimmylu890303

lRUCacheCreate
lRUCacheFree
lRUCacheGet
lRUCachePut

3.在 Linux 核心找出 LRU 相關程式碼並探討

測驗 第二週測驗 3

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

2.解釋上述程式碼的運作,撰寫完整的測試程式,指出其中可改進之處並實作

3.在 Linux 核心的 cgroups 相關原始程式碼,找出 pre-order walk 程式碼並探討