Try   HackMD

2024q1 Homework2 (quiz1+2)

contributed by < yenslife >

第一週測驗 1

quiz1-1

參考 Optimized QuickSort — C Implementation (Non-Recursive) 實作非遞迴的快速排序法。
考慮結構體 node_t,其中 left, right 成員在 quiz1-1 中似乎沒有用到。

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;






n1



head1

left

right

next

value



head2

left

right

next

value



head1:next->head2





head3

left

right

next

value



head2:next->head3





NULL1
NULL



head3:next->NULL1





函式說明:

  • list_tail : 回傳 list 的最後一個節點
  • int list_length(node_t **left) : 回傳 list 的長度
  • void list_add(node_t **list, node_t *node_t) : 在 list 的開頭新增一個節點,並將 list 指向的節點改為新增的節點,該節點必須先被初始化
  • node_t *list_construct(node_t *list, int n) : 初始化一個新的節點
  • void list_free(node_t **list) : 釋放 list 中所有節點的記憶體空間

快速排序函式解說

初始化

觀察快速排序函式 void quick_sort(node_t **list),在初始化部分,這邊使用 beginend 這兩個長度為 max_levelnode_t 陣列來表示 stack,並個別初始化為 list 的開頭和結尾。leftright 用來指向被分割成兩個部分的 list 開頭。每次都從 stack 的最上層 (index 為 0) 開始處理

int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n; /* (2 * n) 是最糟情況,即每次都找到最大/小的 */
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;

begin[0] = *list;           
end[0] = list_tail(list);   

主要的迴圈,模擬遞迴呼叫

先讓 L, R 分別表示目前這個 list 要處理的開頭和結尾。i 是待處理堆疊的數量,一開始是 0。當 list 還可以被切割時,程式碼最後會以 i += 2 增加兩個堆疊數量,分別表示左邊和右邊未處理的 list。如果發現當下的 list 只剩下一個節點 (L == R),那就將 i--。如果 L 非空,則將 L 加入 result 這個 list。

/* 模擬遞迴呼叫 */
while (i >= 0) {
    node_t *L = begin[i], *R = end[i];
    if (L != R) {
        /** 
         * 
         * 其他程式碼,稍後討論
         * 
         */
        i += 2;
    } else {     /* 剩下一個節點,放到 */
        if (L)
            list_add(&result, L);
        i--;
    }
}
*list = result;

if (L != R) 的內容

發現 pivot 的選定方式為直接指定 L (這邊一定可以改進,好的 pivot 選擇方式能有效避免最糟情況),並將 p 指向 pivot 的下一個節點,也就是 L 的下一個節點。

node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;






main



pivot
pivot



s0

4



pivot->s0





L
left



R
right



null
NULL



s1

1



s0->s1





s2

3



s1->s2





s3

5



s2->s3





s4

2



s3->s4





s5

7



s4->s5





s5->null





在 while 迴圈中開始比大小,比 pivot 大的節點放到 right 之後;反之,放到 left 之後。

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}






main



pivot
pivot



s0

4



pivot->s0





L
left



s1

1



L->s1





R
right



s3

5



R->s3





n1
NULL



n2
NULL



s2

3



s1->s2





s4

2



s2->s4





s5

7



s3->s5





s4->n1





s5->n2





最後才是「切割」,可以發現處理順序是右邊 -> pivot -> 左邊

begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);

left = right = NULL;
i += 2;






stack



end
end



e_stack

list_tail(&left)

pivot

list_tail(&right)



end->e_stack:left





begin
begin



b_stack

left

pivot

right



begin->b_stack:left





我的改寫方法

兩點可能的改進方案:

  1. 減少額外空間利用 (max_level 大小)
  2. 選擇 pivot 的方式 (Randomized Quick sort / Middle-of-Three)

減少空間佔用

主要佔空間的變數,其中 max_level = 2 * n

  • beginmax_level * sizeof(node_t)
  • end : max_level * sizeof(node_t)

max_level 初始化大小之所以會是 n * 2 * sizeof(node_t),是因為其中的 n * 2 表示 worst case 的 stack 大小,也就是每次都選到最大/小,導致無法一分為二。但越想越不對,如果已經有 shuffle 過了,那 max_level 的大小也不應該超過 n 才對。

