2024q1 Homework1 (lab0)

contributed by < yy214123 >

Reveiwed by `56han`

q_reverse 可以善用 list.h 中的 list_for_each_safe 代替 while 迴圈，使程式碼更簡潔。

commit 5b898f0
謝謝你的建議，已進行改善。

Reveiwed by `Ackerman666`

在 queue.c 中有自訂的 get_midpoint 函式
那麼 q_delete_mid 可以直接呼叫該函式獲取中間點，以此精簡程式碼

commit 873001e
謝謝你的提醒，我在實作 merge sort 時沒有注意到這點，已進行改善。

Reveiwed by `164253`

get_midpoint 中用快慢指針尋找中點
若直接用兩個指針從頭尾走向對方，可從

\frac{3}{2} n

次走訪節點變為

n

次

commit b77197f
謝謝你的建議，我覺得是很棒的想法，因為此作業的資料結構為雙向環狀鍊結串列，這個作法能減少走訪次數，詳細的更新紀錄請參見下方 q_sort。

q_delete_dup q_ascend q_descend 三者中有許多重複部分

q_swap 可用 q_reverseK(head, 2) 改寫，你有提出了我不再贅述

commit bd00799
謝謝你的提醒，之前有提及但沒有將其實作，此更新已進行改善。

q_insert_head 和 q_insert_tail 也有許多重複

commit af6de3e

commit 90351a3
受到這個建議的啟發，也同步修改了 q_remove_tail 的實作方式，使其可重用 q_remove_head 的程式碼。

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Address sizes:         39 bits physical, 48 bits virtual
Byte Order:            Little Endian
CPU(s):                20
On-line CPU(s) list:   0-19
Vendor ID:             GenuineIntel
Model name:            13th Gen Intel(R) Core(TM) i5-13600KF
CPU family:            6
Model:                 183
Thread(s) per core:    2
Core(s) per socket:    14
Socket(s):             1
Stepping:              1
CPU max MHz:           5100.0000
CPU min MHz:           800.0000
BogoMIPS:              6988.80 
Virtualization:        VT-x 
L1d:                   544 KiB (14 instances)
L1i:                   704 KiB (14 instances)
L2:                    20 MiB (8 instances)
L3:                    24 MiB (1 instance) 
NUMA node(s):          1
NUMA node0 CPU(s):     0-19

準備事宜

Linux 相關

一直以來沒太多操作 Linux 的經驗，所以我是先從 GNU/Linux 開發工具這份教材開始進行，在 Linux 效能分析工具：perf 這個子教材的教學流程，當我輸入

$ perf top

因為現行是 Normal User 所以出現了這個錯誤

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

此時有個想法，那我能不能把 4 改為 -1 呢？

$ vim  /proc/sys/kernel/perf_event_paranoid

這時候打開了這份文件檔案，但其為唯讀格式，即便我想改為 -1 也無法儲存

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

file 的翻譯是「檔案」，而非「文件」(document)

我想我得把檔案權限配置這塊的東西弄熟，又去瀏覽了鳥哥的教材:
第五章、Linux 的檔案權限與目錄配置，進一步把這些東西搞懂。

command 是「命令」，而非「指令」(instruction)

輸入以下指令可得知剛剛想修改的 perf_event_paranoid 其讀寫相關的權限配置情形

$ ls -al  /proc/sys/kernel/perf_event_paranoid
-rw-r--r-- 1 root root 0  2月 24 10:55 /proc/sys/kernel/perf_event_paranoid

目前是 "- rw- r- - r- -" 代表僅 root 有寫入權限，所以如果我想將 perf_event_paranoid 中的 4 改為 -1，我應該輸入

$ sudo vim  /proc/sys/kernel/perf_event_paranoid

將 4 改為 -1後儲存離開，結果此時又顯示了以下錯誤資訊

/proc/sys/kernel/perf_event_paranoid" E667: Fsync 命行執行失敗

文字訊息避免用圖片來表示，否則不好搜尋和分類

經過更進一步的查詢，這跟 /proc 此檔案系統的性質有關，/proc 是一個虛擬檔案系統，為處理器與處理器模組間的 Communcation Interface，而我透過 vim 去對一個實際上不存在於硬碟中的檔案進行修改，這種操作行為並~~沒有意義~~ 無法完成想將 4 改為 -1 的需求，目前尚未釐清上述命令的影響。

為何要說「沒有意義」呢？你真的知道上述命令的影響嗎？

解決方法

$ echo -1 | sudo tee /proc/sys/kernel/perf_event_paranoid
$ cat /proc/sys/kernel/perf_event_paranoid
-1

你所不知道的 C 語言系列

後續又看〈你所不知道的 C 語言：指標篇〉，但在學習操作 GDB 相關操作時，發生了一些問題。

以相同的範本程式進行

#include <stdio.h>
    int a[3];    
    struct { double v[3]; double length; } b[17];
    int calendar[12][31];

    int main(){}

當我想用 p 指令命令來變更記憶體內容時出現了無法存取的錯誤，尚未找到解決方法。

(gdb) x/4 b
0x4620 <b>:     0       0       0       0
(gdb) p (&b[0]) ->v = {1,2,3}
Cannot access memory at address 0x4620

command 是「命令」，而非「指令」(instruction)

在你所不知道的 C 語言: linked list 和非連續記憶體
前半部介紹了有品味的四行程式碼

