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