/* shuffle array, only work if n < RAND_MAX */
void shuffle(int *array, size_t n)
{
    if (n <= 0)
        return;

    for (size_t i = 0; i < n - 1; i++) {
        size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
        int t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

測試1:極端案例

我在快速排序的 while 迴圈中加入了 max_i 變數,其功能為紀錄目前最大的 i 值,並在函式最後將其印出。

int max_i = 0;
while (i >= 0) {
    /**
     * 一堆程式碼
     * */
    if (i > max_i)
        max_i = i;
}

用極端案例「排序好的 list」來測試,發現 max_i 的值會和節點數量相同,與先前的理解無誤。

測試2:隨機案例

再來我想看看 shuffle 過後的 list 平均的最大 stack 數 (average_max_i) 會是多少,以下設定節點數量為 1000 ~ 10000,shuffle 次數從一次到一千次,取平均。這邊我讓 quick_sort 可以回傳 max_i

/* 觀察 shuffle 1 ~ n 次平均的最大 stack 數 */
void test_shuffle(int n, int node_count)
{
    int *list = malloc(sizeof(int) * node_count), average = 0;
    node_t *head = NULL;
    for (int i = 0; i < node_count; ++i)
            list[i] = i;

    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= i; k++) {
            shuffle(list, node_count);
        }
        for (int i = 0; i < node_count; ++i)
            head = list_construct(head, list[i]);

        average += quick_sort(&head);
        list_free(&head);
    }
    free(list);
    printf("node_count = %d, shuffle = %d, average = %f\n",
           node_count, n, (float)average / n);
}

int main () {
    for (int i = 1000; i <= 10000; i+=1000)
        test_shuffle(50, i);
    return 0
}

印出結果,發現節點個數確實與 average_max_i 成正比,shuffle 的次數增加也會增加平均最高堆疊數,但是影響力不大 (因為是隨機的隨機),到了 50 次之後就幾乎沒有影響了。

實驗數據 (shuffle: 10)

node_count = 1000, shuffle = 10, average = 24.600000
node_count = 2000, shuffle = 10, average = 28.200001
node_count = 3000, shuffle = 10, average = 29.600000
node_count = 4000, shuffle = 10, average = 29.000000
node_count = 5000, shuffle = 10, average = 30.600000
node_count = 6000, shuffle = 10, average = 33.200001
node_count = 7000, shuffle = 10, average = 33.799999
node_count = 8000, shuffle = 10, average = 33.000000
node_count = 9000, shuffle = 10, average = 33.799999
node_count = 10000, shuffle = 10, average = 34.599998

實驗數據 (shuffle: 20)

node_count = 1000, shuffle = 20, average = 25.500000
node_count = 2000, shuffle = 20, average = 28.200001
node_count = 3000, shuffle = 20, average = 31.900000
node_count = 4000, shuffle = 20, average = 32.000000
node_count = 5000, shuffle = 20, average = 32.400002
node_count = 6000, shuffle = 20, average = 31.900000
node_count = 7000, shuffle = 20, average = 34.000000
node_count = 8000, shuffle = 20, average = 35.099998
node_count = 9000, shuffle = 20, average = 35.099998
node_count = 10000, shuffle = 20, average = 35.700001

實驗數據 (shuffle: 50)

node_count = 1000, shuffle = 50, average = 26.480000
node_count = 2000, shuffle = 50, average = 28.760000
node_count = 3000, shuffle = 50, average = 31.799999
node_count = 4000, shuffle = 50, average = 31.520000
node_count = 5000, shuffle = 50, average = 33.279999
node_count = 6000, shuffle = 50, average = 34.080002
node_count = 7000, shuffle = 50, average = 35.160000
node_count = 8000, shuffle = 50, average = 35.919998
node_count = 9000, shuffle = 50, average = 36.160000
node_count = 10000, shuffle = 50, average = 36.639999

實驗數據 (shuffle: 100)

node_count = 1000, shuffle = 100, average = 27.000000
node_count = 2000, shuffle = 100, average = 29.740000
node_count = 3000, shuffle = 100, average = 31.320000
node_count = 4000, shuffle = 100, average = 32.740002
node_count = 5000, shuffle = 100, average = 33.740002
node_count = 6000, shuffle = 100, average = 34.860001
node_count = 7000, shuffle = 100, average = 35.139999
node_count = 8000, shuffle = 100, average = 36.259998
node_count = 9000, shuffle = 100, average = 36.599998
node_count = 10000, shuffle = 100, average = 37.400002

實驗數據 (shuffle: 200)

