2021q1 Homework1 (quiz1)

contributed by < XDEv11 >

GitHub
第 1 週測驗題

1.解釋上述程式運作原理

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

首先我們可以看到，根據 __node 的結構定義，一個無環的 singly-linked list 如下。

static inline void list_add_node_t(node_t **list, node_t *node_t) {
    node_t->next = *list;
    *list = node_t;
}

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        LLL;
    *left = right;
}

void quicksort(node_t **list)
{
    if (!*list)
        return;

    node_t *pivot = *list;
    int value = pivot->value;
    node_t *p = pivot->next;
    pivot->next = NULL;

    node_t *left = NULL, *right = NULL;
    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? AAA : BBB, n);
    }

    quicksort(&left);
    quicksort(&right);

    node_t *result = NULL;
    list_concat(&result, left);
    CCC;
    *list = result;
}

接著，在上面 quicksort 的程式碼中，可以看到許多 node_t ** (指標的指標)，在進入問題前，我們需要先了解它在此處的用途。

操作一個 singly-linked list 時，最為直觀的方式就是透過一個 node_t * 型態的指標，來指向目前的節點，但是這會導致我們無法改動它。因此我們可以思考，一個節點是如何存在一個 singly-linked list 中的這個位置的呢？是根據前一個節點的 next (或是 head) 來決定的。
因此當我們今天處理一個節點 A 時，透過一個 node_t ** pp 來指向前一個節點的 next (或是 head)，一方面當我們需要節點 A 時，可以透過 *pp 來得到節點 A 的指標，另一方面需要把目前位置的節點 A 做替換時，也可藉由指定數值到 *pp 來完成。

下圖以操作節點 B 為例，紅色箭頭表示操作節點 B 的方式，*pp 可得到節點 B 的指標，**pp 可得到節點 B，*pp = ??則可把節點 B 替換掉。

LLL = ?

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
        LLL;
    *left = right;
}

根據上述解釋， while 敘述的成立條件 *left，即在判斷目前的節點 X 是否為空，若不為空，則推進到下一個節點。
left 是指向 X 的前一個節點的 next，顯而易見的，在推進後，left 會轉為記錄 X 的 next，因此*left 得到 X 的指標，再把 X 的 next 取位址，答案為left = &((*left)->next)。

而在 while 敘述之後，目前的節點 (singly-linked list 的尾端) 的下一個位置為空，根據上述解釋，*left = right; 即可把這個空位置替換成 right，完成 list_concat() 的工作。

AAA / BBB = ?

    while (p) {
        node_t *n = p;
        p = p->next;
        list_add_node_t(n->value > value ? AAA : BBB, n);
    }

先判斷 AAA (BBB) 的型態，由 list_add_node_t() 的原型可得知是 node_t **，再綜合下面 list_concat(&result, left); 以及依據遞增順序排序，可以得知 left 是存放數值比較小的節點，因此 list_add_node_t(n->value > value ? &right : &left, n);

CCC = ?

quicksort 的原理是透過一個基準 (pivot)，每次把元素分成大於以及小於二個部分，因此基準節點最後當然是接在中間。
答案為 list_concat(&result, pivot); list_concat(&result, right);

random

測試程式中的 random()，我們可以看到，

The random() function uses a nonlinear additive feedback random number generator employing a default table of size 31 long integers to return successive pseudo-random numbers in the range from 0 to RAND_MAX.

代表程式每次執行都會得到相同結果。
我們可以透過 srandom()，給予不同的種子來改善。

The srandom() function sets its argument as the seed for a new sequence of pseudo-random integers to be returned by random().

為了每次執行可以得到不同的種子，我們這邊使用時間。

time() 函式，根據 C11 standard 7.27.2.4，

The time function determines the current calendar time. The encoding of the value is unspecified.

但在作為亂數用途上，編碼方式不影響我們使用。

程式碼:
srandom(time(NULL));

留意 time(NULL) 的輸出由於刻度只到秒級，容易預測，倘若挪作 PRNG 的種子，會有潛在的資訊安全風險。

jserv

---

2.重寫上述 quick sort 程式碼，避免使用遞迴呼叫

quick sort 與 merge sort 都是透過 divide-and-conquer 的技巧來解決問題，不同的是，merge sort 合併時還需要進行額外處理，而 quick sort 只需要單純的把 left, pivot, right 三部分擺好而已。參考 array 版本的 quick sort 實作，可以發現到在 array 上，left, pivot, right 自然而然就會維持這個順序，由於沒有其他需要處理的工作，子問題遞迴很正常的就是 tail recursion，因此我們能夠輕易改寫成非遞迴版本。

再觀察測驗題中，singly-linked list 版本的 quicksort 顯然不是這麼回事，因為我們會動到其中的鏈結，最後必須把他們接回來。

