2023q1 Homework1 (quiz1)

contributed by < hankTaro >

測驗一

實作快速排序法，數值由小到大排列，並確保可達到 stable sorting 的目標。



























static void list_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    struct item *pivot = list_first_entry(head, AAA, BBB);
    list_del(&pivot->list);

    struct item *itm = NULL, *is = NULL;
    CCC (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            DDD (&itm->list, &list_less);
        else
            EEE (&itm->list, &list_greater);
    }

    list_sort(&list_less);
    list_sort(&list_greater);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    FFF(&list_greater, head);
}

此為遞迴模式的 quick sort
利用Divide and Conquer

找出中間節點 pivot
以 pivot 為比較值，分出值大於/小於 pivot 的兩群，重複進行 list_sort ，直到分不出新的大小群為止

//將第一個節點設為 pivot，並將此點從串列中移出
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);

其中 list_first_entry 的參數是 #define list_first_entry(head, type, member) ，所以 AAAA = struct item ，BBBB = list

//節點結構
struct item {                         
    uint16_t i;
    struct list_head list;
};















// 群訪各點判斷其與 `pivot` 的大小關係，並分群
struct item *itm = NULL, *is = NULL;
    CCC (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            DDD (&itm->list, &list_less);
        else
            EEE (&itm->list, &list_greater);
    }
// 將兩群分別進行遞迴
    list_sort(&list_less);
    list_sort(&list_greater);
// 將串列依據合併
    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    FFF(&list_greater, head);

其中 CCC = list_each_entry_safe ，尋訪各點並且支援在尋訪期間移動當前節點移至其他串列中
if (cmpint(&itm->i, &pivot->i) < 0) 由於是取第一個節點，所以與他相將等的值，必定在其後方，因此比較時使用 < 而非 <= 使與他相等的的節點存入 greater 中，以保持 stable
利用 list_move_tail 將當前節點分別移到 list_less 和 list_greater 的尾端，由於 list_each_entry_safe 是正向尋訪，所以需要使用 list_move_tail 而非 list_move 以保持結果 stable ，所以 DDD = EEE = list_move_tail
最後將大小串列合併，將小於 pivot 的放於 pivot 與 head 之間，將大於 pivot 的串列放於 pivot 之後，故 FFF = list_splice_tail

(代辦)針對 Quick sort 提出上述程式碼的改進方案並實作

引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響

測驗二

將測驗一的程式碼改為非遞迴






















































#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head stack[MAX_DEPTH];
    for (int i = 0; i < MAX_DEPTH; i++)
        INIT_LIST_HEAD(&stack[i]);
    int top = -1;
    list_splice_init(head, &stack[++top]);

    struct list_head partition;
    INIT_LIST_HEAD(&partition);

    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &partition);
        if (!list_empty(&partition) && !list_is_singular(&partition)) {
            struct list_head list_less, list_greater;
            INIT_LIST_HEAD(&list_less);
            INIT_LIST_HEAD(&list_greater);
            struct item *pivot =
                list_first_entry(&partition, struct item, list);
            list_del(&pivot->list);
            INIT_LIST_HEAD(&pivot->list);

            struct item *itm = NULL, *is = NULL;
            GGGG (itm, is, &partition, list) {
                list_del(&itm->list);
                if (cmpint(&itm->i, &pivot->i) < 0)
                    list_move(&itm->list, &list_less);
                else
                    list_move(&itm->list, &list_greater);
            }

            HHHH (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);
        } else {
            top++;
            list_splice_tail(&partition, &stack[top]);
            while (top >= 0 && list_is_singular(&stack[top])) {
                struct item *tmp =
                    list_first_entry(&stack[top], struct item, list);
                list_del(&tmp->list);
                INIT_LIST_HEAD(KKKK);
                list_add_tail(&tmp->list, head);
            }
        }
    }
}

分段說明

初始化，將愈進行 quick sort 的串列放入 stack[0] 中






// 將 stack[0] 指向 head 後的串列，並將 head 指向自身
    struct list_head stack[MAX_DEPTH];
        for (int i = 0; i < MAX_DEPTH; i++)
            INIT_LIST_HEAD(&stack[i]);
        int top = -1;
        list_splice_init(head, &stack[++top]);

進入 while 後，將 stack[top] 中的值 pop() 進入 partition ，並且判別其值是否可再次分割，若可以，隨後所做的事與遞迴版本無異，都是先找出 pivot 並分出 less 和 greater 兩群，唯一不同的是這裡使用的是 list_move 而非 list_move_tail 會使其 non-stable ，其餘與與測驗一相同，下方的程式碼 GGGG = list_each_entry_safe


























    while (top >= 0) {
        // 將從 stack 中 pop() 出的值放入 partition
        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &partition);
        if (!list_empty(&partition) && !list_is_singular(&partition)) {
            /* 
             .
             .
             .
             */
            struct item *itm = NULL, *is = NULL;
            GGGG (itm, is, &partition, list) {
                // 不必 remove 因為在 `list_move` 時，自然就會被移出
                // list_del(&itm->list);
                if (cmpint(&itm->i, &pivot->i) < 0)
                    list_move(&itm->list, &list_less);
                else
                    list_move(&itm->list, &list_greater);
            }
            /* 
             .
             .
             .
             */
        }
    }