void remove_list_node(List *list, Node *target)
{
    // The "indirect" pointer points to the *address*
    // of the thing we'll update.
    Node indirect = &list->head;
    // Walk the list, looking for the thing that 
    // points to the node we want to remove.
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。

~~由於對指標不太熟悉，看起來雖只有短短四行，也讓我花了不少時間來理解他，看懂後我只能說 "牛"！~~

由於對指標不太熟悉，雖該程式僅短短四行，仍花費不少時間來理解，以往在撰寫程式時，若面對有特例狀況須處理，通常也是以大量條件判斷來處理，經由這個範例，不僅對 indirect pointer 及 pointer 操作上有更進一步的認識，最大的收穫是解決問題的思維，面對問題時應適當的換個角度去思考，而非土法煉鋼。

如果看懂卻只能說「牛」，是不是自己的認識太有限？
詳述你的啟發。

Git 相關

參考教材：

首先我在家目錄底下新增了 Linux2024 這個目錄，並遵循教材內容進行相關設定，接著 fork 本次作業的 repository，並在剛剛新增的目錄中取得相關的程式碼

git clone https://github.com/yy214123/lab0-c

而在 lab0(A) 中建議利用 brach 進行實驗，我從上方參考教材之 [為什麼要使用分支] 章節開始學習相關操作，我認為教材蠻有趣的！他以火影忍者的影分身術來形容 branch 的相關運作

分支的概念就有點像「影分身術」，
當你做出一隻新的分身（分支），這個分身會去執行任務或是打倒敵人，
如果執行失敗了，最多就是那個分身消失，就再做一隻新的分身就行了，
本體不會因此受到影響。

——《為你自己學 Git》

Git 會預設一個名為 main 的分支，而＊表示目前分支所在位置

$ git branch
* master

先後嘗試了新增不同分支，並學習在不同分支底下進行 commit，最後將分支 merge，而在完成了牛刀小試中修改 queue.c 的要求後，我想將我的更新結果 push 回 GitHub 時，出現了下方的錯誤資訊

$ git push
Username for 'https://github.com': yy214123
Password for 'https://yy214123@github.com': 
remote: Support for password authentication was removed on August 13, 2021.
remote: Please see https://docs.github.com/en/get-started/getting-started-with-git/about-remote-repositories#cloning-with-https-urls for information on currently recommended modes of authentication.
fatal: 'https://github.com/yy214123/lab0-c/' 身份驗證失敗

解決方法: GitHub 不能再使用密碼驗證，你有更好的選澤 - SSH Key

$ git remote set-url origin git@github.com:yy214123/lab0-c.git
$ git push

作業說明也有提及上述解法，為何捨近求遠？

確實教材有提及，是我當初沒注意。

指定的佇列操作

~~### ```q_new```~~

`q_new`

段落中的程式碼標注，使用 1 個 backtick，而非 3 個。

已改進。

起初在實作這部分時，沒有留意到 list.h 中有 INIT_LIST_HEAD，修正如下：

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;

-   head->next = head->prev = head;
+   INIT_LIST_HEAD(head);
    return head;
}

`q_free`

這邊也是相同的問題，沒有留意到 queue.h 中有 q_release_element，修正如下：

/* Free all storage used by queue */
void q_free(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *pos, *tmp;
    list_for_each_safe (pos, tmp, head) {
        element_t *current_pos = list_entry(pos, element_t, list);
-       free(current_pos->value);
-       free(current_pos);
+       q_release_element(current_pos);
    }
    free(head);
}

`q_delete_mid`

commit 5b898f0
改進建議由 Ackerman666 提出。原始方法中，首先計算中間索引，並採用迭代方式實現相關功能。在對合併排序算法的實現過程中，我引入了一種新的策略，即使用快慢指針來定位中點。此次更新中，採用這一新策略中的 get_midpoint 函式來取代之前的迭代方法。

-   int mid = q_size(head) / 2;
-   struct list_head *current = NULL;
-   int i = 0;
-   list_for_each (current, head) {
-       if (i == mid)
-           break;
-           i++;
-   }
+   struct list_head *current = get_midpoint(head);

`q_delete_dup`

commit 37209d5
這邊不應該在同一次 commit 同時更新 q_delete_dup 及 q_swap，應該獨立開來否則會很混亂。

`q_swap`

commit 37209d5
完全是在硬幹，應多加善用 list.h 中能呼叫的函式，目前還在改進程式碼中。
在思考 q_reverseK 的實作方式時，赫然發現其實 swap 相當於 q_reverseK (當 K =2 時)，這也是可以改進的方向。

commit 8ff1228
改進實作方式，呼叫 list_move 來取代原先冗長的程式碼。

commit bd00799
由 164253 提醒，先前提及 swap 與 q_reverseK (K =2) 功能相同，但並未實際實作，此次更新已完成改進。

`q_reverse`

commit 9ff966d
同樣也是在硬幹，應多加善用 list.h 中能呼叫的函式加以改進。

commit c5be9d4
先前實作遺漏了佇列是否為空、佇列是否僅一個元素的判斷

commit 62fb83c
改進實作方式，呼叫 list_move 來取代原先冗長的程式碼。

commit 5b898f0
由 56han 提出之改善建議，將原先使用 while 去走訪串列的方式，替換為 list.h 中的 list_for_each_safe，程式碼更簡潔的同時也更貼近 Linux 核心風格，更動如下：

