2024q1 Homework2 (quiz1+2)

contributed by < ICARUSHERALD96500 >

第一週測驗

測驗一

Optimized QuickSort — C Implementation (Non-Recursive)

Q1.解釋上述程式碼的運作原理，提出改進方案並予以實作。

Linked list 在 Quick sort 的作法：
step 1. 首先假設開頭 head 為 pivot。
step 2. L 從Linked list 的頭開始逐步向尾走訪，尋找比 pivot 大的值。同時，R 從尾向頭逐步走訪，尋找比 pivot 小值

結構體

程式碼

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

宣告結構體 node_t ，包含三個指向另一節點 node 的指標、型別為 long 的變數，指標 left, right 分別指向 begin, end 兩個堆疊，指標 next 則指向資料鍊結的下個節點。

問題：不知道 left 、 right 的作用

新增節點 void list_add(node_t **list, node_t *node_t)

程式碼

void list_add(node_t **list, node_t *node_t)
{
    node_t->next = *list;
    *list = node_t;
}

宣告一個 indirect pointer, 與儲存 node_t 節點位址的指標 *node_t ，共兩個引數。
node_t->next = *list 將節點的 next 所指向的位址赴值為 indirect pointer **list 最終所指向的相同位置。也就是 list 所指向的位址與 node_t 所指相同。這裡我不免疑惑為什麼要把指標的變數名稱命名與結構體所使用的型別相同，都命名為 node_t ？

指標的指標：在 list_add 當中第一個引數為 **list a pointer to a pointer to a node。這樣作的目的是因為其需要修改 node2 原先所指向 another node 的指標，將其指向 node1，因此最於，指向 node2 的指標 list 而言，需要訪問 node2 結構體中的指標 next。故為指標的指標。

取得節點尾端位址

程式碼

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA);
    return *left;
}

該函是在間接指標所指向節點的前面插入另一節點，在間接指標所指向位址，且所指節點下一節點皆不為空時，while成立，將間接指標 left 賦值為 (*left)->next i.e.AAAA = (*left->next) ，也就是將 left 所指移動到下個節點。直到下一節點 (*left)->next 為空，退出while，故得到鍊結尾端位址。

取得鏈結串列長度

程式碼

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(BBBB);
    }
    return n;
}

用間接指標所指位址不為空時，變數 n 增加1，並將間接指標移動到下一節點，故 BBBB 為 (*left)->next 。

新增鍊結串列節點並賦值

程式碼

node_t *list_construct(node_t *list, int n)
{
    node_t *node = malloc(sizeof(node_t));
    node->next = list;
    node->value = n;
    return node;
}

傳入兩個引數，分別為所要在之前新增節點 list_head 的位址與所要賦值整數變數 n，首先利用 malloc 配置 node_t 大小的記憶體位址，將該節點的 next 指向 list 所指的位址，再為node 除存的變數賦值。有疑問的是所賦值的型別為整數，與開始結構體宣告 value 的型別為 long 不同，這樣的結構體是否有浪費記憶體配置的疑慮？

釋放鍊結串列記憶體配置

程式碼

void list_free(node_t **list)
{
    node_t *node = (*list)->next;
    while (*list) {
        free(*list);
        *list = node;
        if (node)
            node = node->next;
    }
}

輸入引數為間接指標所指鍊結串列 head 的位址，因為當節點被釋放後就無法指向下一節，首先新增一個節點儲存被釋放的節點的下一節點位址，當間接指標所指不為空時， free 釋放該節點，後將該只標重新賦值圍下一節點的位址。當一節點不為空時，將 node 更新為下一節點的位址。

檢驗是否為單調增

程式碼

static bool list_is_ordered(node_t *list)
{       
    bool first = true;
    int value;
    while (list) {
        if (first) {
            value = list->value;
            first = false;
        } else {
            if (list->value < value)
                return false;
            value = list->value;
        }
        list = list->next;
    }
    return true;
}

函式引數為 head 位址，函式中宣告布林值 first 紀錄是否為 list head，首先輸入*list為鍊結開頭，將該節點所存值賦值給在函式中所宣告變數 value，接著將 list 移動到下一節點。

quick_sort 函式初始化：

進入 while (i>=0) , i=0 時：

當 L、R 不是指向同一個鏈結串列節點時：

接著斷開 pivot 所指向的佇列節點與其他鏈結串列的連結：

當 p 指向任一節點時，由 n 承接 p 原來指向的節點，p 指向下一節點：

比較 n 所指向的值與 pivot 所指向的值大小。若大於 pivot 則，加入 right鍊結中;小於則加入 left 中。直到 p 指向 null

n 繼續移動至下一節點，並判斷 3 小於 pivot 的 4，因此使用 list_add()將其加入 left 的鍊結串列中

判斷 list_add(n->value > value ? &right : &left, n);

n、p 向下一節點移動

判斷 list_add(n->value > value ? &right : &left, n);

n、p 向下一節點移動

判斷 list_add(n->value > value ? &right : &left, n);

至此 p 指向 null 因此跳出 while(p)，
答案
AAAA: (*left)->next
BBBB: (*left)->next
CCCC: p->next
DDDD: list_tail(&left)
EEEE: list_tail(&right)

一般的 Quick sort 具有的特點：
1.會因為選擇不同 pivot 有不同結果。e.g.[0 5 2 4 7 2 6 2 ] 若選擇 2 作為 pivot，經過第一輪排序後會得到 [0 2 2 2 5 4 7 6]。
2.非 in-place：每次將鏈結串列分為兩個子串列，因此會申請兩個新串列來儲存，對每次遞迴的空間複雜度是

O (n^{2})

，最佳狀況是

O (n l o g 2 n)

。

Q2.使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

快速排序法最糟糕的情況是在每一輪排序中 pivot 恰為佇列中最大或最小值，時間複雜度可能為

O (n^{2})

所以若每次都選取固定位置的節點為 pivot 則可能資料本身分佈使得，pivot 特別容易選擇在偏大或偏小的值上。若採用隨機選擇 pivot，則受到鍊結串列資料先驗機率影響的程度也會較小。

因此我使用隨機選擇 pivot 位置的快速排序法，並使用 perf 進行效能測試、並使用隨機資料作為側測資。
結果如下：
pivot為鍊結串列的第一個節點

# node	1e+5	2e+5	5e+5	1e+6
cache-references	1.7e+10	1.5e+10	12	123
instruction	2.5e+11	2.5e+11	12	123
cycles	2.2e+11	2.4e+11	12	123
insn per cycle	1.14	1.05
exeution time（s）	49.71 ± 1.32	53.33 ± 1.55

實作上我使用
答案
AAAA: (*left)->next
BBBB: (*left)->next
CCCC: p->next
DDDD: list_tail(&left)
EEEE: (&right)

2024q1 Homework2 (quiz1+2)

第一週測驗

測驗一

Q1.解釋上述程式碼的運作原理，提出改進方案並予以實作。

Q2.使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

第二周測驗

Read more

2024q1 Homework4 (quiz3+4)

2024q1 Homework5 (assessment)

2024q1 Homework1 (lab0)