2024q1 Homework4 (quiz3+4)

contributed by < HenryChaing >

第三週測驗題

測驗二

參考： CA2023-Lab02, rv32emu

CPU 週期數量

在測驗二當中共有兩種不使用除法及模數運算來得到商及餘數的方法，我們會針對這兩種方法進行分析，分別會分析他們的組譯結果以及執行時所需要的 CPU 週期。

在分析中我所使用到的工具為 rv32emu , GNU toolchain ，我們會分析經由跨平台編譯器組譯後的 RISC-V 組合語言程式，以及在 rv32emu 運行時程式在模擬器當中所使用的時脈週期數量。

riscv-none-elf-gcc , riscv-none-elf-objdump

首先 riscv-none-elf-gcc 是我們的跨平台編譯器，透過我們給定的 C 語言原始碼，它可以幫我們組譯成目標檔或是編譯成 elf 執行檔。為了分析編譯後的結果，我們會利用 riscv-none-elf-objdump 幫我們從執行檔中的機器碼還原顯示成 RISC-V 組合語言程式。

RISC-V 組合語言程式

運用除法運算的程式碼

$ riscv-none-elf-objdump -d mod3_v1.o

mod3_v1.o:     file format elf32-littleriscv

Disassembly of section .text:

00000000 <divmod_10>:
   0:   ff010113                add     sp,sp,-16
   4:   00812423                sw      s0,8(sp)
   8:   00058413                mv      s0,a1
   c:   00a00593                li      a1,10
  10:   00112623                sw      ra,12(sp)
  14:   00912223                sw      s1,4(sp)
  18:   01212023                sw      s2,0(sp)
  1c:   00060493                mv      s1,a2
  20:   00050913                mv      s2,a0
  24:   00000097                auipc   ra,0x0
  28:   000080e7                jalr    ra # 24 <divmod_10+0x24>
  2c:   00a42023                sw      a0,0(s0)
  30:   00a00593                li      a1,10
  34:   00090513                mv      a0,s2
  38:   00000097                auipc   ra,0x0
  3c:   000080e7                jalr    ra # 38 <divmod_10+0x38>
  40:   00a4a023                sw      a0,0(s1)
  44:   00042583                lw      a1,0(s0)
  48:   00812403                lw      s0,8(sp)
  4c:   00c12083                lw      ra,12(sp)
  50:   00412483                lw      s1,4(sp)
  54:   00012903                lw      s2,0(sp)
  58:   00050613                mv      a2,a0
  5c:   00000537                lui     a0,0x0
  60:   00050513                mv      a0,a0
  64:   01010113                add     sp,sp,16
  68:   00000317                auipc   t1,0x0
  6c:   00030067                jr      t1 # 68 <divmod_10+0x68>

Disassembly of section .text.startup:

00000000 <main>:
   0:   fe010113                add     sp,sp,-32
   4:   00812c23                sw      s0,24(sp)
   8:   01212823                sw      s2,16(sp)
   c:   01312623                sw      s3,12(sp)
  10:   00112e23                sw      ra,28(sp)
  14:   00912a23                sw      s1,20(sp)
  18:   00000413                li      s0,0
  1c:   000009b7                lui     s3,0x0
  20:   01300913                li      s2,19

00000024 <.L5>:
  24:   00a00593                li      a1,10
  28:   00040513                mv      a0,s0
  2c:   00000097                auipc   ra,0x0
  30:   000080e7                jalr    ra # 2c <.L5+0x8>
  34:   00050493                mv      s1,a0
  38:   00a00593                li      a1,10
  3c:   00040513                mv      a0,s0
  40:   00000097                auipc   ra,0x0
  44:   000080e7                jalr    ra # 40 <.L5+0x1c>
  48:   00050593                mv      a1,a0
  4c:   00048613                mv      a2,s1
  50:   00098513                mv      a0,s3
  54:   00140413                add     s0,s0,1
  58:   00000097                auipc   ra,0x0
  5c:   000080e7                jalr    ra # 58 <.L5+0x34>
  60:   fd2412e3                bne     s0,s2,24 <.L5>
  64:   01c12083                lw      ra,28(sp)
  68:   01812403                lw      s0,24(sp)
  6c:   01412483                lw      s1,20(sp)
  70:   01012903                lw      s2,16(sp)
  74:   00c12983                lw      s3,12(sp)
  78:   00000513                li      a0,0
  7c:   02010113                add     sp,sp,32
  80:   00008067                ret