node_count = 1000, shuffle = 200, average = 26.809999
node_count = 2000, shuffle = 200, average = 29.410000
node_count = 3000, shuffle = 200, average = 31.680000
node_count = 4000, shuffle = 200, average = 33.139999
node_count = 5000, shuffle = 200, average = 33.730000
node_count = 6000, shuffle = 200, average = 34.820000
node_count = 7000, shuffle = 200, average = 35.840000
node_count = 8000, shuffle = 200, average = 36.189999
node_count = 9000, shuffle = 200, average = 37.160000
node_count = 10000, shuffle = 200, average = 37.810001

node_count = 1000, shuffle = 1000, average = 26.486000
node_count = 2000, shuffle = 1000, average = 29.719999
node_count = 3000, shuffle = 1000, average = 31.938000
node_count = 4000, shuffle = 1000, average = 33.189999
node_count = 5000, shuffle = 1000, average = 34.256001
node_count = 6000, shuffle = 1000, average = 35.015999
node_count = 7000, shuffle = 1000, average = 36.018002
node_count = 8000, shuffle = 1000, average = 36.480000
node_count = 9000, shuffle = 1000, average = 37.243999
node_count = 10000, shuffle = 1000, average = 37.987999

節點數少(shuffle: 50, node_count: 1 ~ 200)

node_count = 1, shuffle = 50, average = 0.000000
node_count = 2, shuffle = 50, average = 1.960000
node_count = 3, shuffle = 50, average = 2.560000
node_count = 4, shuffle = 50, average = 2.920000
node_count = 5, shuffle = 50, average = 3.760000
node_count = 6, shuffle = 50, average = 4.040000
node_count = 7, shuffle = 50, average = 4.720000
node_count = 8, shuffle = 50, average = 5.160000
node_count = 9, shuffle = 50, average = 5.800000
node_count = 10, shuffle = 50, average = 6.200000

node_count = 10, shuffle = 50, average = 5.920000
node_count = 20, shuffle = 50, average = 9.160000
node_count = 30, shuffle = 50, average = 10.320000
node_count = 40, shuffle = 50, average = 11.680000
node_count = 50, shuffle = 50, average = 12.440000
node_count = 60, shuffle = 50, average = 13.120000
node_count = 70, shuffle = 50, average = 13.800000
node_count = 80, shuffle = 50, average = 14.360000
node_count = 90, shuffle = 50, average = 15.600000
node_count = 100, shuffle = 50, average = 15.760000
node_count = 110, shuffle = 50, average = 16.040001
node_count = 120, shuffle = 50, average = 16.200001
node_count = 130, shuffle = 50, average = 16.680000
node_count = 140, shuffle = 50, average = 16.799999
node_count = 150, shuffle = 50, average = 17.000000
node_count = 160, shuffle = 50, average = 17.799999
node_count = 170, shuffle = 50, average = 17.480000
node_count = 180, shuffle = 50, average = 17.879999
node_count = 190, shuffle = 50, average = 17.959999
node_count = 200, shuffle = 50, average = 18.320000

將實驗結果繪製成折線圖

shuffle 1 次,每次增加十個節點
截圖 2024-03-12 下午5.01.05

shuffle 2 次,每次增加十個節點
截圖 2024-03-12 下午7.49.28

shuffle 5 次,每次增加十個節點
截圖 2024-03-12 下午4.49.35

shuffle 10 次,每次增加十個節點
截圖 2024-03-10 上午1.01.10

shuffle 50 次,每次增加一百個節點 (因為跑太慢了)
截圖 2024-03-10 上午12.45.23

可以發現結果會趨近於 45 左右,shuffle 越多次,趨勢就越集中。所以我想將 max_level 的值依照節點數量的多寡來設定,並在排序之前先執行 2 ~ 10 次 shuffle,也就是加入 Randomized Quick Sort 的想法進去。

節點數 n max_level
n < 100 n
100 <= n <= 1000 n / 10
1000 <= n n / 20

同時也發現一個問題,那就是 shuffle 的時間也會隨著節點量增加而變長,有沒有更好的方法?或者說可以如何改進 shuffle 的方式?會不會 shuffle 的亂度會影響趨勢的集中程度呢?

TODO: 利用 lab0-c(D) 的工具來測試亂度

觀察 glibc 的 rand() 實作

我原本想要用以上的 Randomized Quick Sort 方法來避免最糟情況,但是遇到太慢的問題,觀察 shuffle 函式的實作,會發現他其實是用 rand() 這個 PRNG 來實作 Fisher–Yates shuffle 方法。希望透過理解 rand() 或是 srand() 的實作,嘗試以合理的角度修改目前 shuffle 的實作方式,最好在不影響隨機性的情況下提升執行速度。 (隨機性?這個也可以來探討,因為 rand() 並不是真正的「隨機」,而是在使用範圍內不可預測的「偽亂數」PRNG)

