Try   HackMD

2024q1 Homework2 (quiz1+2)

contributed by < LindaTing0106 >

第一週測驗題

測驗 1

此函式目的在於找到串列的尾端,故在 *left(*left)->next 不等於 null 的情況下,
left 應該要等於 &(*left)->next ,也就是 *left 下一個節點的地址。

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

此函式是在計算整個串列的長度,所以 while 中只需要判斷 *left 當下的節點是否為 null ,如有指向節點,則可以持續往下一個節點,並計算長度。
left = &(*left)->next

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

此處 CCCC 填入 p->next ,因為此函式需要去遍歷串列的每個節點,並根據他們大於或是小於 pivot 的值,決定應該插入 right 或是 left

while (p) {
    node_t *n = p;
    p = CCCC;
    list_add(n->value > value ? &right : &left, n);
}

原本想法是因為 begin 和 end 儲存一段串列的頭與尾,像是前面的

begin[0] = *list;
end[0] = list_tail(list);

所以 DDDD = list_tail(left)EEEE = list_tail(right)

後來發現是傳進去的型態問題, node_t *list_tail(node_t **left) 傳入的型態應該為 pointer of pointer of node_t ,故將答案改為 DDDD = list_tail(&left)EEEE = list_tail(&right)

begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;

延伸問題:

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

上述的快速排序法是使用非遞迴的方式實作。

還沒進入迴圈之前, begin[0]end[0] 分別會指向串列的頭與尾。







First



4

4



1

1



4->1





3

3



1->3





5

5



3->5





2

2



5->2





7

7



2->7





NULL
NULL



7->NULL





begin[0]
begin[0]



begin[0]->4





end[0]
end[0]



end[0]->7





先選定 4 作為 pivot ,並且將 pivot 從串列移除,之後開始比較 pivot 與串列各個節點之間的大小,將小於 pivot 的節點 list_addleft ,大於 pivot 的節點 list_addright







pivot_is_4



4

4



pivot
pivot



pivot->4











move_p



1

1



3

3



1->3





5

5



3->5





2

2



5->2





7

7



2->7





NULL
NULL



7->NULL





p
p



p->3





n
n



n->1





排列好大小後,利用 begin[i]end[i] 指標指向串列的頭跟尾。
begin[i]end[i] 指向的是比 pivot 小的串列, begin[i+2]end[i+2] 指向的是比 pivot 大的串列, begin[i+1]end[i+1] 則指向 pivot 。







begin_end



7

7



5

5



7->5





2

2



3

3



2->3





1

1



3->1





4

4



right
right



right->7





left
left



left->2





begin[0]
begin[0]



begin[0]->2





end[0]
end[0]



end[0]->1





begin[1]
begin[1]



begin[1]->4





end[1]
end[1]



end[1]->4





begin[2]
begin[2]



begin[2]->7





end[2]
end[2]



end[2]->5





由於 i += 2; 所以先從上一回合比 pivot 大的串列開始執行上述動作。
將 7 當作 pivot 所以在比大小的時候, 將節點 5list_addleft,而right 只能指向 NULL 。







pivot2



7

7



begin[3]
begin[3]



begin[3]->7





end[3]
end[3]



end[3]->7





pivot
pivot



pivot->7











round2



5

5



NULL
NULL



left
left



left->5





begin[2]
begin[2]



begin[2]->5





end[2]
end[2]



end[2]->5





right
right



right->NULL





begin[4]
begin[4]



begin[4]->NULL





end[4]
end[4]



end[4]->NULL





再下一回合 i = 4 時,因為 begin[4]end[4] 都指向 NULL ,所以進到else中,並且 i-- ,來到 i = 3 ,由於 begin[3]end[3] 都指向節點 7,故將 7 list_addresult ,且 i--i = 2 時也是相同操作,將 5 list_addresult 。重複以上步驟,最終 result 則會為一個遞增串列,以上及為程式碼的運作原理。

提出改進方案並予以實作。

從上述程式碼可以看出他永遠都是選擇第一個節點作為 pivot ,但當最差情況發生時的時間複雜度會來到 O(n²) ,像是 [1, 2, 3, 4, 5] 則每次選到的 pivot 都為最左邊的數字,如此 left 都為 NULL 而 right 為除了 pivot 以外的節點。如此每次選擇 pivot 後,都要遍歷剩下的節點,那麼就可以使用 Median of Medians Algorithm 的方法去規避最差情況發生。

使用 Linux 核心風格的 List API 改寫上述程式碼

程式碼

在程式碼中引入 list.h 函式,並將 node_t 改為串列連接。

+#include "list.h"

 typedef struct __node {
-    struct __node *left, *right;
-    struct __node *next;
+    struct list_head list;
     long value;
 } node_t;

將程式碼內部用到 node_t 的函式,都改寫為 list_head 的型態。
由於改為 list_head 的型態,故可以將 list_tail 的函式刪除,直接使用 list->prev 的方式表示最尾端的端點,故也將 end 移除。但因為要保存每次分治的串列,故這裡的 begin 需要配置 list_head 的空間。