下圖為示意圖，假設我們現在處理的區間稱為 X，

分成子問題之後，X 會變成三個散落的部分，彼此並沒有透過鏈結連在一起。

而我們希望的是，他跟 array 一樣，在切分成子問題後，就透過鏈結連在一起了。
此外，把 X 視作一個整體的話，可以發現原本左右也都有鏈結，我們也要維持它們，換句話說，也就是要讓 X 待在整個串列中原本的這個位置。

因此 stack L 的型態為 node_t **，就是為了要能夠修改誰待在這個位置，而 stack R 的型態只需要為 node_t *，因為是透過 X 指過去。
同時，子問題採許左閉右開區間表示 ([*L[i]:R[i]))，不僅僅易於走訪串列上的所有節點，同時也可以改變 X 該放在哪 (透過修改 *L[i]) 以及 X 該接上誰 (指向 R[i])。

這邊優先處理長度較短的區間，可以看到，現在處理的區間為 X，stack 如下圖，

處理完後分成 Y 與 Z 二部分，假設較短的區間為 Z，stack 如下圖，

由 len(Y) + len(Z) = len(X) - 1 和 len(Z) <= len(Y) 可以得知，stack 每多一層，處理的區間長度至少會減半，深度為 O(

$\log n$)。
在一台 64 位元的電腦上，定義 MAX_LEVELS 為 64 即可，因為資料長度不可能超過

$2^{64}$。

void quicksort_nr(node_t **list) {
    // non-recursive version of quicksort
    #define MAX_LEVELS 64
    node_t **L[MAX_LEVELS], *R[MAX_LEVELS]; // stack

    int i = 0;
    L[0] = list, R[0] = NULL;
    while (i >= 0) {
        // pop from stack
        node_t **LL = L[i], *RR = R[i--];
        if (*LL == RR)
            continue;

        // choose first element as pivot
        // partition [pivot->next:RR)
        node_t *pivot = *LL;
        *LL = NULL;
        node_t *p = pivot->next;
        pivot->next = NULL;

        node_t *left = NULL, *right = NULL;
        while (p != RR) {
            node_t *n = p;
            p = p->next;
            list_add_node_t(n->value > pivot->value ? &right : &left, n);
        }
        // keep list linked together
        list_concat(&right, RR);
        list_concat(&pivot, right);
        list_concat(&left, pivot);
        list_concat(LL, left);

        // push into stack
        L[++i] = LL, R[i] = pivot; // [*LL:pivot)
        L[++i] = &(pivot->next), R[i] = RR; // [pivot->next:RR)
        // handle shorter segment
        if (cntl < cntr) {
            {
                node_t **tmp = L[i - 1];
                L[i - 1] = L[i];
                L[i] = tmp;
            }
            {
                node_t *tmp = R[i - 1];
                R[i - 1] = R[i];
                R[i] = tmp;
            }
        }
    }
}

---

3.linux-list 仿效 Linux 核心內部 linked list 的實作並予以簡化，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫

程式碼主要差異在於，只需要在自己定義的結構中納入一個 list_head 的成員，即可使用 list.h 中的 API，也可透過 list_entry() 得到整個物件。
這樣的好處是，不需要自行維護一個鏈結串列，同時也可以降低程式碼的耦合性，增加可維護性。

延續上面第 2 部分的概念，改寫成非遞迴版本，這邊 stack 選擇放入左開右開區間有幾個好處，

• 程式碼簡潔，區間容易表示
  • (head:head)
  • (L:pivot)
  • (pivot:R)
• 容易把節點放到基準的左邊
  • list_move(node->next, L)

比較特別的是，這邊直接將數值較小的節點接到 L 之後，而數值較大的節點則不需要移動，整個結構隨時維持為一個 circular doubly-linked list，

static void list_qsort_nr(struct list_head *head)
{
#define MAX_LEVELS 64
    struct list_head *sl[MAX_LEVELS], *sr[MAX_LEVELS];
    int i = 0;
    sl[0] = head, sr[0] = head;
    while (i >= 0) {
        struct list_head *L = sl[i], *R = sr[i--];
        if (L->next == R)
            continue;
        struct list_head *pivot = L->next, *node = pivot;
        int cl = 0, cr = 0;
        while (node->next != R) {
            if (cmpint(&list_entry(node->next, struct listitem, list)->i,
                       &list_entry(pivot, struct listitem, list)->i) < 0)
                list_move(node->next, L), ++cl;
            else
                node = node->next, ++cr;
        }
        if (cl >= cr) {
            sl[++i] = L, sr[i] = pivot;
            sl[++i] = pivot, sr[i] = R;
        } else {
            sl[++i] = pivot, sr[i] = R;
            sl[++i] = L, sr[i] = pivot;
        }
    }
}

---

4.研讀 Ching-Kuang Shene 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中

TODO

tags: linux2021