# 2025q1 Homework1 (lab0)
contributed by < [LambertWSJ](https://github.com/LambertWSJ) >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境
參考作業說明在 Ubuntu 24.04 安裝 gcc, valgrind 等開發工具外，可另外[安裝 clangd](https://hackmd.io/@lambert-wu/tinker-v#clangd) 作為編輯器的 [Language server](https://code.visualstudio.com/api/language-extensions/language-server-extension-guide) 來追蹤程式碼。

---

延伸去年的[報告](https://hackmd.io/@lambert-wu/linux2024-homework1)做過的部份
- [實做 queue 介面](https://hackmd.io/AbSGb2SrQHKEgkVSdalHoA?view#%E5%AF%A6%E4%BD%9C-Queue-%E4%BB%8B%E9%9D%A2)
- [引入 list_sort 並用 gdb 搭配 script 輸出合併過程的圖片](https://hackmd.io/AbSGb2SrQHKEgkVSdalHoA?view#%E5%BC%95%E5%85%A5-list_sortc)

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

## 實做 Shuffle

洗牌(Shuffle) 選擇 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_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 論文中

<!-- introduction to PRNG -->

<!-- ### Xorshift RNG -->
<!-- [xorshift](https://www.jstatsoft.org/article/view/v008i14) 為 George Marsaglia 提出的亂數產生器，特點實做簡單，效能優異。 -->

<!-- ### MT19937 -->

## 比較 kernel sort 和 q_sort