Try   HackMD

2024q1 Homework2 (quiz1+2)

contributed by < allenliao666 >

2024quiz1

測驗1

想法及思考

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







__node


cluster_a

node_t



node1

value

*next

*left

*right



node_t 為佇列中的節點結構,由 node_t 指標 *left 、 *right 和 *next 還有 long value 所組成。
其中 *next 用於連接下一個 node_t , value 為該節點的值。

所需函式

  • void list_add(node_t **list, node_t *node_t)
  • node_t *list_tail(node_t **left)
  • int list_length(node_t **left)
  • node_t *list_construct(node_t *list, int n)
  • void list_free(node_t **list)

以此串列為例:







eg



a

5



b

3



a->b





c

2



b->c





d

7



c->d





e

8



d->e





在測驗一的快速排序非遞迴實作中,首先 pivot 指向串列第一個節點,並且把該節點的 value 設定為比較對象。並把 L 和 R 指標分別指向待排序串列兩側的節點。







eg



pivot

pivot



a

5



pivot->a





L

L



L->a





R

R



e

8



R->e





b

3



a->b





c

2



b->c





d

7



c->d





d->e





接著依序和串列中的其他節點比較大小,將 value 小於 piovt 的節點加入 left 指向的串列,反之加入 right 指向的串列。最後使用 begin[] 和 end[] 兩個指標陣列紀錄 left 和 right 指向的兩個串列的開頭和尾端節點,其中 begin[i] 指向 left 的串列的開頭節點,end[i] 指向 left 的串列的尾端節點,begin[i + 2] 指向 right 的串列的開頭節點,end[i + 2] 指向 right 的串列的尾端節點。







eg



pivot

pivot



a

5



pivot->a





b1

begin[0]



c

2



b1->c





b2

begin[2]



e

8



b2->e





e1

end[0]



b

3



e1->b





e2

end[2]



d

7



e2->d





c->b





e->d





接著會針對 right 串列中重複執行上述的步驟,持續分割排序串列,並把分割排序後的串列的頭尾紀錄在對應的 begin[] 和 end[] 中,直到待排序的串列只有一個節點後開始合併。

改進空間

  • 原程式碼中,先宣告 begin[] 和 end[] 的大小為串列長度的兩倍,然而實際執行時,最多僅會將串列分割為 n 個子串列,故 begin[] 和 end[] 僅須為串列即可。
  • end[i] 的功能為記錄子串列的尾端節點,故可用 list_tail(&begin[i]) 取代。
  • (實驗待補)據 quick sort 性質,其最差狀況是 pivot 為最小值,導致該次迴圈的比較無意義,最差的時間複雜度為
    O(n2)

測驗2

想法及思考

Timsort 結合合併排序及插入排序的優點。 Timsort 執行過程如下:

  1. 首先使用 find_run() 尋找資料中已排序的子序列(以下稱為 run ),以避免浪費時間排序資料中已排序的部分。在尋找 run 的過程中,若遇到反向排序( value 由大到小)的部分時會將其反向排序成為 run 。
  2. 將 run 透過 pair 結構紀錄,其中 head 指向 run 的第一個節點, next 指向剩餘串列的第一個節點。
struct pair {
    struct list_head *head, *next;
};
  1. 透過堆疊儲存每一個 run ,以 tp ˋ指標指向最新的 run ,並用 result.head 的 prev 連接上一個加入堆疊的 run 。
  2. 透過 merge_collapse 確保堆疊頂端的3個 run 符合長度規則,若不符合則合併相鄰的2個 run ,藉此維持堆疊中 run 長度的平衡。

改進空間

2024quiz2

測驗1

想法及思考

題意:給定二元樹的前序及中序表示法,藉此重建二元樹。

測驗2

想法及思考

測驗3

想法及思考

題意:尋找記憶體位置中的第 n 個設定位元。

因為對 bitwise 操作一竅不通,故依序理解巨集。
GENMASK(h, l)

#define GENMASK(h, l) \
    (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

其中((~0UL) - (1UL << (l)) + 1) 即把右邊 l - 1個位元設為0,(~0UL >> (BITS_PER_LONG - 1 - (h))) 把左邊 h + 1個位元設為0。其手法類似 linux 中 bitops.h 的程式碼。

#define GENMASK(h, l) \
	(((~0UL) << (l)) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

#define GENMASK_ULL(h, l) \
	(((~0ULL) << (l)) & (~0ULL >> (BITS_PER_LONG_LONG - 1 - (h))))

其目的皆為設定 lh 位元為1,其餘皆為0。

BIT_WORD(nr)

#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)

換算 nr 個位元的長度為多少個 word。

#define BITS_TO_LONGS(nr)

#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_TYPE(long))

使用 DIV_ROUND_UP(n, d)BITS_PER_TYPE(long) 兩個巨集, DIV_ROUND_UP 的目的為將 n / d 的結果向上取至整數,例如42/5=8.4 代入 DIV_ROUND_UP 就會得到9。BITS_PER_TYPE(long) 則是計算 long 的位元數。故BITS_TO_LONGS(nr) 表示至多需要多少個 long 儲存 nr 。

__const_hweight8(w)

#__const_hweight8(w)                                              \
    ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
                     (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
                     (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
                     (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))

計算8個位元中共有多少個位元被設定(即為1)。

BITMAP_LAST_WORD_MASK(nbits)

#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))

這個巨集會用在當 nbit 不整除於 BITS_PER_LONG 時(即 nbit 非64的倍數),必須把多餘的部份湊成64位元,所以使用遮罩保護右邊 nbit % BITS_PER_LONG 的值。

FIND_NTH_BIT(FETCH, size, num)

這個巨集較複雜,故先從參數開始介紹:

  • FETCH : 記憶體位置,並從該位置開始尋找設定的位元
  • size(sz) : 尋找的範圍
  • num : 尋找的目標

該巨集在 size 範圍內從 FETCH 開始尋找第 num 個設定的位元。 idx 為 word 的索引。
分為以下幾種狀況:

  1. idx * BITS_PER_LONG + nr >= sz : 當 idx * BITS_PER_LONG 長度超過 sz ,表示尋找範圍已經超過 size ,所以 goto out 並回傳 sz 。
  2. w > nr : w 為該 word 中設定的位元數,當 w 大於 nr 表示目標就在這個 word 中,故 goto found 利用 fns 巨集和 word 偏移地址即可得到目標。
#define FIND_NTH_BIT(FETCH, size, num)                          \
    ({                                                          \
        unsigned long sz = (size), nr = (num), idx, w, tmp;     \
                                                                \
        for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) { \
            if (idx * BITS_PER_LONG + nr >= sz)                 \
                goto out;                                       \
                                                                \
            tmp = (FETCH);                                      \
            w = hweight_long(tmp);                              \
            if (w > nr)                                         \
                goto found;                                     \
                                                                \
            nr -= w;                                            \
        }                                                       \
                                                                \
        if (sz CCCC BITS_PER_LONG)                              \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })