測驗

$\alpha -1$

解釋上述程式碼運作原理

• st_rotate_left

測驗

$\alpha -2$

撰寫時間量測程式碼

1. 引入資料結構 timespec，實作計算時間消耗的函示 diff_in_second：

struct timespec start, end;
double cpu_time1, cpu_time2;

static double diff_in_second(struct timespec t1, struct timespec t2)
{
    struct timespec diff;
    if (t2.tv_nsec-t1.tv_nsec < 0) {
        diff.tv_sec  = t2.tv_sec - t1.tv_sec - 1;
        diff.tv_nsec = t2.tv_nsec - t1.tv_nsec + 1000000000;
    } else {
        diff.tv_sec  = t2.tv_sec - t1.tv_sec;
        diff.tv_nsec = t2.tv_nsec - t1.tv_nsec;
    }
    return (diff.tv_sec + diff.tv_nsec / 1000000000.0);
}

2. 量測 insert 與 remove 消耗時間：

clock_gettime(CLOCK_REALTIME, &start);
for (long int j = 0; j < num; ++j) {
    treeint_insert(rand() % (num - 1));
}
clock_gettime(CLOCK_REALTIME, &end);
t1 = diff_in_second(start, end);

其中 num 為需要 insert/remove 的節點總數。對應 remove 的部分：

clock_gettime(CLOCK_REALTIME, &start);
for (long int k = 0; k < num; ++k) {
    int v = rand() % (num - 1);
    treeint_remove(v);
}
clock_gettime(CLOCK_REALTIME, &end);
t2 = diff_in_second(start, end);

3. 使用 numpy 與 matplotlib 繪製結果：

import numpy as np
import matplotlib .pyplot as plt

if __name__ == "__main__":
    output = np.loadtxt('data.txt', dtype='float').T

    X = output[0]
    fig, ax = plt.subplots(1, 1, sharey=True)
    ax.set_title('Time consumption', fontsize=16)
    ax.set_xlabel('numbers of insert/remove', fontsize=16)
    ax.set_ylabel('time (s)', fontsize=16)

    ax.plot(X, output[1], marker='+', markersize=3, label='insert')
    ax.plot(X, output[2], marker='*', markersize=3, label='remove')
    ax.legend(loc='upper left')

    plt.show()

4. 實驗結果：

• 硬體設備資訊

MacBook Pro (16-inch, 2019)
處理器：2.3 GHz 8 核心 Intel Core i9

測驗

$\beta -1$

觀察數值為 2 的冪的倍數時，其二進為表示法的最低

$n-1$ 的位元為 0。因此數值

$x$ 以 2 的冪做向上對齊時 (align up)，考慮以下情況：

align_up(120, 4) 輸出結果為 120

$\to$ 1111000
align_up(121, 4) 輸出結果為 124

$\to$ 1111100
align_up(122, 4) 輸出結果為 124

$\to$ 1111100
align_up(124, 4) 輸出結果為 124

$\to$ 1111100

1. 120 已經是 align_up(120, 4) 的結果。
2. 121 做完 align_up(121, 4) 後為二進位 1111100，既然是向上對齊，考慮加上對齊值
   $2^n$ ，然後對對齊值低於
   $n$ 的位元遮蔽：
   (121 + 4) &~ (4-1) = 124
3. (122 + 4) &~ (4-1) = 124
4. (123 + 4) &~ (4-1) = 124
5. (124 + 4) &~ (4-1) = 128，然而 124 做 align_up(124, 4) 是 124。觀察 124 + 4 的二進位，其第 2 位元發生進位，為避免此情況，改寫為 (124 + (4-1)) &~ (4-1) = 124

完整程式碼：

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {  /* power of two? */
        return (((sz) + (mask)) & ~(mask));       
    }
    return (((sz + mask) / alignment) * alignment);
}

測驗

$\gamma -1$