2024q1 Homework2 (quiz1+2)

contributed by < v0103 >

第一周測驗題

測驗1

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

因為這裡使用的是單向鏈結串列，因此需要確保傳入的指標在該函式執行完依舊指向串列的頭，參考你所不知道的 C 語言: linked list 和非連續記憶體提到的 indirect pointer，該函式用 node_t **left，而非 node_t *left。由於 left 是指向 list 的指標，*left 是 list ，*left->next 則是 node1，left = &(*left->next) 就會將 left 更新為 node1，經過while迴圈不斷往後找就可以找到串列的尾。

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

list_length 函式要計算串列總長，跟上面的 list_tail 一樣，使用 while 迴圈不斷的找下一個 node ，解題思路跟上面一樣，所以 BBBB 會是 *left->next。

quick_sort

原方法 Optimized QuickSort — C Implementation (Non-Recursive) 首先選定最左邊的數字為 pivot，分別使用 L 由左往右移動，R 由右往左移動，在 LR 移動過程會把小於 pivot 的數字放到左側，大於的則放到右側，最後 LR 相遇後再把 pivot 放到該點，以此完成排序。再來就是對 pivot 右側做排序，右側排序完了再對 pivot 左側做排序。

有了原方法的排序概念接下來看看題目 quick_sort 和原方法有何異同。

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

這裡一樣使用 begin 和 end 作為堆疊，去儲存尚未排列好的序列。

node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;

一樣選擇 L 作為 pivot，value 則是 pivot 的值。這邊多了一個 node_t *p 指向 pivot->next 目前還不知道其作用。

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

可以看到這是一個 while 迴圈，運行到 p==NULL 才會結束，每次會用新指標 n 來存取 p 所指向的節點，n->value > value ? &right : &left 這邊判斷該次迴圈所指到的節點是否大於 pivot ，大於則會執行 list_add(&right, n) 將該節點放到 right 這個串列，反之，則放到left 串列。看起來這個迴圈的作用就是走訪串列，並將小於 pivot 的節點放左側，大於 pivot 的節點放右側。因此可以判斷出 CCCC 為 p->next。

n 指向 p 的位置後 p 指向 p->next。

n->value < pivot->value，所以 n 要放到 left 串列。

下一輪迴圈 n 指到 3，因此將 3 也放到 left。

最後會將原串列拆成三組串列。

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

left = right = NULL;
i += 2;

有了 left right兩個串列，再來要將他們存起來。begin end 會做為下一輪迴圈的 L R，因此如果 begin[i] 是 left 可以得知 DDDD 是 list_tail(&left)，同理 EEEE 是 list_tail(&right)。最後 i += 2 所以跟原方法一樣是先排序右側。

TODO : 用list API改寫，提出可避免最差狀況的快速排序實作

測驗2

首先在閱讀題目時講到 minrun 的選擇策略時，有個令我疑惑的點。

顯然，選擇 minrun 的策略是 Timsort 的關鍵，其中一個實務上的方法是，取資料長度 N 的前 6 位，若剩餘位中任何一位被設置，則加 1。這主要是為了在處理隨機數列時，使得 N 能夠被 minrun 切分成 2 的冪的 run，以便在合併時達到最佳平衡。

其中，取資料長度 N 的前 6 位我一直看不懂是甚麼意思，google 後才知道是將資料長度 N 轉換為二進位表示，並取其前 6 位的意思。
以題目的例子 N = 2112為例，2112 換成二進位是 100001000000 ，取其前六位也就是 100001 = 33，剩餘的六位都是 0，因此選擇 33 作為 minrun。

---

運行原理

我解這題的方法是先大略理解了 Timsort 的原理，然後按照前後的結構來處理問題，先填補空缺的部分，最後再完全理解每個函式的作用。

首先，我看到了 timsort 函式，首先將原本的雙向鏈結串列轉換為單向的，然後使用 find_run 函式將原始串列劃分為多個 run。在這個拆分的過程中，同時使用 merge_collapse 函式來確保堆疊上的 run 長度保持平衡。接著，使用 merge_force_collapse 函式確保 run 的數量少於 3。如果 run 的數量剩餘 2，則執行 merge_final 函式進行最後的合併。同時，裡面包含一個 build_prev_link 函式，將原本的單向鏈結串列轉換為雙向的。如果 run 的數量剩餘 1，則直接執行 build_prev_link 函式。

我覺得一個有趣的地方是，在 find_run 函式中，將 run 的長度存儲在 head->next->prev 中。這樣做的好處是，在進行合併時可以直接讀取兩個 run 的長度，而不需要額外記錄或者重新掃描一次。

解題思路

AAAA BBBB CCCC 都在 merge 函式。

在 merge 函式中 tail 負責指向串列的尾部，讓下一次迴圈比較完的較小值可以知道要接在哪，所以 tail 初始值應該指向 head，AAAA 為 &head。

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

在這段程式碼中，當 a 小於 b 時，在第一輪迴圈中，會將 *tail，也就是 head，設定為 a。接著，為了確保下一輪迴圈中較小的值能夠接在 a 後面，我們需要更改 tail 的指向位置。因此，BBBB 為 &a->next。

if (cmp(priv, a, b) <= 0) {
    *tail = a;
    tail = BBBB;
    a = a->next;
    if (!a) {
        *tail = b;
        break;
    }
}

同理，CCCC 為 &b->next。

else {
    *tail = b;
    tail = CCCC;
    b = b->next;
    if (!b) {
        *tail = a;
        break;
    }
}

前面有提到build_prev_link 函式的作用是將原本的單向鏈結串列轉換為雙向的。根據註解可以得知這兩行的作用是執行最後一步，讓串列的頭尾相接，因此 DDDD 為 tail->next， EEEE 為 head->prev。

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

TODO : 提出改進方案，整合進lab0-c

---

第二周測驗題

測驗1

運行原理

解題思路

測驗2

測驗3

運行原理

要找出第 N 個設定的位元，要先能找出第 1 個設定的位元，所以看到 __ffs 函式，使用多個 mask 逐步找出 word 中第 1 個設定的位元。我挑其中一個來講解。

下面條件若成立，表示 word 第 1 個設定的位元不在後 16 位，所以 num 計數要加 16 並且把 word 右移 16 位，檢查更高位元。

if ((word & 0xffff) == 0) {
    num += 16;
    word >>= 16;
}

知道怎麼找第 1 個設定的位元，要找到第 N 個也就沒問題了。
fns 函式使用 while 迴圈，找到 word 第 1 個設定的位元後，再使用 __clear_bit 清除該位元，下一輪迴圈找到的就會是第 2 個設定的位元，以此循環便能找到第 N 個。

static inline unsigned long fns(unsigned long word, unsigned int n)
{
    while (word) {
        unsigned int bit = __ffs(word);
        if (n-- == 0)
            return bit;
        __clear_bit(bit, &word);
    }

    return BITS_PER_LONG;
}

解題思路

前面運行原理舉的例子是檢查後 16 位，mask 是 0xffff，所以這個檢查後 32 位的 mask AAAA 是 0xffffffff。

#if BITS_PER_LONG == 64
    if ((word & AAAA) == 0) {
        num += 32;
        word >>= 32;
    }
#endif

從 fns 函式可以知道，nr 是第 1 個設定的位元的位置，BIT_MASK 的作用是把 nr 的位元設為 1 其他設為 0，所以要將 p 的第 nr 個位元位元清除，BBBB 會是 ~mask。

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= BBBB;
}

如果 size > BITS_PER_LONG 時，會執行此巨集。

#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;                                                     \
    })