而接下來的分治部分，先將 pivot 併入 list_less 這群中，再利用 stack 的 pop 和 push 實現
其中 HHHH = list_move_tail ，而 IIII = JJJJ = &stack[++top] 將兩群分別 push() 進入 stack
這裡 push() 的順序極為重要，會影響到後續程式碼的寫法，以下是以先 push(greater) 再 push(less) ，所以 less 方的會最先被分割到無法分割，也就是最終越接近頂端的值最小，隨後合併時要依序從上到下的放入 head 中，就會是由小到大的 (詳見圖解)






            // 將 pivot 併入 list_less 這群中
            HHHH (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);

當 pop() 出的值不可再次分割，由於 less 總是後 push() 所以會最早分割完，使不可分割值由大到小向上堆疊，所以依序將 stack 中 pop() 出的值 list_add_tail 至 head，直到遇上可分割的值為止

KKKK = &stack[top--] 作為 pop()
另外 while 中做的事，與 list_splice_tail_init(&stack[top--], head); 等價，可直接用其替代











else {
            top++;
            list_splice_tail(&partition, &stack[top]);
            while (top >= 0 && list_is_singular(&stack[top])) {
                struct item *tmp =
                    list_first_entry(&stack[top], struct item, list);
                list_del(&tmp->list);
                INIT_LIST_HEAD(KKKK);
                list_add_tail(&tmp->list, head);
            }
        }

圖例

圖一

圖二
partition = pop(top) 也就是 list_splice_init(&stack[top--], &partition);

圖三
將其分群後使用
list_splice_tail(&list_greater, &stack[++top]);
list_splice_tail(&list_less, &stack[++top]);

(代辦)效能分析

(代辦)改進辦法與成果

必免依賴 `MAX_DEPTH`

此程式碼的 wrost case 就是傳入遞減數列，會使得每一次 push() 進去的串列大小為

n - 1

，最終會占用到 stack[n] 才有辦法合併

想法一:
使用動態記憶體分配，將 stack 大小分配成 list_count_nodes(head) 的大小

想法二:
利用 hybrid sort 的概念，在不同深度使用不同排序法，進而減少運算時間並且降低 stack 最大所需空間

































































#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head stack[MAX_DEPTH];
    for (int i = 0; i < MAX_DEPTH; i++)
        INIT_LIST_HEAD(&stack[i]);
    // int top = -1;
    // list_splice_init(head, &stack[++top]);
    int top = 0;// 作為stack_ptr
    list_splice_init(head, &stack[0]); //減少沒必要的運算量

    // struct list_head partition;
    // INIT_LIST_HEAD(&partition);
    INIT_LIST_HEAD(partition); // 可用一行指令表示

    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        // 將資料 pop() 進 partition 中
        list_splice_init(&stack[top--], &partition);
        // 與遞迴版本中一致，找出 pivot 並且分群出 less 和 greater
        if (!list_empty(&partition) && !list_is_singular(&partition)) {
            struct list_head list_less, list_greater;
            INIT_LIST_HEAD(&list_less);
            INIT_LIST_HEAD(&list_greater);
            struct item *pivot =
                list_first_entry(&partition, struct item, list);
            list_del(&pivot->list);
            INIT_LIST_HEAD(&pivot->list);
            //尋訪各點進行分群
            struct item *itm = NULL, *is = NULL;
            list_each_entry_safe(itm, is, &partition, list) {
                // 不必 remove 因為在 `list_move` 時，自然就會被移出
                // list_del(&itm->list); 
                if (cmpint(&itm->i, &pivot->i) < 0)
                    // list_move(&itm->list, &list_less);
                    //使其 stable
                    list_move_tail(&itm->list, &list_less);
                else
                    // list_move(&itm->list, &list_greater);
                    //使其 stable
                    list_move_tail(&itm->list, &list_greater);
            }

            list_move_tail (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, &stack[++top]);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, &stack[++top]);
        } else {
            top++;
            list_splice_tail(&partition, &stack[top]);
            while (top >= 0 && list_is_singular(&stack[top])) {
                // struct item *tmp =
                //     list_first_entry(&stack[top], struct item, list);
                // list_del(&tmp->list);
                // INIT_LIST_HEAD(KKKK);
                // list_add_tail(&tmp->list, head);
                list_splice_tail_init(&stack[top--], head);
            }
        }
    }
}

測驗三

LLL = (uintptr_t) a ^ (uintptr_t) b
MMM = &list->tail
PPP = real_next->cmp

2023q1 Homework1 (quiz1)

測驗一

(代辦)針對 Quick sort 提出上述程式碼的改進方案並實作

測驗二

分段說明

圖例

(代辦)效能分析

(代辦)改進辦法與成果

必免依賴 MAX_DEPTH

測驗三

Read more

2023 年「資訊科技產業專案設計」作業 1

vcam

2023q1 Homework2 (quiz2)

2023q1 Homework5 (assessment)

必免依賴 `MAX_DEPTH`