-   struct list_head *current = head->next;
-   while (current != head) {
-       struct list_head *tmp = current->next;
-       list_move(current, head);
-       current = tmp;
-   }
+   struct list_head *node = NULL;
+   struct list_head *safe = NULL;
+   list_for_each_safe (node, safe, head) {
+   list_move(node, head);

`q_reverseK`

commit 09079bd

實作此功能時受到了 q_reverse 的啟發，故額外撰寫了類似功能的輔助函式，其作用為對長度為 k 的子佇列進行反轉。

struct list_head *sub_q_reverse(struct list_head *head,int k)
{
    struct list_head *current = head->next;
    while (k>0) {
        struct list_head *tmp = current->next;
        list_move(current, head);
        current = tmp;
        k--;
    }
    return current->prev;
}

`q_insert_head` 及 `q_insert_tail`

兩者邏輯大致相同，前者是呼叫 list.h 中的 list_add 來實作功能，後者則呼叫 list_add_tail，後續檢查 queue.h 時注意到這條規則

// Return: true for success, false for allocation failed or queue is NULL

起初實作時有疏忽，修正如下：

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
+   if (!head)
+       return false;
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return false;

commit af6de3e
由 164253 提出的改善建議，原先 q_insert_head 及 q_insert_tail 兩者程式架構上有許多重複之處，此次更新在 q_insert_tail 呼叫 q_insert_head 來實現其功能。

`q_remove_head` 及 `q_remove_tail`

commit 8c14403
實作兩個函式。

commit 90351a3
參照 commit af6de3e 對於 q_insert_tail 的修改，其實 q_remove_tail 也能重用 q_remove_head 的程式碼來完成其功能。

`q_sort`

commit 81b674f
目前是先以 Bubble sort 來實作佇列元素排序，為改善時間複雜度，目前正在寫 Merge sort 。

commit 545f07d
我在實作 Merge_sort 時遇到了一些困難，此次提交參考了 yanjiew1，無進行任何修改。

commit ac0df04
我對 yanjiew1 程式碼進行了幾項的改進。首先，我把合併排序（merge sort）從原來的函式中分離出來，獨立成一個新的函式。這麼做的主要目的是為了讓程式碼更容易管理，並且方便未來能輕鬆地加入更多的排序方法來進行效能比較

接下來，我移除了原本處理降序排列的程式碼片段。原來的設計是在排序過程中直接考慮降序，但我改成了先按升序排序，如果需要降序，則在排序完成後再將結果反轉。這麼做的好處是使排序函式的職責更專一，只關心如何排序，而不是排序的同時還要考慮排序方向。這種分離也使得程式碼更易於理解和維護。

最後，我新增了一個 get_midpoint 函式來取代原有的中間點尋找過程。原先的方法通過同時移動首尾指標來尋找中間點，get_midpoint 函式的設計是基於快慢指標的策略：快指標每次移動兩步，慢指標每次移動一步。這樣當快指標達到鏈結串列末尾時，慢指標正好位於鏈結串列的中點。

commit b77197f
由 164253 提出的改善建議，原先 get_midpoint 函式的設計是基於快慢指標的策略。假設
$n$ 為佇列長度，為了找到串列的中間節點，快指標須走訪
$n$ 次，慢指標須走訪
$\frac{n}{2}$ 次，總共
$\frac{3 n}{2}$ 次。

但考慮本次實作的佇列為雙向環狀鍊結串列，其實走訪
$n + 1$ 次就能找到中間節點，示意圖如下：

對程式做了下列修改：

-   struct list_head *slow = head->next, *fast = head->next;
-   while (fast != head && fast->next != head) {
-       slow = slow->next;
-       fast = fast->next->next;
-   }
-   return slow ;
+   struct list_head *node1 = head->next, *node2 = head->prev;
+   while (node1 ->next != node2 && node1 != node2) {
+       node1 = node1->next;
+       node2 = node2->prev;
+   }
+   return node1;

執行 make test 後發現有誤，並不能獲得完整的分數，於是我用 qtest 去進行測試，有呼叫 get_midpoint 的函式有二，分別是 merge_sort 及 q_delete_mid ，經測試後發現長度為偶數時有以下問題：
根據 LeetCode 2195 範例的描述，假設資料如下：

長度為 4，所以刪除索引為 2 的節點，而起始索引為 0，故被刪除的是值為 3 的節點。

而我修改後的程式，其刪除的節點會是 2，步驟如下所示：

對應正確的刪除規則，應該要 return node2 而非 return node1。

-   return node1;
+   return node2;

移去非必要的標示，內容才是主體。

已改進。

考慮到 Timsort 的整合，應準備相關的測試案例，反映其資料分布的多元因素。

已於下方實驗二~實驗六進行，準備了三種資料分佈(隨機資料、部分排序、降序)並計算排序所花時間、最後以 perf 去觀察執行不同排序法時 cycles、cache-misses、cache-references、instructions 的變化。

`q_ascend` 及 `q_descend`

指定的佇列以環狀雙向鏈結串列實作，「反向」不是精準的用語。

已修正表達方式。這邊有詢問 chatGPT 該如何更精準的描述，其給出的回應是逆向走訪，但根據國家教育研究院辭書中描述，我認為 chatGPT 的描述方式還是不好。

參考 Leecode 2487 給予的提示進行實作，反向由 head 往前走訪佇列並根據規則進行比較，在實作時有疏忽，導致 commit 時報錯

queue.c:208:13: portability: Assigning a pointer to an integer is not portable. [AssignmentAddressToInteger]
    int max = entry->value;
            ^
queue.c:239:13: portability: Assigning a pointer to an integer is not portable. [AssignmentAddressToInteger]
    int max = entry->value;
            ^

發現是型別的問題，起初是以整數宣告，修正如下：

-   int min = entry->value;
+   char *min = entry->value;

-       if (entry->value <= min) {
+       if (strcmp(entry->value,min)<=0)

commit 091ac54
我發現在 queue.h 對於這兩個函式的實作說明與 Leetcode 2487 中的說明有些許差異是之前沒有留意到的。

前者是：
Remove every node which has a node with a strictly greater value anywhere to the right side of it.

後者是：
Remove every node which has a node with a greater value anywhere to the right side of it.

參考維基百科對於 strict 一詞之解釋，兩者在結果上會有不同，會影響到佇列中重複元素是否該保留，故在此次更新進行了調整使其符合 strictly greater 及 strictly less。修正如下：

-   if (strcmp(entry->value, max) >= 0) {
+   if (strcmp(entry->value, max) > 0) {
        max = entry->value;
        count++;
}

-   if (strcmp(entry->value, max) <= 0) {
+   if (strcmp(entry->value, max) < 0) {
        max = entry->value;
        count++;
}

`q_merge`

不要濫用詞彙，理工人說話要精準。

\to

資訊科技詞彙翻譯

已修正表達方式。

一開始覺得這邊很抽象不直觀，因為根據描述要合併多個排序好的佇列，但觀察其傳入的參數僅有一個 struct list_head，~~不太能理解~~ 不理解到底該如何合併。後續去檢查了 queue.h 觀察到下列的描述及定義。

不理解說就不理解，不要裝懂說「不太能理解」，誠實面對自己。

已修正表達方式。

@head: header of chain

/
queue_contex_t - The context managing a chain of queues
@q: pointer to the head of the queue
@chain: used by chaining the heads of queues
@size: the length of this queue
@id: the unique identification number
*/
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;

假設有三個佇列，分別是 [1,2,3]、[4,5,6]、[7,8,9]，q 這個成員用來指向每個佇列的第一個元素，並透過 chain 將不同 queue_contex_t 實例串接起來，示意圖如下：

Graphviz 腳本要嵌入到 HackMD 筆記中。

已改進。

使用 Graphviz 製圖，並嵌入到 HackMD 筆記中。

已改進，但我覺得畫的還不夠漂亮，邊有點凌亂。 boju

著重呈現概念的關鍵部分，不用一張圖涵蓋太多，這也是工程表達的練習。 jserv

收到！在後續的共筆作業中，會訓練自己用最簡潔的圖形同時精準表達。 boju

commit 6129a77

這邊一開始在 commit 時被指示出以下錯誤：

queue.c:37:5: warning: Assignment of function parameter has no effect outside the function. Did you forget dereferencing it? [uselessAssignmentPtrArg]
    head = NULL;
    ^
queue.c:332:13: error: Uninitialized variables: ctx.q, ctx.chain, ctx.size, ctx.id [uninitvar]
        if (ctx == first_ctx)

以我們的角度會認為 ctx 在每次迭代時會被~~賦予新值~~ 更動，但靜態程式分析工具並不清楚 list_for_each_entry 的運作邏輯，因此有使用 Uninitialized variables 的潛在問題產生。
我進行了以下修改：

-   queue_contex_t *ctx ;
+   queue_contex_t *ctx = NULL ;
    list_for_each_entry (ctx, head, chain)

目前是先將所有佇列合併，再呼叫 q_sort對合併後的佇列進行排序，我認為還有改善空間，目前沒有善用各佇列已排序好的優點來撰寫。

目前進度，除了 trace-17-complexity 以外，其他測試皆順利通過，但回顧自己所寫的程式碼，發現我都沒運用到 indirect pointer，這點是我需要改進的部份。

嘗試將 lib/list_sort.c 引入到 lab0-c

`list_sort`

commit 7c23d5a
此次提交已成功將Linux 核心原始程式碼的 lib/list_sort.c 引入到 lab0-c 專案

在 git commit 時，靜態程式分析工具指示出了下列錯誤：

queue.c
queue.c:303:23: style: Variable 'head' is not assigned a value. [unassignedVariable]
    struct list_head *head, tail = &head;

翻閱 C99 後，我在 [6.7.8] 看到有關這部份的說明：

If an object that has automatic storage duration is not initialized explicitly, its value is
indeterminate. If an object that has static storage duration is not initialized explicitly,
then:
— if it has pointer type, it is initialized to a null pointer;

對此我對程式碼做了一些修改，避免靜態程式分析工具報錯：

-   struct list_head *head, tail = &head;
+   struct list_head *head = NULL , tail = &head;

效能比較

在 Linux 核心設計/實作 (2022): 第 1 週作業解說的 2:25:06 有給予提示，可利用 cpucycles.h 進行效能評比。

根據〈Dude, is my code constant time?〉裡有關設計測試的描述，可以將測試輸入分為兩種類別，分別為 Random class 及 Fix class，目前實作部份還是有困難，我不懂該如何準備資料，以及如何進行測試。

注意書名號 (即 〈 和 〉) 的使用，並非「小於」和「大於」。

後續更新紀錄時會注意這點。

觀察 qtest.c 後，在 console_init() 這個 function 中看到各種 ADD_COMMAND，其相關定義配置在 console.h 中：

#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

一開始不懂 # 與 ## 的用意為何，翻閱 C99 後，我在 [6.10.3.2]、[6.10.3.3] 看到有關這部份的說明，我的解讀如下：

#：會將其後的參數轉換為 character string literal，假設傳遞了 sort 作為 ADD_COMMAND 的 cmd 參數，#cmd 會被轉換為 sort character string literal

##：會將前後參數連接，do_##cmd 變為 do_sort

而原先我程式的撰寫方式是由 q_sort 去呼叫 merge_sort 或 list_sort 來完成指定的佇列排序操作，但如此一來若要搭配 q_test 進行效能評比，使用上較為不方便，所以我希望透過新增指令來更彈性選擇當下要以何種排序進行。

經測試後確定可用

cmd> new
l = []
cmd> ih RAND 2000
l = [rkcbmfioe opjcoyab oykythycu eucotn ticakvac nxkbvi ecguhpelw zwrbx fzlea iirxdvb mbkfim birvbm nrifyb ehmmkjh ukqcvvjp pttrc smdwre zserunjw zbrye idcffhm ikhxzgpqv jxamrroj qhfgjigae hsgvfjwx yuedav kzworgcf feujm ubdtw oapbnzy coyrriux ... ]
cmd> ksort
l = [aagax aahwoeh aaoavl aatjq aatpl aauruta aaykul aberrxw abjjapb abkpstup abttbqaq abxldhf adcwnood adeaxjnv adkkc adqcox adtfsevtk aenvs aepayuot aezetx afnjhvxz aggmk agrkc ahevlrfp ahpdl aiaoskls aiask aicfwoy aisemi aisfalgqt ... ]

但當我想 git commit 出現了下列訊息

/usr/bin/sha1sum: 警告：1 個總和檢查碼不符合
[!] You are not allowed to change the header file queue.h or list.h

原因是我為了使 qtest 中新增的 ksort 可用，我對 queue.h 做了以下更動：

    void q_sort(struct list_head *head, bool descend);
+   void k_sort(struct list_head *head, bool descend);

老師應該是不希望我們這樣去進行不同排序法的效能比較，才對 queue.h 做了該設定，目前還沒想到應如何調整，我在效能分析這邊遇到了蠻大的瓶頸。

qtest 的命令列解析器有 option 可用，你可參照 qtest 的 help 訊息，設計針對排序演算法的選項切換。

已實作完成。

commit 9ff95d4

參考上方老師建議，我在 qtest.c 中新增了以下程式碼：

+   add_param("sort_type", &sort_type, "0 for merge_sort, 1 for list_sort",NULL);

透過 option 命令，來修改 sort_type 之值，在 queue.c 中的會根據該值來決定使用何種排序算法。這也使後續要加入 Timsort 也更方便了，只須新增一個對應的 case 即可。

/* Sort elements of queue in ascending order */
extern int sort_type;
void q_sort(struct list_head *head, bool descend)
{
    switch (sort_type) {
    case 0:
        merge_sort(head);
        break;
    case 1:
        list_sort(head, cmp);
        break;
    default:
        printf("Unknown sort type.\n");
        break;
    }

    if (descend)
        q_reverse(head);
}

測試如下：

cmd> option sort_type 1
cmd> option
Options:
  sort_type   1            | 0 for merge_sort, 1 for list_sort
cmd> option sort_type 0
cmd> option
Options:
  sort_type   0            | 0 for merge_sort, 1 for list_sort

測試資料不該簡稱，不然你以後遇到 "examine information" 這樣的敘述，要寫什麼？

已修正表達方式。

接著是測資測試資料的部份，在分析排序算法時，考慮不同規模和資料分布的資料集對性能的影響至關重要。目前將這一分析分為兩個主要部份：資料集的大小、資料分布的類型，

資料集的大小

小規模：資料量介於 1K~9K 之間。
中規模：資料量介於 10K~99K 之間。
大規模：資料量介於 100K~999K 之間。

使用 SI prefix 來表示資料規模，即 K, 10K, 100K 等等。

已修正。

資料分布的類型

完全隨機
部份已排序

我不確定上述兩部份是否考慮周全。為了能在 qtest 中去讀取生成好的資料集，我新增了 load 命令

+   ADD_COMMAND(load, "Load data", "file");

基於 do_it，去實作能讀取外部資料並插入佇列的 do_load 相關功能。

commit 48c8401

首先新增了一個 data.txt 用於測試，其內容為：
apple
orange
lemon
使用 qtest 測試後確定可用，佇列中已插入 data.txt 的三個元素。

cmd> new
l = []
cmd> load data.txt
l = [apple]
l = [apple orange]
l = [apple orange lemon]
Loaded data from data.txt
cmd> show
Current queue ID: 0
l = [apple orange lemon]

實驗設計

以簡潔明確的漢語書寫。

按照原先規劃，我以 python ~~撰寫了生成測資的程式~~ 產生測試資料，此函式功能在於根據給定的 min_size 和 max_size 作為範圍，動態生成一組隨機字串的資料集。每一個字串的長度將會在 5 到 15 個字元之間隨機選擇，而整個數據集將包含從 min_size 到 max_size 隨機數量個字串。

def generate_string_datasets(min_size, max_size):
    size = random.randint(min_size, max_size)
    random_data = [''.join(random.choices(string.ascii_letters, k=random.randint(5,15))) for _ in range(size)]
    return random_data

接著呼叫上方函式，基於先前實作完成之 option sort_type 及 load 命令，撰寫了相關的腳本，這些腳本能由 source 命令執行。具體步驟如下：

首先，使用 for 迴圈進行 100 次迭代。在每次迭代中，我們執行以下操作：
透過 generate_string_datasets 函式生成一組隨機字串資料集，其字串總量介於給定的參數範圍(下方範例為 1000 ~ 1000000)
將這批隨機生成的字串保存到兩個不同目錄（ms_test_data 和 ls_test_data）下相對應的檔案文件中。每個檔案名 ~~文件名~~ 包括了迭代次數，以便於區分不同的資料集。
為了測試 merge_sort 的效能，為每個資料集創建了一個 source_data，該檔案指定了一系列操作，包括加載資料集、執行排序、輸出排序後資料的大小，並最終釋放記憶體。所有source_data 的引用被添加到 total.txt 檔案中，以便後續批次處理。
針對 list_sort ，採取了類似的步驟，不過在排序前設置了排序類型選項。同樣，每次操作的 source_data 也被記錄在相應的 total.txt 檔案中。
若要測試 merge_sort 效能，執行 qtest 後輸入 source ./ms_test_data/total.txt ; 反之要測試 list_sort 效能，執行 qtest 後輸入 source ./ls_test_data/total.txt

file 的翻譯是「檔案」，而非「文件」(document)

已修正。

通過這樣的設計，程式能夠自動產生多組資料集，並為每組資料集準備好執行排序操作所須的一切設定，預計會將 Delta time 及 size 儲存後繪圖，~~我不確定這樣考慮是否周全，請老師給予進一步的建議~~。

你的統計學課本在哪？
多大的數量才可代表樣本特徵呢？應有對應的數學分析。

我先前並沒有修過統計相關課程，第一週老師說過缺什麼補什麼，這幾日查閱了相關的資料，對於資料集的準備及實驗有了一些見解：

以下方實驗一來說，我產生的 1000 個資料集對應到統計學名詞中的樣本大小，合適的樣本大小應該透過計算統計檢定力 (Statistical power)來確立。

首先要提出對應效能比較的虛無假說及對立假說：

$h 0 :$ list_sort 和 merge_sort 的效能無顯著差異。

$h 1 :$ list_sort 和 merge_sort 的效能有顯著差異。

計算統計檢定力所需參數

效應值 (Effect Size)：
這邊我詢問了 ChatGPT，其提及可先採 Pilot study 來計算效應值，但是 Pilot study 也需要一個樣本大小來進行實驗，這部份我找不到相關教材來參考，所以我不知道該如何正確設計 Pilot study 之樣本大小
暫以簡單範例假設：
生成 30 個 10000 個隨機字串用以計算效應值
經 list_sort 排序平均花費 1.8秒(
${\bar{x}}_{1}$ )，標準差 0.2秒(
$S D_{1}$ )
經 merge_sort 排序平均花費 2.0秒(
${\bar{x}}_{2}$ )，標準差 0.2秒(
$S D_{2}$ )
這邊假設標準差相同方便下方表示，否則須以池化標準差計算，公式如下：

$S D_{p o o l e d} = \sqrt{\frac{(n_{1} - 1) S D_{1}^{2} + (n_{2} - 1) S D_{2}^{2}}{n_{1} + n_{2} - 2}}$
使用 Cohen's d 計算效應值，公式如下：

$d = \frac{{\bar{x}}_{1} - {\bar{x}}_{2}}{S D_{p o o l e d}} ＝ 1$

顯著水平 (significant level)：通常設
$α = 0.05$ 。

Pilot study 樣本大小：30，我遇到瓶頸的部份。
接著就能計算統計檢定力，可使用 G*Power 工具，尚未研究如何使用。

實驗一已知缺失：

不滿足統計學中的重複性 (Repeatability)，對於同一個資料集我只個別用 list_sort 及 merge_sert 排序一次並紀錄時間，應增加測試次數並將其平均。

尚未確定 1000是否 >= 統計檢定力。

想詢問老師上述的推導方向是否有誤?因為我還是無法解決 Pilot study 樣本大小的問題，我認為下方的幾個實驗都不嚴謹，我不知道如何正確使用統計工具去準備資料集。

for i in range(100):#The number of iterations depends on the size of data sets.
    
    large_random_strings = generate_string_datasets(1000, 1000000)
    print(len(large_random_strings))
    
    with open('./ms_test_data/random_data'+str(i)+'.txt', 'w') as file:
        for item in large_random_strings:
            file.write("%s\n" % item)
    with open('./ls_test_data/random_data'+str(i)+'.txt', 'w') as file:
        for item in large_random_strings:
            file.write("%s\n" % item)
    # Test merge_sort performace
    with open('./ms_test_data/source_data'+str(i)+'.txt', 'w') as file:
        file.write("new\n")
        file.write("load ./ms_test_data/random_data"+str(i)+'.txt\n')
        file.write("time sort\n")
        file.write("size\n")
        file.write("free\n")
    with open('./ms_test_data/total.txt', 'a') as file:
        file.write("source ./ms_test_data/source_data"+str(i)+'.txt\n')
    # Test list_sort performance    
    with open('./ls_test_data/source_data'+str(i)+'.txt', 'w') as file:
        file.write("option sort_type 1\n")
        file.write("new\n")
        file.write("load ./ls_test_data/random_data"+str(i)+'.txt\n')
        file.write("time sort\n")
        file.write("size\n")
        file.write("free\n")
    with open('./ls_test_data/total.txt', 'a') as file:
        file.write("source ./ls_test_data/source_data"+str(i)+'.txt\n')

程式碼註解總是用美式英語書寫。

已修正。

commit 465e8f4
當我開始實驗時，遭遇到一個效率問題，主要原因是在執行資料加載（load）操作時，會進行大量的I/O（輸入/輸出）操作，這對效率造成了顯著的拖累。此外，q_show 函數的使用也對 time 函數所計算出來的時間造成了影響，從而進一步降低了實驗的運行效率。
為了優化這一過程，我在這次更新中進行了一些調整，包括將部分函式中的 q_show 呼叫註解掉。這樣做雖然在一定程度上解決了問題，但可以採用一個更優雅的解決方案。具體而言，可以借鑑 option sort_type 概念的設計思路，為當前的實驗情境設計一套選項切換機制。通過這種方式，可以根據需要來決定是否呼叫 q_show ，從而在保證實驗有效輸出的同時，進一步提高運行效率。

實驗一

資料集：產生 1000 個完全隨機資料集，每個資料集中的隨機字串量介於 10K～1000K 之間。
比較對象： list_sort 及 merge_sert。
比較方式：為確保公平，同一個資料集會由 list_sort 及 merge_sert 各自排序並使用 qtest 的 time 來紀錄時間。

比較結果：

分析：
隨資料集規模逐漸變大，明顯可看出list sort 效能表現較佳，而相較於list sort，merge sort 的效能表現不穩定。

嘗試將 Timsort 引入到 lab0-c

commit ce2f8f4

先前已完成透過 option 命令修改 sort_type 之值，根據其值選擇要使用 merge_sort 或 list_sort 進行佇列排序操作。此次更新加入 timsort 並對程式碼做了下方更動。

-   add_param("sort_type", &sort_type, "0 for merge_sort, 1 for list_sort",NULL);
+   add_param("sort_type", &sort_type, "0 for merge_sort, 1 for list_sort, 2 for timsort",NULL);

void q_sort(struct list_head *head, bool descend)
{
    switch (sort_type) {
    case 0:
        merge_sort(head);
        break;
    case 1:
        list_sort(head, cmp);
        break;
+   case 2:
+       timsort(head, cmp);
+       break;
    default:
        printf("Unknown sort type.\n");
        break;
    }

    if (descend)
        q_reverse(head);
}

實驗二

與上方實驗一資料集一致，同為 1000 個規模介於 10K～1000K 之間的隨機字串資料集。

比較結果：

分析：可以看到tim sort 也蠻不穩定的，隨資料集規模變大，有部份的資料排序所花時間少於了 list sort，但若考慮到穩定性仍還是 list sort 勝出。

實驗三

資料集：改為產生 1000 個部份已排序資料集，每個資料集中的字串量介於 10K～1000K 之間。
比較對象： list_sort、merge_sert、tim_sort。
比較方式：為確保公平，同一個資料集會由不同排序演算法各自排序並使用 qtest 的 time 來紀錄時間。

資料集生成方式：

def generate_string_datasets(min_size, max_size):
    size = random.randint(min_size, max_size)
    random_data = [''.join(random.choices(string.ascii_letters, k=random.randint(5,15))) for _ in range(size)]
    for i in range(10):
        sort_idx=random.randint(0,size-1)
        random_data[sort_idx:sort_idx+2000] = sorted(random_data[sort_idx:sort_idx+2000])   
    return random_data

架構上與原先生成隨機資料的差不多，首先也是生成隨機的亂數資料，而為了達到部份已排序的效果，隨機從當前資料集挑一個索引，將該索引往後 2000 個元素進行排序，如此步驟重複 10 次。

比較結果：

分析：
雖已排序資料整體佔比並不是太高，但明顯可以看到 timsort 相較於實驗二又更加穩定。

實驗四

基於實驗三所畫出的圖片，為了更清楚顯示三種排序演算法的差距(資料量 <40K 時效能差異不明顯)，這次調整了生成資料集總數及各資料集中的字串量，並將已排序資料的佔比提高。
資料集：改為產生 500 個部份已排序資料集，每個資料集中的字串量介於 400K～800K 之間。

比較結果：

分析：
這次提高了已排序資料的佔比，隨機從當前資料集挑一個索引，將該索引往後 5000 個元素進行排序，如此步驟重複 50 次。
在這充斥大量已排序好的資料場景，timsort 充分發揮其開發初衷，可以看到執行時間幾乎都低於 list_sort，且也不像先前的幾次實驗，出現了明顯不穩定的狀況，而單以 qtest 中 time 命令來看，在實驗三 x 軸資料量 40K 的部份，執行時間都高於 0.1 秒，在本次實驗也精進許多。

for i in range(50):
    sort_idx = random.randint(0,size-1)
    random_data[sort_idx:sort_idx+5000] = sorted(random_data[sort_idx:sort_idx+5000])

實驗五

資料集：產生 500 個已排序好資料集，每個資料集中的字串量介於 400K～800K 之間，最後將資料集反轉，使其為降序資料集。

random_data = sorted(random_data)
random_data.reverse()

比較結果：

分析：
在處理降序資料的場景，三種排序法的效能表現以 timsort 最佳。

實驗六

參考 Linux 效能分析工具: Perf 及觀摩 ShawnXuanc 後，以該工具進行效能分析，實驗設計方式為生成 400K的測試資料集，將測試資料集分為三種不同的資料分佈：完全隨機、部分已排序、降序。使用 perf 去觀察執行不同排序法時 cycles、cache-misses、cache-references、instructions 的變化。

cycles	merge_sort	list_sort	tim_sort
完全隨機	1,673,107,818	1,626,741,058	1,556,823,021
部分已排序	1,417,089,487	1,346,025,377	1,300,886,270
降序	962,928,056	876,407,771	810,662,483

cache-misses	merge_sort	list_sort	tim_sort
完全隨機	9,715,541	9,004,040	7,886,174
部分已排序	7,441,889	6,706,097	5,959,273
降序	5,814,908	4,812,159	4,402,701

cache-references	merge_sort	list_sort	tim_sort
完全隨機	23,716,471	19,601,592	18,532,688
部分已排序	20,203,233	15,548,596	14,620,037
降序	13,142,469	8,473,563	4,402,701

instructions	merge_sort	list_sort	tim_sort
完全隨機	1,941,617,250	1,867,349,033	1,899,680,816
部分已排序	1,901,561,867	1,841,902,509	1,799,855,524
降序	1,790,490,704	1,731,909,792	1,565,952,943

分析：
我注意到生成的資料可能存在一定的問題。以先前的實驗為例，當資料分佈是部分排序或降序時，觀察到 tim_sort 的表現最為出色是合理的。然而，在完全隨機的資料集上，tim_sort 一直勝出似乎不太符合預期。這次實驗中，我僅生成了一個包含 400K 個元素的資料，並使用以下指令進行 100 次的執行測試，同時計算出平均值：

sudo perf stat  -r 100 -e cycles,cache-misses,cache-references,instructions ./qtest -f <script>

這種情況可能暗示生成的測試資料本身就偏向於部分排序的狀態，從而導致 tim_sort 在這次的效能測試中表現異常突出。

Valgrind + 自動測試程式

執行 make test

---     trace-17-complexity     0/5
---	TOTAL		95/100

執行 make valgrind

---     trace-17-complexity     5/5
---	TOTAL		100/100

原先對於這個結果還很疑惑。

重新閱讀 Linux 核心設計/實作 (2022): 第 1 週作業解說後，在 2:22:47 有提及，須閱讀論文後進行改善。

在作業要求中有提到 lab0-c 不具備 percentile 的處理，對應到論文中 Step 2 : Apply post-processing 的 Cropping 敘述，我認為 trace-17-complexity 無法通過的原因是沒有排除離群值，故導致無法通過全部測試資料。進一步瀏覽原始 dudect.h檔案文件後，我認為得將 prepare_percentiles 這個函式引入 fixture.c 中，目前還在研究函式彼此呼叫的關聯性。

file 的翻譯是「檔案」，而非「文件」(document)

已修正。

commit f7b6823
此次提交已完成 prepare_percentiles 這個函式引入 fixture.c 中，執行 make test 及 make valgrind 皆可全數通過，GitHub Actions 的星之卡比終於出現了。

不要濫用 **，除了增加視覺困難外，這對工程溝通有幫助嗎？

已修正。

整合網頁伺服器

亂數 + 論文閱讀

commit 26b559e
此次提交已完成 Fisher–Yates shuffle 的原始方法，利用了 list.h 中的 list_move_tail 函式來協助實作。

while (cnt) {
        random = rand() % cnt;
        list_for_each (old, head) {
            if (random == 0)
                break;
            random--;
        }
        list_move_tail(old, head);
        cnt--;
    }

將 jserv/ttt 專案整合進 lab0-c

參考 M03: ttt 將 jserv/ttt 下載後，觀察到在其目錄中也有 Makefile 檔案，可以發現 OBJS 變數的目標檔案與 lab0 的 Makefile 不相同。參考 Makefile 語法和示範後，在教材中提到：可以同時有很多不同的 makefile 管理專案的不同部分，為進一步搞懂 Makefile 檔案命名的規則，我去瀏覽了GNU make 中文手册，在手冊的第三章提到：

在預設的情況下，make 會在工作目錄（執行 make 的目錄）下按照檔案名順序 ("GNUmakefile" >> "makefile" >> "Makefile") 尋找 makefile 檔案讀取並執行。

當 makefile 檔案的命名不是這三個任何一個時，需要通過 make 的 "-f" 或者 "–file" 選項來指定 make 讀取的 makefile 檔案。

〈GNU make 中文手册 - § 3.2 makefile 文件的命名〉

commit aa9981d
此更新將 jserv/ttt 中的程式整合進 lab0-c 中，部份調整如下：
將 jserv/ttt 中的 list.h 重新命名為 hlist.h。
將 jserv/ttt 中的 Makefile 重新命名為 Makefile_ttt。

執行下列命令後，可進行遊戲：

$ make -f Makefile_ttt
$ ./ttt
 1 |             
 2 |             
 3 |             
 4 |             
---+-------------
      A  B  C  D

我想將 Makefile_ttt 的使用整合進 lab0-c 的 Makefile 中，我去瀏覽了GNU make 中文手册，在手冊的第二章提到：

預設的情況下，make 執行的是 Makefile 中的首個規則。

〈GNU make 中文手册 - § 2.4 make 如何工作〉

對應到 lab0-c 的 Makefile，可以看到：

all: $(GIT_HOOKS) qtest
OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        shannon_entropy.o \
        linenoise.o web.o
qtest: $(OBJS)
	$(VECHO) "  LD\t$@\n"
	$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm
clean:
	rm -f $(OBJS) $(deps) *~ qtest /tmp/qtest.*
	rm -rf .$(DUT_DIR)
	rm -rf *.dSYM
	(cd traces; rm -f *~)

commit 19d6b74

我對此進行了下列更動，以達到將 Makefile_ttt 的使用整合進 lab0-c 的 Makefile 中此目標。

qtest: $(OBJS)
    $(VECHO) "  LD\t$@\n"
    $(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm
+   $(MAKE) -f Makefile_ttt
clean:
    rm -f $(OBJS) $(deps) *~ qtest /tmp/qtest.*
    rm -rf .$(DUT_DIR)
    rm -rf *.dSYM
    (cd traces; rm -f *~)
+   $(MAKE) -f Makefile_ttt clean

現在當執行 make 命令時，可以看到連同 make -f Makefile_ttt 也一併執行。

$ make  
  CC	qtest.o
  :
  LD	qtest
  make -f Makefile_ttt
  make[1]: 進入目錄「/home/boju/Linux2024/lab0-c」
  cc -Wall -Wextra -std=c11 -I. -MMD   -c -o game.o game.c
  :
  cc -o ttt game.o mt19937-64.o zobrist.o agents/negamax.o main.o 
  make[1]: 離開目錄「/home/boju/Linux2024/lab0-c」

接著在執行 git commit 時，出現一系列的靜態程式分析報錯，逐一排除後剩餘此項:

zobrist.c:64:25: error: Null pointer dereference: (struct zobrist_entry_t*)0 [nullPointer]
                entry = hlist_entry(hash_table[i].first, zobrist_entry_t, ht_list);
                        ^

但根據該行程式的上下文，在 while 迴圈的條件判斷已經有 !hlist_empty(&hash_table[i])，我不懂為何會出現此錯誤，也找不到解決辦法。

commit f0ee647
此次更新在 pre-commit.hook 的 CPPCHECK_suppresses 中新增了 –suppress=nullPointer:zobrist.c \，暫時可解決上方問題。

但接著我收了 Actions 的錯誤通知，錯誤訊息指出：

game.c:74:6: error: conflicting types for ‘available_moves’; have ‘int *(const char *)’
   74 | int *available_moves(const char *table)
      |      ^~~~~~~~~~~~~~~
In file included from game.c:7:
game.h:22:6: note: previous declaration of ‘available_moves’ with type ‘int *(char *)’
   22 | int *available_moves(char *table);
      |      ^~~~~~~~~~~~~~~

當初在處理一系列的靜態程式分析報錯時，僅修改了 game.c 沒有注意到 game.h。

commit d6bb905
修復上述問題。

commit d300744
根據作業要求，修改 qtest 程式，使其新增 ttt 命令。
目前採在 qtest 中 fork 一個子行程執行 ttt.exe 的方式來實作。

2024q1 Homework1 (lab0)

Reveiwed by 56han

Reveiwed by Ackerman666

Reveiwed by 164253

開發環境

準備事宜

Linux 相關

解決方法

你所不知道的 C 語言系列

Git 相關

指定的佇列操作

q_new

q_free

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_insert_head 及 q_insert_tail

q_remove_head 及 q_remove_tail

q_sort

q_ascend 及 q_descend

q_merge

嘗試將 lib/list_sort.c 引入到 lab0-c

list_sort

效能比較

資料集的大小

資料分布的類型

實驗設計

實驗一

嘗試將 Timsort 引入到 lab0-c

實驗二

實驗三

實驗四

實驗五

實驗六

Valgrind + 自動測試程式

整合網頁伺服器

亂數 + 論文閱讀

將 jserv/ttt 專案整合進 lab0-c

Read more

文獻閱讀

2025q1 Homework5 (assessment)

2025q1 Homework1 (lab0)

2025q1 Homework3 (kxo)

Reveiwed by `56han`

Reveiwed by `Ackerman666`

Reveiwed by `164253`

`q_new`

`q_free`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_insert_head` 及 `q_insert_tail`

`q_remove_head` 及 `q_remove_tail`

`q_sort`

`q_ascend` 及 `q_descend`

`q_merge`

`list_sort`