size_t j = i + rand() / (RAND_MAX / (n - i) + 1);

觀察 glibcstdlib/rand.c,其用途為回傳一個介於 0 ~ RAND_MAX 之間的整數

/* Return a random integer between 0 and RAND_MAX.  */
int
rand (void)
{
  return (int) __random ();
}

然後找到 __random 的實作,在 stdlib/random.c,這邊用了 __libc_lock_lock (lock) 來避免 race condition,其中的 critical section 是 _random_r (&unsafe_state, &retval),該函式實作在 stdlib/random_r.c

至於為什麼要分成 random.crandom_r.c 兩個檔案?前者用來呼叫實作函式,並用 lock 確保不會發生 race condition,後者才是邏輯實作。其他函式像是 initstate, setstate 也是相同的概念,這讓我想到軟體開發中的 Dependency Injection 的設計方式。

long int
__random (void)
{
  int32_t retval;

  __libc_lock_lock (lock);

  (void) __random_r (&unsafe_state, &retval);

  __libc_lock_unlock (lock);

  return retval;
}

這裡有一個參數 unsafe_state,用來記錄隨機演算法的 state information 參數,他是一個名為 random_data 的結構體。

static struct random_data unsafe_state =
  {

    .fptr = &randtbl[SEP_3 + 1], /* 指向距離 rptr rand_sep 個位置
                                  * 事實上不用這個也可以,只是為了實作方便 */ 
    .rptr = &randtbl[1],         /* 指向 state information 的開頭,從
                                  * 之所以從 index 1 開始是因為
                                  * index 0 紀錄 TYPE 了*/


    .state = &randtbl[1], /* 由於是從 index 1 開始,所以
                           * state[-1] 就是 R.N.G 的種類 */

    .rand_type = TYPE_3,  /* R.N.G 的 種類       */
    .rand_deg = DEG_3,    /* 多項式冪數           */ 
    .rand_sep = SEP_3,    /* fptr 和 rptr 的距離 */

    .end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])]
        /* end_ptr 指向 state information 的結尾 */
};

閱讀 stdlib/random.c 的註解,當 state information 小於 32 bytes 時,使用較簡單的 Linear congruential (TYPE_0);反之,使用 LFSR 來產生隨機數,預設為 128 bytes 也就是 TYPE_3。state information 本質上是一個由 long 組成的陣列,第一個元素為 TYPE,其他則是 R.N.G 的 state information。

If we are using the trivial TYPE_0 R.N.G., just do the old linear
congruential bit. Otherwise, we do our fancy trinomial stuff, which is the
same in all the other cases due to all the global variables that have been
set up. The basic operation is to add the number at the rear pointer into
the one at the front pointer. Then both pointers are advanced to the next
location cyclically in the table. The value returned is the sum generated,
reduced to 31 bits by throwing away the "least random" low bit.
Note: The code takes advantage of the fact that both the front and
rear pointers can't wrap on the same call by not testing the rear
pointer if the front one has wrapped. Returns a 31-bit random number.

如果 state table (randtbl) 是 32 bytes 的情況,扣掉第一個元素 TYPE_1,就會剩下 7 個元素,而 7 就表示多項式的最高冪次;同理,128 bytes 的最高冪次就是

(128÷4)1=31 個元素,如下程式碼。

static int32_t randtbl[DEG_3 + 1] =
  {
    TYPE_3,

    -1726662223, 379960547, 1735697613, 1040273694, 1313901226,
    1627687941, -179304937, -2073333483, 1780058412, -1989503057,
    -615974602, 344556628, 939512070, -1249116260, 1507946756,
    -812545463, 154635395, 1388815473, -1926676823, 525320961,
    -1009028674, 968117788, -123449607, 1284210865, 435012392,
    -2017506339, -911064859, -370259173, 1132637927, 1398500161,
    -205601318,
  };

我的問題:這些數字到底是怎麼選的,完全看不出線索,一開始猜測會不會是質數,但也不是,而且居然有負數存在?

我後來在這個 commit 50843ff 發現 Roland McGrath 有更新這些數字,但他並沒有解釋為什麼。似乎在最初的 commit 這些數值就已經定好了。

實作上使用三項式,如此一來要相加的量比較少。state table 中所有數值的 LSB 會是週期為

2deg1 的 LFSR,前提為多項式是不可約 (Irreducible polynomial)、本原多項式 (Primitive Polynomial),總週期約為
deg(2deg1)

