2024q1 Homework4 (quiz3+4)

contributed by <ICARUSHERALD96500>

第三週測驗

測驗一

測驗二

針對正整數在相鄰敘述進行 mod 10 和 div 10 操作，如何減少運算成本？

由於無法將

\times 10

或

\div 10

使用 2 的整數冪表示，因此利用

f = G \times Q + r

處理

題目的程式碼中：

 int tmp = (b[i] - '0') + (a[i] - '0') + carry;
        carry = tmp / 10;
        tmp = tmp % 10;

將 b 和 a 中，目前位的字符轉換成數字（通過減去字符 '0'），再加上 carry（進位值）。由於 b[i] 和 a[i] 都是單個數字字符，所以 (b[i] - '0') 和 (a[i] - '0') 的結果都是 0 到 9 之間的數字。當兩個 0 到 9 之間的數字相加時，結果會在 0 到 18 之間，再加上可能的 carry（0 或 1），最終 tmp 的範圍會在 0 到 19 之間。

在題目給定目標中，得到 tmp / 10 且直到小數點後第一位都是精確的。

此時就需要找到滿足該條件的除數。這裡用到一個我覺得蠻直觀的概念：當

n, l \in N

且

l < n

。若

n

除某實數在精確度內，則

l

除該除數仍會在精確度內，證明如第 3 週測驗題所述，這裡不贅述。

接著只需要找出符合條件的除數。因為利用逐元運算必為

a \div 2^{N}

，所以找

2^{N}

在找符合條件的

a

即可。下面利用題目範例：

以 13 為例，

13 = 8 + 4 + 1

，也就是

\frac{t m p}{16} + \frac{t m p}{2} + \frac{t m p}{1}

，而在逐元操作中為:

(tmp >> 3)+(tmp >> 1)+tmp

但是如次會造成右側的位元被捨棄，故在此之前應該先將其承接紀錄

        d0 = q & 0b1;
        d1 = q & 0b11;
        d2 = q & 0b111;

而後再將其結合即得到商數

q = ((((tmp >> 3）+(tmp >> 1) + tmp)<< 3) + d0 + d1 + d2) >> 7

在題目提供的測試程式中，有疑問：

為什麼 q 在未定數值下即用於被捨棄的位元提取？

#include <stdint.h>
#include <stdio.h>

int main()
{
    for (int n = 0; n <= 19; n++) {
        unsigned d2, d1, d0, q, r;
        d0 = q & 0b1;
        d1 = q & 0b11;
        d2 = q & 0b111;
        q = ((((n >> 3) + (n >> 1) + n) << 3) + d0 + d1 + d2) >> 7;
        r = n - (((q << 2) + q) << 1);
        printf("q: %d r: %d\n",  q, r);
    }
    
    return 0;
}

可包裝為以下函式: (部分遮蔽)

#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

    *div = (q >> CCCC);
    *mod = in - ((q & ~0x7) + (*div << DDDD));   
}

其背後的原理是，由於逐元操作僅有辦法處理二的冪，因此想要得到除以 10 的結果，就該程式碼是採用先湊出 0.8 被的被除數，最後再 >> 3 ，也就是除去 8 ，就可以得到 0.1 的數值。

為了要湊出 0.8 倍。程式碼中採取 (in | 1) - (in >> 2 ) 如此變可以得到

1 - 0.25 ＝ 0.75

，但是 0.75 距離 0.8 仍有 0.05 倍誤差因此再利用

0.75 / 16 = 0.046875

的特性。數值非常接近 0.05 了。進一步利用遞迴方式可以產生更接近的數值：

$0.796875 / 256 + 0.796875 = 0.79998779296$
$0.79999995231 / 256 + 0.796875 = 0.79999999981$
$0.79999999981 / 256 + 0.796875 = 0.79999999999$
$0.79999999999 / 256 + 0.796875 \approx 0.8$

到此為止就得到 0.8 倍的被除數，接著只需要將其除以 8 便可以得到

\times 0.1

的數值，即q >> 3。因此，CCCC 即為 3。

接著要處理模數，依據

r = f - G \times Q

。但此處的操作為：

*mod = in - ((q & ~0x7)+(*div << 1))

首先注意到 q 經過先前逼近的處理已經近似 0.8 倍的 in，而 (q & ~0x7) 的目的在於捨棄 q 最低為的 3 個位元，因此該數值可能小於等於原始的 q 最多 7 以內的數值，
也就是 q

-

(q & ~0x7)

\leq 7

