2023q1 Homework1 (quiz1)

contributed by < DokiDokiPB >

測驗 2

```c #include <stdint.h> #include "list.h"

struct item {
uint16_t i;
struct list_head list;
};

```c=
#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);
            }
        }
    }
}

取 HHHH 為 list_splice_tail
取 GGGG 為 list_for_each_entry_safe
取 IIII 為 &stack[++top]
取 JJJJ 為 &stack[++top]
取 KKKK 為 &stack[top--]

不用抄題目。闡述你的認知和想法。

jserv

解釋程式碼原理

• 串列中的元素的排序取決於當前 while loop 的 partition 處理對象的順序，並且由 stack[top] 決定
• 在第 38 行中，依據 stack 的性質，list_less 會是下一輪的 while loop 的 partition 處理對象。也就是會先處理最小值
• 最終當串列中元素數量小於等於 1 時，即表示此為當前最小值。
• 在 else case 中，將此串列的元素(僅有 1 個元素)加入至 head 末端中

以表格顯示過程

使用 Graphviz 重製，並嵌入於 HackMD 頁面。

jserv

最一開始 stack 內容
    +------+
    | head |
    +------+

第一次 while loop 後 -->
    +-------+ +-------+ +------+
    | empty | | great | | less |
    +-------+ +-------+ +------+
top:    0        1          2

第二次 while loop 後 -->
    +-------+ +-------+ +-------+ +-------+ +------+
    | empty | | empty | | great | | great | | less |
    +-------+ +-------+ +-------+ +-------+ +------+
top:    0         1         2         3        4

很多次 while loop 後 -->
    +----------+ +----------+ +----------+
    | singular | | singular | | singular |
    +----------+ +----------+ +----------+
top:   ...          ...         ...

指出其缺失

參考上面表格的第二次 while loop 後，產生用不到的 empty，empty 的數量為（

$n$ 為節點數量) ，此不計算 singular 數量：

$$2^0+2^1+...+2^{(lo{g}_{2}n)-1}=2^{(lo{g}_{2}n)}-1=n-1$$
若 n = 256，empty 的數量為 255 個，因此 MAX_DEPTH=512 實際能夠處理的節點數量少於 256 個

比較和實驗

效能改進方案

• 特別是避免依賴 MAX_DEPTH：可以先想到的就是將 MAX_DEPTH 替換為 head 的節點數量，並且在某些步驟時將 empty 移除，(或是 circular stack?)
• 另一種偶然想到的方式， linked list 與 Array 混合版本，例如：

struct StackArray{
    struct list_head chain;
    struct list_head stack[MAX_DEPTH];
}