__random_r 函式的實作可以分成「LCG TYPE_0」和「LFSR (TYPE_1 ~ TYPE_4)」兩個部分來討論。

線性同餘實作 LCG (Linear Congruential Generator)

直接先看程式碼

int32_t *state;
state = buf->state;
int32_t val = ((state[0] * 1103515245U) + 12345U) & 0x7fffffff;
state[0] = val;
*result = val;

為什麼會有 1103515245U 這個數字,這個數字不是亂選的,參考 stackoverflow 上的討論,以及這篇論文

在開始之前要先理解什麼是 LCG (Linear Congruential Generator),他是一種很常在密碼學中被使用的 Uniform PRNG 方法,利用質數的特性來產生一個週期很長的序列,每次的值都是可以預期的,但因為序列長度很長,所以有「隨機」的效果。判斷一個 LCG 的好壞通常使用 spectral test,觀察序列在二維平面或更高維度中的分佈,並比較距離。

state[0] = val; /* 遞迴關係 */

遞迴關係式:

Xn+1=aXn+b (mod m),LCG 的週期最大為
m
,我們會選擇一個 seed
x0
當作初始值,寫成函式的樣子:
LCG(m,a,b,x0),a,b,x0Zm

要讓 LCG 達到最大週期,應符合以下條件

  • b,m
    互質
  • m 的所有質因數都要能整除
    a1
  • M
    是 4 的倍數,
    A1
    也是
  • a,b,x0
    都比
    m
  • a,b
    是正整數

那為什麼 ANSIC 要選擇

LCG(231,1103515245,12345,12345) 做為參數呢?參考二維度 spectral test 的結果,雖然看起來很平均

image

但在論文中提到這句話

Park and Miller [194] writes: its deficiencies are well known- according to Berke-
ley 4.2 documentation, the low bits of the numbers generated are not very random.
Spectral test for dim.

2s8

與相對應的表格

s
= 2
3 4 5 6 7 8
0.84 0.52 0.63 0.49 0.68 0.43 0.54

測試結果表示這個方法並不隨機 (特別是低位元的表現),但在實作方面卻很方便,因為取模運算的成本高,除非你是對二取餘數,就可以直接用 bitwise 操作。

int32_t val = ((state[0] * 1103515245U) + 12345U) & 0x7fffffff;

0x7fffffff 這個數字的來源?0x7fffffff 就是

2311,所以取餘數就是保留剩下的位元 (就想想 x
21
取餘數會寫成 x & 1
231
也是一樣的道理)。

LFSR (Linear feedback shift register) 實作

LFSR (Linear feedback shift register) 指的是給定前一個狀態的輸出,將該輸出的線性函數再用作輸入的移位暫存器。

int32_t *state;  
if (buf == NULL || result == NULL)
    goto fail;
state = buf->state;

/* 
 * other code... 
 * */

/* 儲存 LFSR 的狀態*/
int32_t *fptr = buf->fptr;
int32_t *rptr = buf->rptr;
int32_t *end_ptr = buf->end_ptr;
uint32_t val;

/* 計算 LFSR 的下一個狀態 */
val = *fptr += (uint32_t) *rptr;
/* Chucking least random bit.  
 * 之所以要丟棄是因為最 LSB 的隨機性較差 */
*result = val >> 1;
++fptr;
if (fptr >= end_ptr) { /* 當 ptr 到達 end,就回到 state */
    fptr = state;
    ++rptr;
}
else {
    ++rptr;
    if (rptr >= end_ptr)
        rptr = state;
}
buf->fptr = fptr;
buf->rptr = rptr;

fptrrptr 指向的值相加,並更新 fptr 的值,將結果右移 1 bit,即可得到隨機值。目前最大的疑問就是 randtbl 那 31 個值到底是怎麼決定的?不可能是憑空想出來的,因為它可以做到

231 循環,但我目前還沒找到相關文獻。

用 List API 改寫非遞迴 Quick sort

結構體

新的結構體 node_t,與 lab0element_t 相似,將原本 struct __nodenext 改成 struct list_head,並刪除用不到的 left, right