。舉例來說，0x7 在位元中表示 0111，而 ~0x7 即取反操作，因此為 1000。而假設 q 的三個低位元最大表示數值為 111 等於數值 7 ;最小表示數值為 000 等於數值 0。所以最大會被捨棄的數值變落在 0~7 之間。

其次 (*div << 1) 的作用在於彌補扣除 q 以後所剩下的 0.2 倍的 in。*div 是 in 除以 10 以後的商數，因此是 0.1

\times

in 再無條件捨棄取整數，i.e. *div

\approx 0.1 \times i n

，因此再對其乘以二，極為所求。故 (*div << 1)

問題
1.(in | 1) 為什麼需要把被除數的最低位設定為 1

測驗三

考慮 ilog2 可計算以 2 為底的對數，且其輸入和輸出皆為整數。以下是其一可能的實作: (版本一)

int ilog2(int i)
{
    int log = -1;
    while (i) {
        i >>= 1;
        log++;
    }
    return log;
}

該題的方法便是不停將位元向右移動，直到數值為零，如此便可得到最高位元為 1 的位置。

版本二則是透過二分法搜尋

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= AAAA) {
        result += 16;
        i >>= 16;
    }
    while (i >= BBBB) {
        result += 8;
        i >>= 8;
    }
    while (i >= CCCC) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

整數在 32 位元當中使用二元搜索首先會對半比對數值，首先由第 16 位元也就是 65536 作判定，是否該數值大於該值。接著由第 8、4、1位元，也就是 256、16、2。

版本三是直接使用 __builtin_clz 找到第一個 set bit 的位置

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v));
}

__builtin_clz(unsigned int x) 的功能是回傳第一個 set bit 之前有多少個位元為零，例如數值 16 的二進制在 32 位元表示為 00000000000000000000000000010000 因此在第一個 set bit 前有 27 個零，因此回傳值為 27。所以只需要 31 減去該回傳值變可以獲得開 log2 的結果（__builtin_clz 回傳的是 set bit 前有幾個零，而非本身的位置，故為 32-1）。

測驗四

（EWMA; 指數加權移動平均），簡而言之，就是採用所有歷史資料但，降低對前一筆資料的信賴程度進行的統計平均方法。

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

internal: 用來表示內部目前的平均值
factor: 縮放內部表示值，詳細功能會再提到
weight: 即
$α$ ，但是以
$\frac{1}{2^{w e i g h t}}$ 形式表達

factor 的功能如下：

unsigned long ewma_read(const struct ewma *avg)
{
    return avg->internal >> avg->factor;
}

factor 的功能在上面的程式碼 ewma_read 中，在讀取目前的平均數時，都會將其向右移動 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;
}

上述程式碼用於初始化，確保 factor、weight 都是二的冪。並將這兩個變數開 log2，便可得到在逐元運算中平移量。

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 寫入。最一開始時

S_{0} = Y_{0}

，會先將 val 左移 factor 個位元，再存入 internal 中。而當 internal 後續在有值的情況下進行更新，則是使用：

(((avg->internal << avg->weight) - avg->internal) + (val << avg->factor)) >> avg->weight

該手法是先將

S_{t} = α x_{t} + (1 - α) x_{t - 1}

，前面介紹 weight 時，過

α

是以

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

形式存在。因此將

α

替換後，同乘

2^{w e i g h t}

即可得到

2^{w e i g h t} S_{t} = X_{t} + (2^{w e i g h t} - 1) X_{t - 1}

。再同除

2^{w e i g h t}

便可得

S_{t} = \frac{X_{t} + (2^{w e i g h t} - 1) X_{t - 1}}{2^{w e i g h t}}

。進一步展開便可與上述程式一一對應。

測驗五

目標是找到輸入的第一個 set bit 的位置。手法與測驗三的方法二相同，利用二分法的概念依序檢查輸入值

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;       
}

上述程式碼與測驗三的差異在於條件判斷式的數值會比測驗三的還要小 1，如 r = (x > 0xFFFF) << 4; 當中 0xFFFF 為 65535，較測驗三的 65536 小 1。因為，一開始的 x-- 為了要處理 x 恰為二的冪時，若不減一最後的輸出會因為最後的 +1 而比正確答案多一。

第四週測驗

測驗連結

Linux 核心專題: 平衡二元搜尋樹的研究

執行人: ICARUSHERALD96500

任務簡介

研究 Linux 核心的 red-black tree 並探討相關的資料結構。

TODO: 探討第 4 周測驗 3 的 XTree

第 4 周測驗 3 提到 XTree ，將其與紅黑樹 (Linux 核心風格)、AVL 樹進行比較: 量化分析 (含演算法分析: tree height, 要有對應的數學分析)