運用右移運算替代除法之程式

$ riscv-none-elf-objdump -d mod3_v2.o

mod3_v2.o:     file format elf32-littleriscv

Disassembly of section .text.startup:

00000000 <main>:
   0:   ff010113                add     sp,sp,-16
   4:   00812423                sw      s0,8(sp)
   8:   00912223                sw      s1,4(sp)
   c:   01212023                sw      s2,0(sp)
  10:   00112623                sw      ra,12(sp)
  14:   00000413                li      s0,0
  18:   00000937                lui     s2,0x0
  1c:   01400493                li      s1,20

00000020 <.L2>:
  20:   40145793                sra     a5,s0,0x1
  24:   40345593                sra     a1,s0,0x3
  28:   00f585b3                add     a1,a1,a5
  2c:   008585b3                add     a1,a1,s0
  30:   00359593                sll     a1,a1,0x3
  34:   0075d593                srl     a1,a1,0x7
  38:   40b00633                neg     a2,a1
  3c:   00567613                and     a2,a2,5
  40:   00161613                sll     a2,a2,0x1
  44:   40c40633                sub     a2,s0,a2
  48:   00090513                mv      a0,s2
  4c:   00140413                add     s0,s0,1
  50:   00000097                auipc   ra,0x0
  54:   000080e7                jalr    ra # 50 <.L2+0x30>
  58:   fc9414e3                bne     s0,s1,20 <.L2>
  5c:   00c12083                lw      ra,12(sp)
  60:   00812403                lw      s0,8(sp)
  64:   00412483                lw      s1,4(sp)
  68:   00012903                lw      s2,0(sp)
  6c:   00000513                li      a0,0
  70:   01010113                add     sp,sp,16
  74:   00008067                ret

這是還未經過連結器的目標檔還原成 RISC-V 程式碼的結果，這些程式的目的皆是處理 0~19 對整數十進行除法運算。以下方程式來說重點在位址 0x20 ~ 0x48 ，這裡是處理除法的段落，因此可以推斷在進行一次除法運算需要這 11 個指令，會比上方除法運算要快上許多。

rv32emu

接著要看實際運行狀況，我們會讓可以運行 elf 執行檔的 rv32emu 來運行上方編譯完成的兩個執行檔。為了得到正確的時脈週期，這裡會加入由 getcycle.S 提供組合語言撰寫成的時間函式，得到各自進行 20 次除法運算後所使用到的時脈週期。

運用除法運算

cycle count: 26417
inferior exit code 0

運用右移運算替代除法

cycle count: 25892
inferior exit code 0

可能是二十次測驗效果還不夠顯著，但運用右移運算只須原本除法運算

\frac{98}{100}

所使用的時脈週期。

mod5 實作

參考： Modulus without Division

在這項實作中，我們會先處理模 15 的運算，再得到模 5 的結果。
在參考中有提到，針對

2^{n} - 1

的模數運算，我們可以將其改成這項對計算機友善的公式：

a \mod (2^{n} - 1) = ((a / 2^{n}) + (a \mod 2^{n})) \mod (2^{n} - 1)

其中除以

2^{n}

之運算可以替換為右移

n

，

m o d

運算也可以用 & 運算達成。但由於

(a / 2^{n}) + (a \mod 2^{n})

並未必小於

2^{n} - 1

，因此這項運算須重複至原本

a

可能之最大值也須小於

2^{n} - 1

，再者這項運算等同於計算