-   typedef struct __node {
-       struct __node *left, *right;
-       struct __node *next;
+   typedef struct {
+       struct list_head list;
        long value;
    } node_t;

list_length, list_free

只要會走訪整個 list 的函式都用 list_for_each API 來改寫

int n = 0;  /* 計算長度 */
struct list_head *pos;
list_for_each(pos, list) {
    n++;
}
struct list_head *pos, *q;  /* 釋放 list */
list_for_each_safe(pos, q, list) {
    node_t *node = list_entry(pos, node_t, list);
    free(node);
}

list_add

list.h 中已經有定義 list_add 了,我把 list_add 改成 list_add_node

list_add(&node->list, list);

其他函式的改寫都有一個共通點:參數只接收 struct list_head 而不是 node_t,因為有 list_entry 可以找到所屬 node_t 了。

swap_node

利用 list API 可以很方便實作雙向鏈結的節點交換
TODO: 相鄰節點交換會出錯,待改進。

void swap_node(struct list_head *head, struct list_head *l1, struct list_head *l2)
{
    if (!head || !l1 || !l2)
        return;
    if (list_empty(head))
        return;    
    if (l1 == l2)
        return;

    if (l1->next == l2) {
        list_move_tail(l1, l2->next);
        return;
    }
    if (l2->next == l1) {
        list_move_tail(l2, l1->next);
        return;
    }

    
    struct list_head *temp1 = l1->next;
    struct list_head *temp2 = l2->next;

    list_del_init(l1); /* 拔下來 */
    list_del_init(l2);

    list_add_tail(l1, temp2); /* 插回去 */
    list_add_tail(l2, temp1);
}

Quick sort

與原本作法的不同之處在於

  • 原本的 beginendnode_t 陣列改成 struct list_head 的陣列
  • 使用「交換」的方式來儲存節點,如此一來不需要額外的變數,更直覺。
    • 利用雙向鏈結的優勢來比大小,把尾端比較小的值和開頭比較大的值交換,規則如下:
    1. left, right 指向同一個節點,表示該節點為 pivot,直接 return
    2. left <= pivot ,節點位置不變,將 left 指向下一個節點 (next)
    3. left > pivot
      • right >= pivot,則將 right 指向上一個節點 (prev)
      • right < pivot,則將 leftright 指向的節點交換
    4. 重複以上步驟直到 left == rightleft != right->next (兩個節點的情況),將 pivotleft 的上一個節點交換 (小於 pivot 的節點)
    5. 將下一次迭代的 leftright 記錄到 beginend 陣列

圖示如下,給定鏈結串列 [4, 1, 6, 5, 2] 進行快速排序

left 指向的節點 4 <= 4,所以將 left 指向下一個節點,下一個節點 1 <= 4,所以再指向下一個節點 6。







main



pivot
pivot



s0

4



pivot->s0





L
left



L->s0





R
right



s5

7



R->s5





s1

1



s0->s1





s1->s0





s2

6



s1->s2





s2->s1





s3

5



s2->s3





s3->s2





s4

2



s3->s4





s4->s3





s4->s5





s5->s4





head

head



head->s0






head->s5






left 指向的節點 6 比 4 大,檢查 right 指向的節點,7 比 4 大所以位置保持不變,將 right 指向上一個節點







main



pivot
pivot



s0

4



pivot->s0





L
left



s2

6



L->s2





R
right



s5

7



R->s5





s1

1



s0->s1





s1->s0





s1->s2





s2->s1





s3

5



s2->s3





s3->s2





s4

2



s3->s4





s4->s3





s4->s5





s5->s4





head

head



head->s0






head->s5






檢查 right 指向的節點值,2 比 4 小所以將 leftright 交換







main



pivot
pivot



s0

4



pivot->s0





L
left



s2

6



L->s2





R
right



s4

2



R->s4





s1

1



s0->s1





s1->s0





s1->s2





s2->s1





s3

5



s2->s3





s3->s2





s3->s4





s4->s3





s5

7



s4->s5





s5->s4





head

head



head->s0






head->s5












main



pivot
pivot



s0

4



pivot->s0





L
left



s2

2



L->s2





R
right



s4

6



R->s4





s1

1



s0->s1





s1->s0





s1->s2





s2->s1





s3

5



s2->s3





s3->s2





s3->s4





s4->s3





s5

7



s4->s5





s5->s4





head

head



head->s0






head->s5






left 指向下一個節點,5 比 4 大於是檢查 right 指向的節點 6,因為不滿足條件所以將 right 指向前一個節點







main



pivot
pivot



s0

4



pivot->s0





L
left



s3

5



L->s3





R
right



R->s3





s1

1



s0->s1





s1->s0





s2

2



s1->s2





s2->s1





s2->s3





s3->s2





s4

6



s3->s4





s4->s3





s5

7



s4->s5





s5->s4





head

head



head->s0






head->s5






最後將 pivotleft 的前一個節點交換,並記錄下次迭代 left, right 的位置。







main



b1
begin[i]



s0

2



b1->s0





b2
begin[i+2]



s3

5



b2->s3





pivot
begin[i+1], end[i+2]



s2

4



pivot->s2





e1
end[i]



s1

1



e1->s1





e2
end[i+2]



s5

7



e2->s5





s0->s1





s1->s0





s1->s2





s2->s1





s2->s3





s3->s2





s4

6



s3->s4





s4->s3





s4->s5





s5->s4





head

head



head->s0






head->s5






兩個節點的情況







main



pivot
pivot



s0

2



pivot->s0





L
left



L->s0





R
right



s1

1



R->s1





s0->s1





s1->s0





head

head



head->s0






head->s1












main



pivot
pivot



s0

2



pivot->s0





L
left



s1

1



L->s1





R
right



R->s1





s0->s1





s1->s0





head

head



head->s0






head->s1






會需要在最後加上判斷來將 left, right 指向的同一個節點和 pivot 交換

if (value > list_entry(right, node_t, list)->value)
    swap_node(list, left, pivot);






main



pivot
pivot



s0

1



pivot->s0





L
left



s1

2



L->s1





R
right



R->s1





s0->s1





s1->s0





head

head



head->s0






head->s1






實作上遇到的問題:因為是雙線鏈結串列,所以要隨時記得更新 left, right 的值,這樣會很麻煩,要考慮很多特殊情況,到這邊有點卡關,上面的方法不可行,但如果是矩陣就會方便很多。

醜陋的結果

舉例以下情況,假設我想將 pivot 和 target 交換







main



pivot
pivot



s0

4



pivot->s0





target
target



s3

3



target->s3





s1

1



s0->s1





s1->s0





s2

2



s1->s2





s2->s1





s2->s3





s3->s2





s4

8



s3->s4





s4->s3





s5

7



s4->s5





s5->s4





head

head



head->s0






head->s5






因為紀錄的是記憶體位址而不是陣列的 "index",除了交換節點以外,還要去更改指標指向的位置,這就會導致很多例外情況要處理。







main



target
target



s0

3



target->s0





pivot
pivot



s3

4



pivot->s3





s1

1



s0->s1





s1->s0





s2

2



s1->s2





s2->s1





s2->s3





s3->s2





s4

8



s3->s4





s4->s3





s5

7



s4->s5





s5->s4





head

head



head->s0






head->s5






所以要改寫成 list API 風格可能要把單向鏈結的想法全部消除。舉例來說:end 陣列可能再不需要了,因為雙向鏈結串列的尾端很容易取得;要判斷是否剩下一個節點也只需要用 list_is_singular 巨集即可。參考 yeh-sudo 的做法來寫會比較好,上面實作想法並沒有完全利用 list API 的優勢。

  • 使用 list_for_each_entry_safe 來取代 while 迴圈
  • 不再需要 end 陣列

我的 new_list 的實作

struct list_head *new_list()
{
    struct list_head *list = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(list);
    return list;
}

改寫後,需要特別注意的是釋放記憶體的部分,用 valgrind --leak-check=full ./a.out 來查看記憶體洩漏狀況,發現有 53 個 block 沒有被釋放

==16617== HEAP SUMMARY:
==16617==     in use at exit: 848 bytes in 53 blocks
==16617==   total heap usage: 65 allocs, 12 frees, 2,136 bytes allocated

在節點為空或者剩下一個節點的時候釋放記憶體

        } else {
            if (list_is_singular(L)) {
                list_splice(L, result);
            }
+           free(L);
+           free(left);
+           free(right);
            i--;        
        }
    }
    list_splice(result, head);