-    begin[0] = *list;
-    end[0] = list_tail(list);
+    for (int be = 0; be < max_level; be++){
+        begin[be] = list_new();
+    }

+    begin[0] = list;

     while (i >= 0) {
-        node_t *L = begin[i], *R = end[i];
+        struct list_head *L = begin[i]->next, *R = begin[i]->prev;

此外將原本很多單純用 = 賦予值的部分,改為運用 list_splice_initlist_move

並針對鏈結串列,提出可避免最差狀況的快速排序實作,應設計效能評比的測試程式。

測驗 2

AAAA 填入 &head ,則可以透過指標的指標進行編寫。

struct list_head *head;
struct list_head **tail = AAAA;

當此處的priv不為 NULL ,則會將型態轉為整數的指標,使用*取值後再加 1 。初步認為這裡應是對應到最後算出比較次數的計算。

int compare(void *priv, const struct list_head *a, const struct list_head *b)
{
    if (a == b)
        return 0;

    int res = list_entry(a, element_t, list)->val -
              list_entry(b, element_t, list)->val;

    if (priv)
        *((int *) priv) += 1;

    return res;
}

在比較完兩個節點的大小後,使用 *tail 將較小的節點連接到 head ,而後應該要將 tail 指向此節點的 next ,讓下次比較大小時,較小的節點可以繼續接在 *tail 處,也就是讓尾端的 next 可以放入下一個節點的地址。
BBBB 應該填入 &(*tail->next) , 但因為要填入最精簡的程式碼,故寫成 &a->next
CCCC 只是換成在如果節點 b 比 a 的值小的情況,所以可以直接填入 &b->next

 if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = BBBB;

從此段程式碼來看, list 最終會指向 NULL ,而需要補上 DDDDEEEE 才能使整個串列變成雙向環狀鏈結串列,所以需要將 list 的前一個節點,也就是 tail 的下一個節點變為 head ,並且 head 的上一個節點也應該要為 tail 。故 DDDD 填入 tail->next ,而 EEEEhead->prev

static void build_prev_link(struct list_head *head,
                            struct list_head *tail,
                            struct list_head *list)
{
    tail->next = list;
    do {
        list->prev = tail;
        tail = list;
        list = list->next;
    } while (list);

    /* The final links to make a circular doubly-linked list */
    DDDD = head;
    EEEE = tail;
}

在這段程式碼中我們可以觀察到 stk_size 此變數,一開始是設為 0 ,而在後面找 run 的迴圈裡,此變數也會更著增加,從這裡我們可以判斷 stk_size 是表示著切了幾個 run 的個數,並且在各個合併的函示中, stk_size 的數量也會減少。
而在 build_prev_link(head, head, stk0); 此函式中,我們可以得知是在將最後合併出來,只剩下一個 run 的串列修正為雙向環狀鏈結串列,故 FFFF 填入 1。

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)

延伸問題:

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

在上述程式碼內,並無設定 minrun 的部分,假設被傳入 find_run 的 list 。







find_run



5

5



4

4



5->4





3

3



4->3





6

6



3->6





1

1



6->1





因為 5 > 4 的關係想辦法讓這段 run 反轉。







de



5

5



NULL
NULL



5->NULL





4

4



3

3



4->3





6

6



3->6





1

1



6->1





list
list



list->4





next
next



next->3





head
head



head->4





prev
prev



prev->5





最後回傳回主程式遞增的 run ( 稱 run1 ) ,以及另一個還沒被排序過的串列。







de2_break



5

5



NULL
NULL



5->NULL





4

4



4->5





3

3



3->4





6

6



1

1



6->1





list
list



list->3





next
next



next->6





head
head



head->3





prev
prev



prev->4





result.head
result.head



result.head->3





result.next
result.next



result.next->6





tp 會將排序過的 run 的 head 串接在一起,經過剛剛的 find_run ,現在 run 的數量等於 1 ,接著進入 merge_collapse ,但因為 run==1 ,所以直接跳出。
再跑一次迴圈後,剛剛剩下來沒有被排序的串列,經過 find_run 的處理後, result.head 的指針會指向處理好的 run ,在這裡程式是用 result.head->prev 指向 run1 。







run2



1

1



6

6



1->6





NULL
NULL



6->NULL





result.head
result.head



result.head->1





result.next
result.next



result.next->NULL





之後再次進到 merge_collapse 函式,根據是否滿足上面提到的原則,來決定要不要進行合併。

提出改進方案並予以實作。

明顯可以發現上述程式碼中並沒有包含 minrun 的實作,故應將 minrun 加入程式的實作。 minrun 的大小為,將總資料長度轉為二進位後的前 6 位數字,若 6 位數字後不為 0 ,則加 1。

第二週測驗題

測驗 1







hashTable



node2

 

 

 

 

 



node3

val = 3

idx = 1



node2:1->node3





node4

val = 9

idx = 0



node2:0->node4





NULL
NULL



node2:2->NULL





