2024q1 Homework2 (quiz1+2)

contributed by < allenliao666 >

2024quiz1

測驗1

想法及思考

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

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)

以此串列為例：

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

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

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

改進空間

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

測驗2

想法及思考

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

1. 首先使用 find_run() 尋找資料中已排序的子序列(以下稱為 run )，以避免浪費時間排序資料中已排序的部分。在尋找 run 的過程中，若遇到反向排序( value 由大到小)的部分時會將其反向排序成為 run 。
2. 將 run 透過 pair 結構紀錄，其中 head 指向 run 的第一個節點， next 指向剩餘串列的第一個節點。

struct pair {
    struct list_head *head, *next;
};

3. 透過堆疊儲存每一個 run ，以 tp ˋ指標指向最新的 run ，並用 result.head 的 prev 連接上一個加入堆疊的 run 。
4. 透過 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))))

其目的皆為設定 l 到 h 位元為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;                                                     \
    })