a

以二進位表示時 1 的數量，因此我們也可以改變每次位移以及 and 運算的

n

值。

uint32_t mod15( uint32_t a ) {
    a = (a >> 16) + (a & 0xFFFF); /* maximun value: 0x1FFFE */
    a = (a >>  8) + (a & 0xFF);   /* maximun value: 0x2FD */
    a = (a >>  4) + (a & 0xF);    /* maximun value: 0x3C */
    return (a >>  4) + (a & 0xF); /* maximun value: 0xF */
}

以上是我在參考範例程式後改寫的版本，可以將模數的範圍縮至 0~15 。

uint32_t mod5( uint32_t a ) {
    a = (a >> 16) + (a & 0xFFFF); /* maximun value: 0x1FFFE */
    a = (a >>  8) + (a & 0xFF);   /* maximun value: 0x2FD */
    a = (a >>  4) + (a & 0xF);    /* maximun value: 0x3C */
    a = (a >>  4) + (a & 0xF);    /* maximun value: 0xF */
    if(a<5)return a;
    if(a<10)return a-5;
    return a-10;
}

由於

(a \mod 15) \mod 5 \equiv a \mod 5

，因此模 5 的函式即是將模 15 後的結果再模 5 ，並且在已知範圍為 0~15 之情形下利用簡單的減法減去商達到模數效果。

mod9 實作

參考： Hacker's Delight

參考過 Hacker's Delight 對於 Remainder by Summing digits 的描述後，我透過它舉證出的公式，利用模同餘不斷減少數字的值，直到接近除數才用條件式判斷後減掉商數的方式得出餘數值。而這裡會著重在介紹模同餘的運算方式。

這次模同餘我主要運用到的是

2^{6} \equiv 1 (m o d 9)

這項轉換完成。由於這項公式，我可以將

n \cdot 2^{6} (m o d 9)

直接轉換成

n (m o d 9)

。因此

[(r & 0 x 003 F) + (r ≫ 6)] (m o d 9)

會等價於

r (m o d 9)

，而經過這個方法的不斷簡化，我將數值縮小到了小於一千的正整數。

最後是透過查表法的方式找到結果，也就是將這近千個整數建立對應到的餘數的陣列，這樣可以大幅減少運算。

commit 70103d0

int remu9(unsigned n) {
 int r;
 static char table[510] = {0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
 0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5};
    
 r = (n & 0x0FFF) + (n >> 12); // 0 to 1FFFFE.
 r = (r & 0x0FFF) + (r >> 12); // 0 to 11FD.
 r = (r & 0x0FFF) + (r >> 12); // 0 to 1FE.
 return table[r];
}

測驗三

程式碼解說

這些函式的目的是要計算整數取

\log_{2}

後所得到的數值（小數無條件捨去），因為計算以二為底的對數若只觀察二進位的第一個設定位元 (set bit) ，則對數值剛好會等於該數值以二進位表示的指數值。我們也使用這個特性估算出整數以二為底的對數值。

commit ffca224

方法一 (line 5)

透過不斷將數值除以二（右位移）的方式，找到二進位數值第一個設定位元的位置，並用變數 log 紀錄再回傳對數值。

方法二 (line 15)

假設輸入的數值不為零，則二進位數值可以表示成二的冪數列和，而這個函式會同樣將第一個設定位元移至 LSB 的位置，最後回傳對數值。

方法三 (line 41)

這裡直接使用 GNU C 中的擴充函式 clz ，這個函式可以計算在第一個設定位元前有幾個零，因此我們也用這個函式反推出對數值。

測驗四

程式碼解說

EWMA 公式：

