2021q1 Homework (quiz1)

tags: linux2021 ,linked list

contributed by < cymb103u >

• 第1週測驗題目

---

• 1.解釋程式原理
• 2.引入其他 Pseudorandom number generator
• 3.非遞迴呼叫改寫
• 4.仿效 linux-list 並改寫
• 5.思考高效率的 linked list 排序演算法
  • rbtree

---

1. 解釋程式運行原理

• 給定之 data structure，為單向 linked list，typedef 為 node_t

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

• 題目預期 : 已知不存在 circular (環狀結構)，下方程式碼嘗試對該單向 linked list 進行 Quick sort，預期依據遞增順序。

• static inline 舉例說明

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

• list_add_node_t 函式是將 node_t 節點加入到 *list 之前，並將 *list 原本的值更新為 node_t 指向整個串列的最前端。

static inline void list_concat(node_t **left, node_t *right) {
    while (*left)
-       LLL;
+       left = &((*left)->next);
   *left = right;
}

1. LLL = left = &((*left)->next)

list_concat() function 的功用為串接兩個 list。根據給定的 implement 推測它是要走訪 left list 到 end（NULL），再將左右 list 接在一起。而給定的 input left 為 pointer to pointer to node_t; right 則是 pointer to node_t。

一開始以為是 *left = (*left)->next，但這樣子實際上會改變 left 所指向的 address 裡面的值 ( pointer to node_t )，而非改變 left 所指向的 address

所以應該使用 left = &((*left)->next) 來更新 left 所指向的 address

• 1

• 2

• 3

Reference :

• 你所不知道的C語言: linked list 和非連續記憶體操作

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);
+       list_add_node_t(n->value > value ? &right : &left, n);
    }

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

    node_t *result = NULL;
    list_concat(&result, left);
-   CCC;
+   list_concat(&result, pivot); list_concat(&result, right);
    *list = result;
}

2. AAA =&right, BBB = &left

• 在這個 quicksort implement 裡，是以 recursion來進行。 所以用 !*list 來檢查是否要將這個函式中止。
• 而在 16~19 行看到將串列的開頭當做 pivot 取出後並將其 next 指向 NULL 來使它獨立
• 在找到一個 pivot 後比它大的放到right, 比它小的則是放到 left，所以 AAA 填入 &right BBB 填入 &left
• 並以遞迴的方式來繼續排序 left 和 right

3. CCC = list_concat(&result, pivot); list_concat(&result, right);

在最後將分開的 list 以 list_concat() 做串接，並將*list 指向為 result 。

---

2.引入其他 Pseudorandom number generator

• 延伸：透過 time(NULL) 引入時間參數，來產生 random seed.
• 初探 Linux kernel 亂數產生器 – random generator
• linD026

---

3.非遞迴呼叫改寫

Reference :

1. Optimized QuickSort — C Implementation (Non-Recursive)
   
2. Iterative Quick Sort

在原本的程式碼使用 recursive function 時,會需要 function call stack 來紀錄變數、return address 等資訊，並且造成 overhead 減慢速度，所以採用 iterative 來做改寫。

asd

void quicksort_iter(node_t **list)
{
    if (!*list)
        return;
    node_t *stack[MAX_LEVELS];
    int top = -1;
    stack[++top] = *list;
    node_t *partition = NULL;
    node_t *result = NULL;
    while (top >= 0) {
        partition = stack[top--];
        if (partition && partition->next != NULL) {
            node_t *pivot = partition;
            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 ? &right : &left, n);
            }
            // pivot handling
                list_concat(&left, pivot);
            // left and right
            if (right)
                stack[++top] = right;
            if (left)                                                                                                                                 
                stack[++top] = left;

        } else {
            /* single pviot*/
            top++;
            while (top >= 0 && stack[top]->next == NULL) {
                node_t *tmp = stack[top--];
                list_concat(&result, tmp);
            }
        }
    }
    *list = result;
}  

---

延伸問題

2. 參考 Optimized QuickSort — C Implementation (Non-Recursive) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
3. Linux 核心內部也有 linked list 實作，但是 circular doubly-linked list，linux-list 仿效 Linux 核心的實作並予以簡化，在 examples/ 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 linux-list 的 quick sort 範例，避免使用遞迴呼叫
   • 參考資料: The Linux Kernel API - List Management Functions
4. 研讀 Ching-Kuang Shene (冼鏡光) 教授撰寫的 A Comparative Study of Linked List Sorting Algorithms，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中

test

• cppcheck