+   free(result);

查看記憶體狀況,沒有多餘的釋放操作,但還是有 6 個 block 沒有檢查到,一個是 16 byte 與 struct list_head 相同。

==20547==
==20547== HEAP SUMMARY:
==20547==     in use at exit: 96 bytes in 6 blocks
==20547==   total heap usage: 65 allocs, 59 frees, 2,136 bytes allocated
==20547==
==20547== 32 bytes in 2 blocks are definitely lost in loss record 1 of 2
==20547==    at 0x4885118: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-arm64-linux.so)
==20547==    by 0x10904B: new_list (in /Users/mac/test/linux2024/a.out)
==20547==    by 0x1091FF: quick_sort (in /Users/mac/test/linux2024/a.out)
==20547==    by 0x1094CB: main (in /Users/mac/test/linux2024/a.out)
==20547==
==20547== 64 bytes in 4 blocks are definitely lost in loss record 2 of 2
==20547==    at 0x4885118: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-arm64-linux.so)
==20547==    by 0x10904B: new_list (in /Users/mac/test/linux2024/a.out)
==20547==    by 0x109207: quick_sort (in /Users/mac/test/linux2024/a.out)
==20547==    by 0x1094CB: main (in /Users/mac/test/linux2024/a.out)
==20547==
==20547== LEAK SUMMARY:
==20547==    definitely lost: 96 bytes in 6 blocks
==20547==    indirectly lost: 0 bytes in 0 blocks
==20547==      possibly lost: 0 bytes in 0 blocks
==20547==    still reachable: 0 bytes in 0 blocks
==20547==         suppressed: 0 bytes in 0 blocks
==20547==
==20547== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