S_{t} = {\begin{cases} α \cdot Y_{t} + (1 - α) \cdot S_{t - 1}, & t > 0 \\ Y_{0}, & t = 0 \end{cases}

結構變數 ewma

struct ewma {
    unsigned long internal;
    unsigned long factor;
    unsigned long weight;
};

這個是用來計算指數加權移動平均所使用到的結構變數， internal 紀錄的是當下的平均值，而 weight 是歷史資料加權降低的程度，最後是公式沒有出現的 factor 變數，我認為是可以讓原始資料放大的參數。

結構變數初始化

void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
    if (!is_power_of_2(weight) || !is_power_of_2(factor))
        assert(0 && "weight and factor have to be a power of two!");

    avg->weight = ilog2(weight);
    avg->factor = ilog2(factor);
    avg->internal = 0;
}

為了解說接下來 EWMA 每一回合的處理，需要特別注意的是 weight 及 factor 的成員變數皆經過對數化，為的是方便待會每一回合的平移步驟，省去計算量龐大的乘除法。

EWMA 計算

struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
    avg->internal = avg->internal
                        ? (((avg->internal << avg->weight) - avg->internal) +
                           (val << avg->factor)) >> avg->weight
                        : (val << avg->factor);
    return avg;
}

這裡應用的就是 EWMA 的公式，函式由於 weight 及 factor 都經過對數化，所以平移可以視為乘除運算。其中較為特別的是每次資料點會先乘以 factor 倍才代入公式當中。還有指數權重較不直觀，但若只觀察資料點會發現指數權重是

\frac{1}{w e i g h t}

，反之歷史資料的權重是

1 - \frac{1}{w e i g h t}

。

Linux 核心 EWMA 應用

部份節錄自 linux/…/dynack.c

我還未研究 git log 因此以下行為視同舉燭。

Linux 核心在 ath_dynack_compute_to 這個計算 station ack time out 的函式中，採用了 EWMA 的方式來更新 station ack time out 的值，而這個 station 是用來儲存連線裝置的狀態，每回合計算的 ack_to 是由 ack_ts = ack_ts - st_ts->tstamp - st_ts->dur 決定。

而 EWMA 更新的公式則是：

S_{t} = \frac{1}{4} \cdot ​ S_{t - 1} + \frac{3}{4} \cdot a c k t o

其中

S_{t}

代表 station 中儲存的 time out 時間。

測驗五

程式碼解說

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | (x > 1) ) + 1;       
}

這個與測驗三中的方法二實作上有相似之處，差別在於採用沒有分支的方式（即沒有 if , while 等組譯後會產生分支的指令），實作方式是會把位移量保留在 r 變數當中。

其中 return 的值很特別，首先 r|shift 是記錄上二行 shift 的結果，而 (x > 1) 則是再處理

x >= 2^{0}

的案例。而最後的加一要與 x-- 一同觀察，這裡是在處理對數值無條件進位的地方，加一就是無條件進位的動作，而 x-- 則是要處理 2 的冪數字的例外。

Linux 核心所應用的 ceil_log2

節錄自 linux/…/thuge-gen.c

int ilog2(unsigned long v)
{
	int l = 0;
	while ((1UL << l) < v)
		l++;
	return l;
}

應用的場合是在計算任務的粒度（granularity），因應可用處理器數目的變更而重新計算，因為粒度與可用處理器之間的關係並非線性，因此用 ilog 進行模擬。

這個函式功能與測驗五的 ceil_ilog2 相同，計算位移的方式同測驗三的方法一，差別在於無條件進位的處理位在進入迴圈的判斷式，除了 2 的冪外它會比方法一還要多算一位，由此來處理無條件進位。

第四週測驗題

測驗一

程式碼解說

int total_hamming_distance(int* nums, int numsSize)
{
    int total = 0;;
    for (int i = 0;i < numsSize;i++)
        for (int j = 0; j < numsSize;j++)
            total += __builtin_popcount(nums[i] ^ nums[j]); 
    return total >> 1;
}

首先兩個迴圈是為了計算每個配對之間的漢明距離，重點在於 popcount 以及互斥或， popcount 可以計算變數以二進位表示時有多少設置位元，而互斥或則是運用其特性會將對應位置相異的位元設為一，反之則為零。因此每個配對即是將對應位置相異的位元數量做計算，最後儲存到 total 變數中。而 total 之所以要右移一，則是要刪掉重複比較的配對。