這段重建二元樹的程式碼,是先從 TreeNode *buildTree 開始,首先程式會先創一個空的 hash table ,並且利用 void node_addinorder 的節點放入 hash table 中,其中節點資訊包含了數值和位置。







hashTable



node2

 

 

 

 

 



node3

val = 3

idx = 1



node2:1->node3





node4

val = 9

idx = 0



node2:0->node4





NULL
NULL



node2:2->NULL





之後在 TreeNode *dfs 中,會利用指標 *tn 去存取目前在前序中最前面的節點的數值,當作此子樹的頭,以及利用這個數值在 int find 中找尋其在中序裡的位置。







tnleft



node1

3

9

20

15

7



pre_low
pre_low



pre_low->node1:1





pre_high
pre_high



pre_high->node1:1











tnleft



node1

9

3

15

20

7



in_low
in_low



in_low->node1:0





in_high
in_high



in_high->node1:0





其中 tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size); ,會持續遞迴出左子樹的函式。 pre_low + 1 做為下輪的 int pre_low 是因為第一個已經被當作頭了,所以 pre_low 就往前一格。 pre_low + (idx - in_low) 做為下輪的 int pre_high ,則是利用 idx - in_low 可以算出左子樹有的節點數量,所以用 pre_low + 左子樹有的節點數量,得出後面 pre_low + (idx - in_low) 格的節點都是左子樹的節點。 idx - 1 做為下輪的 int in_high 是因為在中序中,頭左邊的所有節點都是左子樹的節點。







tnleft



node1

3

9

20

15

7



pre_low
pre_low



pre_low->node1:2





pre_high
pre_high



pre_high->node1:4











tnleft



node1

9

3

15

20

7



in_low
in_low



in_low->node1:2





in_high
in_high



in_high->node1:4





tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size);pre_high - (in_high - idx - 1) 做為下輪的 int pre_low 是因為 (in_high - idx - 1) 可以得出在前序中右子樹的尾到右子樹的頭中間的節點數量,故用 pre_high 減去,可得右子樹的頭的節點的位置。 idx + 1 做為下輪的 int in_low ,則是因為在中序中頭的右側即全為右子樹節點。

測驗 2

LRU Cache 是將一種快取的實做方式,當有新資料進來時,將快取中最後一次被存取的部分給替代掉。

需要寫一般串列和 hash table 的串列,來去串接節點是因為可以利用 hash table 提升我們在取值時的速度,如果只有一般串列,那我們必須遍歷 count 個節點找尋我們要的節點。而需要一般串列是因為我們這樣才有哪個節點是最後被使用的紀錄。

typedef struct {
    int capacity; // 其LRUCache的大小
    int count; // 目前使用的數量
    struct list_head dhead; // 串接所有的節點
    struct hlist_head hhead[]; // 用 hash table 的方式儲存節點
} LRUCache;

LRUCache *lRUCacheCreate(int capacity) 會根據其容量大小來為其配置記憶體大小。

void lRUCacheFree(LRUCache *obj) 利用傳入的指標,將其指向的快取給刪除,程式裡面用到 list_entry 函式,來取得快取中的串列的物件,再將其各個刪除。應該也可以使用 hlist_del 將 hash table 中串列的節點移除。

int lRUCacheGet(LRUCache *obj, int key) 程式碼中會先遍歷對應的 hash table 中的串列,如果有找到對應的值,則將 dlist 中該節點,搬去串列的最前方,並回傳該值,如果找不到,則回傳 -1

void lRUCachePut(LRUCache *obj, int key, int value)
是希望將給定的值放入快取中,首先會利用 key 求出 hash 值,再利用 hash 值來檢查是否此 key 值已經使用過了。

  • 如果使用過了,則將此節點移動至串列最前方並且將 value 改為新的值。
  • 如果沒有使用過,則比對傳進來的快取是否已經滿了。
    • 如果空間滿了,則將最後一個使用的節點移至串列的最前方,並將其在 hash 中對應的位置刪除,並且再將其放入 hash table 中。
    • 如果空間沒有滿,則新配置一個空間,並將節點加入串列,也加入 hash table 中,並將 count++ 。

這段程式碼相當為將 &cache->node move 至 &obj->hhead[hash] ,既然都有 list_move 了,也可以實作出 hlist_move 。

hlist_del(&cache->node);
hlist_add_head(&cache->node, &obj->hhead[hash]);

測驗 3

find_nth_bit 在指定的記憶體空間找出第 N 個設定的位元。
__ffs(unsigned long word) 是用來找一段 long 中,最高的位元是哪一位,程式碼當中用了多個判斷式。
其中原理為,當 word & 0xf 為 0 則表示在 4 位元內 word 的值都為 0 ,故 word 必大於

24 ,以此類推。

if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }

find_nth_bit 的程式碼運作原理為,先比較要找的數字有無超過限制的 size ,並檢查 size 的設置是否符合規範, GENMASK(h, l) 是將 hl 間的位元變為 1 , 故 valaddr hl 間的值,如果 val 有值,則利用 fns 找到為 1 的最高位元並回傳。