2025q1 Homework1 (lab0)

contributed by < LambertWSJ >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

開發環境

參考作業說明在 Ubuntu 24.04 安裝 gcc, valgrind 等開發工具外，可另外安裝 clangd 作為編輯器的 Language server 來追蹤程式碼。

---

延伸去年的報告做過的部份

• 實做 queue 介面
• 引入 list_sort 並用 gdb 搭配 script 輸出合併過程的圖片

今年接著做剩下沒完成的部份

實做 Shuffle

洗牌(Shuffle) 選擇 Fisher–Yates shuffle 實做，虛擬碼看上去像是一般的洗牌，差別在於下一筆隨機的資料是從還沒被選中的開始選，如果選中的話會被存到另一個集合(陣列，串列等等)，但就是因為從還沒被選中的資料開始選，才比一般的作法更"隨機"。

維基提供傳統做法和現代做法，傳統的會配置記憶體儲存被選中的元素，將其依序放入到記憶體的後端，實做簡單但浪費記憶體，現代做法則是在原本的集合中搬動被選中的資料到前端，具備 in-place 的特性的實做，相當節省記憶體。

對於 kernel 串列來說，只要有令一個 list_head 就可以一個個接上被選中的節點，在這前提下，傳統和現代只差在將資料放在尾端或前端，分別使用 list_move_tail, list_move 當做參數傳到 fisher_yate_shuffle。

void q_shuffle(struct list_head *head) {
    extern queue_shuffle_alg shuffle_opt;
    if (list_empty(head) || list_is_singular(head))
        return;

    if (shuffle_opt >= TOT_SHUFFLE) {
        return;
    }

    if (shuffle_opt == FISHER_YATE_SHUFFLE ||
        shuffle_opt == FISHER_YATE_MODERN_SHUFFLE) {
        fisher_yate_shuffle(head, shuffle_opt == FISHER_YATE_SHUFFLE
                                      ? list_move_tail
                                      : list_move);
    }
}

fisher_yate_shuffle 使用 list 儲存被選中的節點，每次迭代的時候，從當前的串列 head 選擇 id，當 i == node 則表示找到這個被選中的節點，將它移動到 list，迭代完後，所有被亂數選中的節點會存入到 list, head 則是空的，可以用 list_splice_tail，把洗牌後的串列接到 head，離開函式後，list 就會被釋放。

typedef void (*list_move_f)(struct list_head *node, struct list_head *head);
static void fisher_yate_shuffle(struct list_head *head,
                                const list_move_f move_node) {
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head *node;
    LIST_HEAD(list);

    for (size_t len = q_size(head); len; len--) {
        int id = rand() % len;
        int i = 0;
        list_for_each(node, head) {
            if (i == id) {
                move_node(node, &list);
                break;
            }
            i++;
        }
    }

    list_splice_tail(&list, head);
}

Fisher–Yates shuffle 數學分析

為書寫方便 Fisher–Yates 先簡稱 FY。

選中的機率

FY 是從剩下的集合中選擇資料，因此下個被選中的機率為

$$P(x)=\frac{1}{n}\cdot \frac{1}{n-1}\cdots \frac{1}{1}=\frac{1}{n!}$$

實做 PRNG

研讀 Xorshift 論文中

比較 kernel sort 和 q_sort