Total Hamming Distance 改進

commit 36ac28c

int hamming_distance_linear(int* nums, int nums_size){
    int iteration = 0, distance = 0;
    for (__uint32_t i = 1; iteration < 32; i<<=1)
    {
        int ones = 0;
        for (int j = 0; j < nums_size; j++)
        {
            __uint32_t bin = nums[j];
            if((bin & i) == i){
                ones++;
            }
        }
        distance += ones*(nums_size-ones);
        iteration++;
    }
    return distance;
}

我使用了測驗一最後歸納的方法實作了線性時間複雜度的漢明距離函式。而這個作法的原理是所有整數一起作逐位元觀察，並且將觀察結果加入總和變數，當在觀察第

n

個位元（

n

屬於0到31）時，我們會統計所有整數中設置位元的數量（

s

），對每一個設置位元來說與其相異的位元共有

s i z e - s

個（

s i z e

為陣列長度），因此對這個整數來說漢明距離共增加

s i z e - s

，並且這樣的整數共有

s

個，因此這回合漢明距離共增加

s * (s i z e - s)

，而這樣的計數共要進行

n

回合。

接著來計算時間複雜度，引用剛才的變數，時間複雜度可記為

O (n \times s i z e)

，其中

n

為常數 32 ，因此時間複雜度可簡化為

O (s i z e)

，所以這是個執行時間與整數陣列大小有關的函式。

測驗二

程式碼解說

模 3 運算

static inline int mod3(unsigned n)
{
    static char table[33] = {
        2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0,
        1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1,
    };

    n = __builtin_popcount(n ^ 0xAAAAAAAA);
    return table[n];
}

這裡不解釋作者已經舉證出的模三可以透過

p o p c o u n t (n \oplus 0 x A A A A A A A A) - 1

來簡化數字成接近模數結果的值

r e s u l t + 3 t

(

t

屬於整數)，為了直接得到

r e s u l t

，我們現在已知經過位元總和運算後，

n

會介於 0~32 ，為了避免加入不必要的運算，我們透過查表法來解決找到

r e s u l t

的問題。

為了方便理解查表法以及作者的公式，我將程式碼改成如下等價表示：

static inline int mod3(unsigned n)
{
    static char table[33] = {
        0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0,
        1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2,
    };

    n = __builtin_popcount(n ^ 0xAAAAAAAA) -1;
    return table[n];
}

透過作者的公式可知，經過位元總和的運算後

n

為

r e s u l t + 3 t

(

t

屬於整數) 並且介於 0~32 ，因此我們建立了對應這 33 個數字之餘數陣列，可以直接從陣列找到這個數字對應的餘數。

測驗三

程式碼解說

Xtree code

首先這棵樹是一棵二元搜尋樹，也有樹基本的插入、刪除操作，也有相似於高等平衡樹的地方，例如紀錄平衡值的 hint 值，以及平衡樹的旋轉操作。其中旋轉操作在對樹進行插入及刪除等會變更樹結構的操作時會觸發。

程式碼改進

commit ce1067e

我發現之問題如下，可能是我理解錯誤，但觀察程式碼時發現旋轉的操作並未減少樹高，也就是沒有達到平衡的目的。 Xtree 中的旋轉分成兩個案例，分別是左傾以及右傾，他們分別對應到 AVL Tree 中的 LL 以及 RR 案例。但是這樣會產生一個缺點，也就是 AVL Tree 中的 LR 以及 RL 案例發生時，旋轉也會執行但是對樹的平衡沒有幫助（高度不變且依舊不平衡）

Xtree (初始狀態)

插入值 3 節點

對 5 進行旋轉

這項插入對 Xtree 造成左傾的不平衡，因此會進行旋轉調整，但是觀察結果會發現樹從左傾變成了右傾，並且高度也不變。而之所以會產生這個結果是因為 LL 所對應的旋轉方式無法解決 LR 案例的不平衡。