最後的程式碼在這邊,希望有人能幫忙找到那消失的 6 個 blocks,可以用 list_print 來查看整個 list 來找線索 。

第一週測驗題 2

Timsort

第二週測驗題 1

quiz2

參考:Linux 核心的 hash table 實作

題目是給定前序 (preorder) 和中序 (inorder),我們要用這些資訊來重新建構一個二元樹

hlist_node 操作

hlist_head 為 hash table

hlist_node 則是 hash table 指向的節點們

struct hlist_node { 
    struct hlist_node *next, **pprev;
}

list_add_head 在雜湊表的開頭插入一個節點」

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = AAAA;
    n->pprev = &h->first;
    h->first = n;
}

有一段比較不直覺的程式碼,因為牽扯到 indirect pointer

if (h->first)
    h->first->pprev = &n->next;

要先知道 h->first 表示第一個 hlist_nodepprev 則是指向一個指向 hlist_node 的指標,&n->next 表示 n 這個節點的下一個節點的記憶體位址,也就是 *pprev 存的內容。

一開始是這樣







G



list_head

list_head

first



node_1

hlist_node_1

pprev

next




list_head:n->node_1:m





node_1:p->list_head:n





node_2

n

pprev

next




NULL
NULL



node_1:n->NULL





經過這一段程式碼之後會變成這樣







G



list_head

list_head

first



node_1

hlist_node_1

pprev

next



list_head:n->node_1:m





node_2

n

pprev

next




node_1:p->node_2:n





NULL
NULL



node_1:n->NULL






然後是後續的程式碼

n->next = h->first;
n->pprev = &h->first;
h->first = n;






G



list_head

list_head

first



node_2

n

pprev

next




list_head:n->node_2:m





node_1

hlist_node_1

pprev

next



node_1:p->node_2:n





NULL
NULL



node_1:n->NULL





node_2:p->list_head:n






node_2:n->node_1:m





Tree 相關資料結構

TreeNode 是我們要建構樹的基本單元

struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};

order_node 紀錄節點的值和索引,內含一個 hlist_node

struct order_node {
    struct hlist_node node;
    int val;
    int idx;
};

Tree 操作

find: 傳入節點的值並計算雜湊值,從雜湊表中找到節點的索引編號 (idx)

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &heads[hash]) {
        struct order_node *on = list_entry(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

node_add 在雜湊表中新增一個節點

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &heads[hash]);
}

build tree 和 dfs

build tree 會先將 inorder 陣列的內容新增到雜湊表上,然後開始做 DFS。

遞迴呼叫 DFS 來建構這顆樹,preorder 順序是中->左->右,可以把每次遞迴呼叫傳入的 preorder 的第一個元素當成根,然後根據 inorder 和 perorder 的範圍來判斷走訪的這個節點存不存在,如果不存在則代表子節點為 NULL。

if (in_low > in_high || pre_low > pre_high)
    return NULL;

struct TreeNode *tn = malloc(sizeof(*tn));
tn->val = preorder[pre_low];
int idx = find(preorder[pre_low], size, in_heads);    
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
               in_low, idx - 1, in_heads, size);
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                idx + 1, in_high, in_heads, size);
return tn;

測試

用測驗題中的範例來測試

程式碼

改進

原本的程式碼沒有檢查 malloc 成功與否,可以在所有 malloc 之前都先檢查一次

Linux cgroups

cgroup 全名為 Linux control group,用來將 process 以層級的方式管理,透過一個虛擬的檔案系統 cgroupfs 為介面來管理

source code 在第 4573 行有關於 pre-order walk 的介紹,透過 cgroup_subsys_state 來走訪

struct cgroup_subsys_state *
css_next_descendant_pre(struct cgroup_subsys_state *pos,
			struct cgroup_subsys_state *root)