第四週測驗題測驗 3

Xtree 是一種同時兼具 AVL 數與紅黑樹特性的自平衡二元樹樹狀結構，其中一項特點為刪除節點的速度較優，利用 hint 值評估樹平衡與否，且僅在 xt_node 被呼叫時更新。下列程式碼說明其移除解點機制

static void __xt_remove(struct xt_node **root, struct xt_node *del)
{
    if (xt_right(del)) {
        struct xt_node *least = xt_first(xt_right(del));
        if (del == *root)
            *root = least;

        xt_replace_right(del, AAAA);
        xt_update(root, BBBB);
        return;
    }

    if (xt_left(del)) {
        struct xt_node *most = xt_last(xt_left(del));
        if (del == *root)
            *root = most;

        xt_replace_left(del, CCCC);
        xt_update(root, DDDD);
        return;
    }

    if (del == *root) {
        *root = 0;
        return;
    }

    /* empty node */
    struct xt_node *parent = xt_parent(del);

    if (xt_left(parent) == del)
        xt_left(parent) = 0;
    else
        xt_right(parent) = 0;

    xt_update(EEEE, FFFF);
}

首先提及其中所使用的函式說明:

xt_root(r) 找出節點 r 的父節點
xt_left(n) 功能為找出節點 n 底下最小的節點，也就是最左邊的極點。巨集定義:#define xt_left(n) (n->left)
xt_right(n) 功能為找出節點 n 底下最大的節點，也就是最又邊的節點。巨集定義:#define xt_right(n) (n->right)
xt_replace_left(n, l) 使用左子樹的節點 l 來調換原本節點 n
xt_replace_right(n, r) 使用右子樹的節點 r 來調換原本節點 n

static inline void xt_replace_right(struct xt_node *n, struct xt_node *r)
{
    struct xt_node *p = xt_parent(n), *rp = xt_parent(r);

    if (xt_left(rp) == r) {
        xt_left(rp) = xt_right(r);
        if (xt_right(r))
            xt_rparent(r) = rp;
    }

    if (xt_parent(rp) == n)
        xt_parent(rp) = r;

    xt_parent(r) = p;
    xt_left(r) = xt_left(n);

    if (xt_right(n) != r) {
        xt_right(r) = xt_right(n);
        xt_rparent(n) = r;
    }

    if (p && xt_left(p) == n)
        xt_left(p) = r;
    else if (p)
        xt_right(p) = r;

    if (xt_left(n))
        xt_lparent(n) = r;
}

if (xt_left(rp) == r) {
        xt_left(rp) = xt_right(r);}

if (xt_right(r)){
            xt_rparent(r) = rp;}

if (xt_parent(rp) == n){
        xt_parent(rp) = r};

xt_parent(r) = p;

xt_left(r) = xt_left(n);

if (xt_right(n) != r) {
        xt_right(r) = xt_right(n);
        xt_rparent(n) = r;
    }

    if (p && xt_left(p) == n)
        xt_left(p) = r;
    else if (p)
        xt_right(p) = r;

 if (xt_left(n))
        xt_lparent(n) = r;

xt_update(n, m)

static inline void xt_update(struct xt_node **root, struct xt_node *n)
{
    if (!n)
        return;

    int b = xt_balance(n);
    int prev_hint = n->hint;
    struct xt_node *p = xt_parent(n);

    if (b < -1) {
        /* leaning to the right */
        if (n == *root)
            *root = xt_right(n);
        xt_rotate_right(n);
    }
    else if (b > 1) {
        /* leaning to the left */
        if (n == *root)
            *root = xt_left(n);
        xt_rotate_left(n);
    }

    n->hint = xt_max_hint(n);
    if (n->hint == 0 || n->hint != prev_hint)
        xt_update(root, p);
}

xt_update(n, m)更新被節點操作後的樹，並根據 hint 判定該樹樹否平衡，而決定後續是否進行旋轉。雖然該機制與 AVL tree 雷同。但差異在於 xt_node 之計算方式為其左右節點 hint 最大值再 +1，並且僅有在 xt_update(n,m) 被呼叫時才更新。而每個節點的 hint 值雖用來判斷樹是否平衡，但是該值卻不用與實際上最長子節點的練長相同。如此一來，便可以減少在每次樹的節點操作後進行更镡時 xt_update(n, m) 所需重新計算高度的工作量。

xt_rotate_right:

static inline void xt_rotate_left(struct xt_node *n)
{
    struct xt_node *l = xt_left(n), *p = xt_parent(n);

    xt_parent(l) = xt_parent(n);
    xt_left(n) = xt_right(l);
    xt_parent(n) = l;
    xt_right(l) = n;

    if (p && xt_left(p) == n)
        xt_left(p) = l;
    else if (p)
        xt_right(p) = l;

    if (xt_left(n))
        xt_lparent(n) = n;
}

xt_rotate_left:

由上述的兩個操作發現，xtree 不論進行左旋或右旋都無法在情況下平衡樹高。

XTree 的最壞情況樹高與普通的二元搜尋樹相似，取決於節點的插入順序。在沒有特殊的平衡措施下，最糟糕情況下可能形成一個高度接近於線性的右斜樹。例如，如果按照特定的插入順序導致每次插入的節點都比前一個節點大（或小），則最終形成的樹可能高度接近於

𝑛

，等同於節點的數量。

與 AVL tree 、 rbtree 比較

AVL tree 為確保平衡，利用平衡因子判斷其子樹高差距，再決定是否旋轉。當為平衡時，必滿足以下條件：

左 子 樹 高 - 右 子 樹 高 \in (- 1, 0, 1)

。xtree 與 AVL tree 類似，利用 hint 紀錄子樹高，在 xt_update 時計算高度差，當左右差異大於一時，進行旋轉。但從程式碼中可以發現，其僅對平衡因子 b 進行大於一或小於一的判斷，進而右旋或左旋。AVL tree 相較之下，有 LL、RR、LR、RL 四種旋轉方式。利用前面提及 xtree 單純使用左或右旋無法解決平衡樹高的情境下。僅需要使用右左或左右旋便可解決。

初始結構：

先對 n 左旋：

再對 p 右旋：

如此一來，變完成樹高平衡。由於樹高對搜尋的效能有所影響，因此簡單討論 AVL tree 的樹高。在平衡的情況下，假設樹高為 h，n(h)為節點最少的情況下樹高與節點的數量關係：

n (h) = n (h - 1) + n (h - 2) + 1

在 AVL tree 樹高。可以發現該關係式與費氏數列相似，因此使用該特性推算第 k 項的數值：

ϕ^{k} / \sqrt{5}

。基於該相似特性，推算

n (h)

也是如此，只不過是把

\sqrt{5}

代換為其他常數，

n (h) \approx k ϕ^{h}

。即便再糟糕的情況下都滿足

ϕ^{h} \leq n

，取對數後樹高即為

h \leq l o g (n) / l o g (ϕ) \approx 1.44 \times l o g (n)

。

rbtree 規則：

節點只能是紅或黑色
根節點必為黑色
葉節點必為黑色
紅色節點的子節點必為黑色
從任一節點到其葉節點，途中路徑上的黑色節點數目相同

滿足上述規則的二元樹，相比一般的二元樹更能保持平衡性，往後套用二元樹的算法來查找資料時能更快速、方便地到達目的地，套用運算的時間複雜度為 O(log n)，這是因為紅黑樹保證最長路徑不會超過最短路徑的兩倍，最短路徑為葉節點到根節點路徑上全部的節點均為黑色，而最長路徑為黑紅相間。

為了 rbtree 在節點操作後，仍滿足 rbtree 的條件。因此，有'變色'與'旋轉'兩種操作。在樹高上，rbtree 與 AVL tree 西相比，因為後者使用平衡因子所以對樹高差異限制嚴格，樹高為

1.44 \times l o g (n)

。反觀 rbtree 平衡機制是利用上述的五條規則，因此樹高較高。因為最長的路徑，可以視為在最短路徑（即路徑上節點均為黑色）間隔插入紅色節點。在 rbtree 樹高上，假設黑高為 bh，那該數至少包含

2^{b h} - 1

個節點（即不存在紅色節點）。利用紅色節點不會連續的條件，可以視為紅色節點被間隔插入，故最高樹高為兩倍的黑高（

h = 2 \times b h

）。假設一顆 rbtree 有 n 個節點，則

2^{b h} - 1 \leq n

，重新整理後可得。

b h \leq l o g (n + 1)

，故在樹高在最糟的情況下

h \leq 2 \times l o g (n + 1)

。在

n

極大的情況下便近似為

2 \times l o g (n)

。

對比 rbtree 與 AVL tree 在樹高上的差異後，rbtree 因為平衡規則較寬鬆，樹高較高。所衍伸的缺點就是雖然在平均狀況下複雜度仍為

l o g (n)

，但最糟的情況下畢竟樹高較高，搜尋的速度稍較 AVL tree 慢。

