2023q1 Homework4 (quiz4)

測驗一

程式碼原理

答案

• AAAA =
• BBBB =
• CCCC =
• DDDD =
• EEEE =
• FFFF =
• GGGG =

---

測驗二

Timsort 原理

原始程式碼

Timsort 是混合 insertion sort 與 merge sort 的 stable 排序演算法，主要原理是將資料分割成小區塊 runs，將這些 runs 用 insertion sort 排序，最後將這些 runs 用 merge sort 合併。

merge_rule

Timsort 會將 runs 放入堆疊中，為了達到 balanced merges，也就是合併時兩個 runs 大小差不多，所以限制當 top-2 的 run 比 top 的 run + top-1 的 run 的長度較大時，才能合併。

$i:|Z|>|Y|+|X|$

$ii:|Y|>|X|$

return run_length(stack[top]) > run_length(stack[top - 1]) ||
       run_length(stack[top]) + run_length(stack[top - 1]) >
       run_length(stack[top - 2]);

next_partition

這裡主要是將資料分割成 runs ，去計算 runs 的數量，因為需要所有的 runs 都是遞增的，所以會判斷是否為遞增的序列，若不是，則將該 runs 反轉成遞增的序列。

if (cmp(cur, next)) {
    while (next < last && cmp(cur, next)) {
        ++run_len;
        cur += size;
        next += size;
    }
} else {
    while (next < last && !cmp(cur, next)) {
        ++run_len;
        cur += size;
        next += size;
    }
    __reverse(first, next, size);
}

若是 run 的長度小於 MIN_RUN ，則會用 insertion sort 去排序，當長度短且為排序過的序列，用 insertion sort 的效率會較好。

if (next < last && run_len < MIN_RUN) {
    last = first + MIN_RUN * size < last ? DDDD : last;
    __insertion_sort(first, last, size, cmp);
    return (last - first) / size;
}

merge

• merge
  這個函式就是將兩個 runs 進行合併。

• inplace_merge
  會有多一個 inplace_merge 函式，主要是因為當一個 run 裡面包含兩個不同的 run 時，不需要額外的空間來儲存合併後的 run ，實作起來會較為簡單。

首先初始狀態會宣告兩個變數 cur1, cur2 分別指向 first1, first2 。

再來先將 cur1 右移，找出第一個 > cur2 的值，也就是找出小區塊 1, 3。

while (cur_1 < last_2 && !cmp(cur_2, cur_1))
    cur_1 += size;

再將 cur2 右移，找出第一個 > cur1 的值，也就是找出小區塊 2, 4。

while (cur_2 < last_2 && cmp(cur_2, cur_1))
    cur_2 += size;

最後進行 3 次 reverse，第一次做 cur1 到 first_2 - 1 的 reverse 。

__reverse(cur_1, first_2, size);

第二次做 first_2 到 cur_2 - 1 的 reverse 。

__reverse(first_2, cur_2, size);

第三次做 cur_1 到 cur_2 - 1 的 reverse 。

__reverse(cur_1, cur_2, size);

最後移動 first_1, first_2 ，再開始新的一輪直到合併成一個 run 。

first_1 = cur_1 + (cur_2 - first_2);
first_2 = cur_2;

答案

• AAAA = __reverse(cur_1, cur_2, size)
• BBBB = top - 1
• CCCC = top - 2
• DDDD = first + MIN_RUN * size
• EEEE = top--
• FFFF = top++
• GGGG = stack[top-1].last = stack[top].last

---

測驗三

程式碼原理

RB_LOG2_MAX_NODES

在 process 中，最多有 1 << (sizeof(void *) << 3) / sizeof(rb_node(x_type)). 個節點，所以 RB_LOG2_MAX_NODES 就是上式取 log ，也就是：

$log$(1 << (sizeof(void *) << 3) / sizeof(rb_node(x_type)))
=

$log$(1 << (sizeof(void *) << 3) -

$log$(sizeof(rb_node(x_type)))
= RB_LOG2_MAX_MEM_BYTES -

$log$(sizeof(rb_node(x_type)))

所以

$log$(sizeof(rb_node(x_type))) 就等於下式

sizeof(void *) >= 8 ? 4 : sizeof(void *) >= 4 ? 3 : 2 - 1

sum_subtree

範例輸入為：7, 11, 1, 99, 22, 33, 44, 9, 3, 5

判斷若是左節點沒有子節點，表示為最左節點，最左節點是最小的值，則印出。

if (!rbtn_left_get(node_t, link, node))
    goto do_print;

這裡利用左節點的最右子節點來紀錄前一個較大的節點，於是下個迴圈會輸出最小的節點，然後進到 for 迴圈內就會判斷是否要透過剛剛紀錄的值回到最小節點的前一個節點，再將用來紀錄的最右子節點設成 NULL。

for (pre = rbtn_left_get(node_t, link, node);
    rbtn_right_get(node_t, link, pre) &&
    rbtn_right_get(node_t, link, pre) != node;
    pre = rbtn_right_get(node_t, link, pre)){}

if (!rbtn_right_get(node_t, link, pre)) {
    rbtn_right_get(node_t, link, pre) = node;
    node = rbtn_left_get(node_t, link, node);
} else {
    rbtn_right_get(node_t, link, pre) = NULL;
    do_print:
        result += node->value;
        printf("value: %d\n", node->value);
        node = rbtn_right_get(node_t, link, node);
}

答案

• HHHH = 3
• IIII = 2
• JJJJ = rbtn_left_get
• KKKK = rbtn_right_get
• LLLL = rbtn_right_get