解決方式-引入新的旋轉方式

於是我引入了 AVL Tree 使用的LR 及 RL 案例所對應的旋轉方式，這項改動雖然有助於樹的平衡，理想上讓插入、刪除、尋找的時間複雜度正比於二元完整樹樹高，也就是

O (l o g n)

。但實際上插入以及刪除時間成本應該會上升，因為旋轉的操作變得更為複雜，這再接下來的結果分析會看出明顯結果，需要旋轉的插入以及刪除會比沒有旋轉發生的案例執行時間多上近 5 倍。

對 5 進行旋轉（改善後）

XTree 對 AVL Tree 的效能評比

為了能與 XTree 進行效能比較，我親手實作了一棵 AVL Tree ，相對應的 git commit 有附上相關程式進行測試，包括基本的插入、刪除、搜尋操作，不過進行效能評比時也有發生過幾次刪除失誤，因此刪除操作尚有待加強。

亂序插入

我們先測試對兩棵樹亂序插入，以下測試結果符合我們對兩者的預測，其中（

↑

XTree,

↓

AVL Tree），因為 XTree 較不常發生旋轉，相對於經常需要旋轉調整的 AVL Tree ，插入及刪除的成本平均要低上許多。但是在搜尋方面， AVL Tree 由於樹高接近於

l o g n

（

n

為節點數），所以平均的搜尋成本會比 XTree 要低。

$ ./build/treeint 10 3

-----    Insert         -----

320,286,132,110,52,48,46,89,34,31,
185,335,432,177,257,358,179,131,189,259,

-----    Find   -----

116, 51, 36, 42, 28, 33, 23, 40, 48, 32, 
66, 41, 30, 21, 22, 26, 40, 28, 28, 31, 

-----    Remove         -----

198, 63, 33, 23, 103, 22, 86, 51, 21, 22, 
89, 497, 30, 148, 29, 61, 134, 43, 35, 29,

循序插入

其實效果與亂序插入看不出明顯的差別，但是循序插入的優點在於我們可以用紙筆追蹤樹的操作。例如對 AVL Tree 循序插入 1,2,3,4 則在插入3時會旋轉插入4時則因為平衡不會旋轉，也間接觀察到再不旋轉的情況下 XTree 以及 AVL Tree 的插入成本近乎相同。並且在此例中也觀察到搜尋成本 XTree 相對於 AVL Tree 要有更大的起伏。

$ ./build/treeint 10 0

-----    Insert         -----

630,368,171,108,170,134,101,103,113,154,
267,449,482,110,263,359,159,108,193,294,

-----    Find   -----

217, 99, 168, 53, 73, 44, 39, 38, 44, 42, 
84, 52, 50, 42, 82, 39, 46, 33, 36, 45, 

-----    Remove         -----

369, 98, 100, 157, 121, 70, 75, 124, 152, 83, 
309, 717, 127, 143, 91, 79, 145, 85, 94, 118,

2024q1 Homework4 (quiz3+4)

第三週測驗題

測驗二

CPU 週期數量

riscv-none-elf-gcc , riscv-none-elf-objdump

RISC-V 組合語言程式

rv32emu

mod5 實作

mod9 實作

測驗三

程式碼解說

測驗四

程式碼解說

結構變數 ewma

結構變數初始化

EWMA 計算

Linux 核心 EWMA 應用

測驗五

程式碼解說

Linux 核心所應用的 ceil_log2

第四週測驗題

測驗一

程式碼解說

Total Hamming Distance 改進

測驗二

程式碼解說

模 3 運算

測驗三

程式碼解說

程式碼改進

解決方式-引入新的旋轉方式

XTree 對 AVL Tree 的效能評比

Read more

HW3-KXO

2025q1 Homework1 (ideas)

第三週測驗

2025q1 Homework1 (ideas)