xtree 因為前面與 AVL tree 作比較時發現，其無法有效的利用程式碼原始的單純左右旋達到平衡樹高，容易出現歪斜的情況，從而增加樹高，減慢在最糟的情況下的搜尋速度。

TODO: 提出 XTree 的改進方案

從資料結構的設計，探討其改進方案，融合 AVL 和 rbtree 的特性，提供對應的實驗

xtree 原始程式碼中，不如 AVL tree 有四種旋轉，僅存在兩種旋轉。在遭遇上述所提及的部份樹狀結構時，無法平衡樹狀結構。對以下程式碼修改，使的 xtree 同樣擁有 4 種旋轉：

     if (b < -1)
     {
         /* leaning to the right */
+        if (xt_balance(xt_right(n)) > 0)
+            xt_rotate_left(xt_right(n));
         if (n == *root)
             *root = xt_right(n);
         xt_rotate_right(n);
     }
 
     else if (b > 1)
     {
         /* leaning to the left */
+        if (xt_balance(xt_left(n)) < 0)
+            xt_rotate_right(xt_left(n));
         if (n == *root)
             *root = xt_left(n);
         xt_rotate_left(n);
     }

當從 xt_balance 回傳左右子樹高的差值 b，除了原始程式碼中判斷其是否在 -1 到 +1 之間外，還必須進一部判斷該節點的子樹是否需要先旋轉。例如當 b<-1 也就是左子樹高小於右子樹高的情況下，還需要進一步判定其右子樹是否需要先被旋轉。也就是 xt_balance(xt_right(n))>0 條件為'真'時，代表 xt_right(n) 的右子樹較高，需要先對其左旋。最後再對 n 右旋。反之亦然。

對於為什麼認為樹高不平衡對於 xtree 來說是缺點? 是以搜索的角度切入，若是一顆 complete binary tree 其搜索複雜度為

O (l o g (n))

。對於原本的 xtree，其樹高會如同上面拿 xtree 與 AVL tree、rbtree 闡述的，隨節點插入，該樹會越發歪斜，而越深則搜索越慢。但若是為了如 AVL tree 為了維持子樹高平衡，就需要加入更多機制在插入節點時進行檢查與旋轉，操作的成本就會增加。而因為 xtree 這些機制較少，因此插入節點的成本較低。所以我推測 xtree 的設計初衷是為了因應需要進行大量節點插入/刪除操作，而捨棄搜索速度所做出的權衡。

在上述的程式碼修改後，xtree 的樹高平衡機制幾乎無異於 AVL tree，差別僅在於 xtree 是透過在每一節點利用 hint 紀錄樹高，而不是在一開始就將左右子樹高的相差先計算好。並且僅在 xt_node 被呼叫時進行平衡狀態更新。有了以上對數高平衡的修正，xtree 的結後會趨近 complete binary tree，其中，對於該樹的第

i

個節點會在第

f l o o r (\log_{2} (i))

層。而對於邊條數量計算上，深度為

d

的節點從根結點到該節點會共有

d

個邊條，也就是說可以透過計算第

i

個節點的深度，推溯出跟節點到第

i

節點的邊數為

f l o o r (\log_{2} (i))

。所以總共

n

個節點就會有

\sum_{i = 1}^{n} f l o o r (\log_{2} (i)) = O (n \times l o g (n))

個邊條。
下面圖解其機制，首先考慮初始狀態的 xtree

使用 xt_balance(n) 可以獲得左右子樹高的相差，即平衡因子，在這裡為

3 - 1 = 2

，沒有落在正負 1 的範圍。引此 b>1 判斷式為真。進入 xt_balance(xt_left(n)<0) 的判斷當中。而 xt_left 節點的子樹高所得的平衡一因子為：

1 - 2 ＝ - 1

，該判斷式同為真。故觸發 xt_rotate_right(xt_left) 對 xt_left 進行左玄。完成該步驟的 xtree 如下：

最後再進行 xt_rotate_right(n) n 右旋：

這樣變可以完成與 AVL tree 相同的旋轉機制，以確保結構平衡。

2024q1 Homework4 (quiz3+4)

第三週測驗

測驗一

測驗二

測驗三

測驗四

測驗五

第四週測驗

Linux 核心專題: 平衡二元搜尋樹的研究

任務簡介

TODO: 探討第 4 周測驗 3 的 XTree

第四週測驗題 測驗 3

與 AVL tree 、 rbtree 比較

TODO: 提出 XTree 的改進方案

Read more

2024q1 Homework5 (assessment)

2024q1 Homework2 (quiz1+2)

2024q1 Homework1 (lab0)

第四週測驗題測驗 3