2024q1 Homework1 (lab0)

contributed by < lintin528 >

Reviewed by `mervin0102`

關於 q_merge 的實作，我的作法是使用 q_sort 中所使用的 merge 來將不同的佇列合併，這樣作的好處是， q_sort 在排序的過程中，仍會把佇列拆開再排序合併，然而 q_merge 中，已知每個佇列都是以排序的狀況，因此只需要注重排序合併就好，有此可知，呼叫 q_sort 較沒有效率。

但是我的作法仍有一些缺點，當需要合併的佇列數量龐大時，由於實作方法是將所有佇列與第一個佇列作合併排序，因此當第一個佇列長度越來越長時，合併會越來越沒有效率，改進方法可以參考 linux/list_sort.c ，將合併長度控制在 2 的冪次可以達到最佳的合併效率。

你的洞見呢？與其談「心法」，不如設想「如果我是你」，我會怎麼做，示範一次給同學看，而且檢討自己哪裡沒做好，從而呼應原本學員的不足處。
軟體工程師要學會說故事，本作業要求學員從良性詳盡的批評開始。繼續檢討！

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0

$lscpu
Architecture:                       x86_64
CPU op-mode(s):                     32-bit, 64-bit
Byte Order:                         Little Endian
Address sizes:                      39 bits physical, 48 bits virtual
CPU(s):                             12
On-line CPU(s) list:                0-11
Thread(s) per core:                 2
Core(s) per socket:                 6
Socket(s):                          1
NUMA node(s):                       1
Vendor ID:                          GenuineIntel
CPU family:                         6
Model:                              151
Model name:                         12th Gen Intel(R) Core(TM) i5-12400
Stepping:                           2
CPU MHz:                            2500.000
CPU max MHz:                        4400.0000
CPU min MHz:                        800.0000
BogoMIPS:                           4992.00
Virtualization:                     VT-x
L1d cache:                          288 KiB
L1i cache:                          192 KiB
L2 cache:                           7.5 MiB
L3 cache:                           18 MiB
NUMA node0 CPU(s):                  0-11

針對佇列操作的程式碼實作

`q_new`

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

~~已修正!~~
認真檢視下方內容，你真的修正了嗎？不要急著假裝自己有做事，誠實面對自己！

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

功能為建立一個新的"空"佇列，因此僅宣告一個新的指標指向 list_head ，並不需要做element_t之初始化。
首先利用 malloc 配置記憶體空間，並且檢測是否發生記憶體配置失敗產生 NULL 佇列，後使用 "list.h" 定義的 INIT_LIST_HEAD 完成佇列之初始化。

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

struct list_head *q_new()
{
    struct list_head *new_queue = malloc(sizeof(struct list_head));
    if (new_queue == NULL)
        return NULL;
    INIT_LIST_HEAD(new_queue);
    return new_queue;
}

commit f04e991
(這裡因為用實驗室電腦 push 且忘記登出原有 github 導致由不同 user 進行 commit)

列出對應 commit 的 GitHub 超連結

q_insert_head and q_insert_tail

q_insert_head

首先檢查兩個 struct 指標是否都不為 NULL，之後透過在 "queue.h" 定義好的list_add 進行 list_head 的雙向連結，之後使用 strdup 建立副本後，配置給 element_t->value ，因為這裡有新配置記憶體，需要再做一次 if (new_value == NULL) 檢查是否成功。

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new_element = malloc(sizeof(element_t));
    if (new_element == NULL || head == NULL)
        return 0;
    list_add(&new_element->list, head);

    char *new_value = strdup(s);
    if (new_value == NULL)
        return 0;
    new_element->value = new_value;

    return true;
}

q_insert_tail

此部分大抵與 q_insert_head 相同，唯一的差異在於使用 list_add_tail 插入在佇列的尾端。

bool q_insert_tail(struct list_head *head, char *s)
{
    element_t *new_element = malloc(sizeof(element_t));
    if (new_element == NULL || head == NULL)
        return 0;
    list_add_tail(&new_element->list, head);

    char *new_value = strdup(s);
    if (new_value == NULL)
        return 0;
    new_element->value = new_value;
    return true;
}

commit 9516360

考慮到若使用者插入一個空字串有可能會導致 '\0' 字元出現在 list 內，將有可能使 '\0' 後的字元遺失，因此加入 input char *s 是否為空字串的檢測。

     element_t *new_element = malloc(sizeof(element_t));
-    if (new_element == NULL || head == NULL)
+    if (new_element == NULL || head == NULL || s == NULL)
         return 0;

commit bbbaf7e

改變執行順序以些微改善效能

commit d7fe98b

你如何證明這項變更得以改善效能？又，改善幅度有多大？工程人員說話要精準，拿出客觀事實來佐證。

考慮發生 malloc failed 的情況下，某些動作可以放到 == NULL 的檢測之後，以避免像是 list_add(&new_element->list, head); 結束後，才發現 s == NULL 變成多餘的指令，效能的改善根據發生 malloc failed 的多寡決定。

既然與q_insert_head相似，能否將兩函式整合，使程式更加精簡

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

marvin0102

q_free

traverse (動詞) 和 traversal (名詞)

根據 Dictionary.com 的解釋: (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)

to pass or move over, along, or through.
to go to and fro over or along.

其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。

當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。

還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。

在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。

遍歷 (Ergodic) 源於以下二個希臘詞：

ergon (對應英語的 work)
odos (對應英語的 path 或 way)

最初這是由奧地利物理學家波茲曼 (Ludwig Boltzmann) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。

因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。

$\to$ 資訊科技詞彙翻譯

使用 "list.h" 中的 list_for_each_safe 遍歷拜訪該佇列的每個 element_t 並使用 "queue.h" 中的 q_release_element 將其釋放後，最終釋放 head of queue 的記憶體。

其中 node, safe 作為 list_for_each_safe 的暫存變數使用。

void q_free(struct list_head *head)
{
    if (head == NULL)
        return;
    struct list_head *node;
    struct list_head *safe;

    list_for_each_safe (node, safe, head) {
        element_t *next_elem = list_entry(node, element_t, list);
        q_release_element(next_elem);
    }
    free(head);
}

這邊遇到的問題是當初使用 while 遍歷整個佇列時，在 qtest 中會發生以下錯誤：

//while ...
element_t *node = list_entry(next_head, element_t, list);
q_release_element(node);
next_head = next_head->next;

cmd> free
Segmentation fault occurred.  You dereferenced a NULL or invalid pointerAborted 
(core dumped)

後來看到 "list.h" 實作的 list_for_each_safe 才發現 safe 這個暫存變數的必要性。

commit d2932a0

主要修正記憶體未完全釋放的問題，在 new_element 記憶體配置成功但 new_value 配置失敗的情況下，需要將 new_element 釋放；此外些微修改 tasks 的執行順序以求減少錯誤時 malloc 與 free 的次數。

-    if (head == NULL || s == NULL) {
-        return 0;
-    }
     element_t *new_element = malloc(sizeof(element_t));
-    if (new_element == NULL)
+    if (new_element == NULL || head == NULL || s == NULL)
         return 0;
+    list_add(&new_element->list, head);
+
     char *new_value = strdup(s);
-    if (new_value == NULL) {
-        free(new_element);
+    if (new_value == NULL)
         return 0;
-    }

second commit : d7fe98b

q_remove_head and q_remove_tail

在進行實作的時候，一開始儲存 string 的方式如下：

element_t *removed = list_entry(head, element_t, list);
char *saved_value = strdup(removed->value);
if (sp && saved_value)
    sp = saved_value;

用這個方式寫的話，會發生 Segmentation fault occurred. 與 ERROR: Failed to store removed value 的問題。

發現不該使用 list_entry 應該使用 list_first_entry，解決 Segmentation fault occurred.。

更改 string 的儲存方式：

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL)
        return NULL;
    element_t *removed = list_first_entry(head, element_t, list);

    if (sp){
        memcpy(sp, removed->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    
    list_del(&removed->list);
    return removed;
}

比較兩者差異，先前使用的方式將配置一塊新的記憶體空間複製原有 removed->value 指向的內容，並改變 sp 指標位址為新配置記憶體空間之位址，猜想原先出現的錯誤 ERROR: Failed to store removed value 可能為偵測到 sp 被更改 (不確定)；後者為將原有 removed->value 指向的內容複製到 sp 指向的記憶體空間內。另外先前的使用方式需要釋放 sp 原有的記憶體空間

commit 43bf04a

兩函式功能相似，能否將兩函式整合，使程式更加精簡

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

marvin0102

q_size

首先處理佇列為空及 NULL queue 的情形，將 return 0，其餘情況則使用簡單的計數器及 "list.h" 中定義的 list_for_each 去遍歷每一個節點。

int q_size(struct list_head *head)
{
    if (head == NULL || head->next == head)
        return 0;
    struct list_head *node;
    int count = 0;
    list_for_each (node, head) {
        count++;
    }
    return count;
}

commit aff7c93

q_delete_mid

透過 q_size 的實作取得佇列長度後取得位於中點的 list_head ，並透過 list_entry 取得 element_t 後進行節點的釋放。

bool q_delete_mid(struct list_head *head)
{
    int size = q_size(head);
    int count = 0;
    struct list_head *mid = head->next;
    size /= 2;
    while (count <= size - 1) {
        mid = mid->next;
        count++;
    }
    element_t *mid_element = list_entry(mid, element_t, list);
    list_del(mid);
    q_release_element(mid_element);

    return true;
}

commit 8803593

更新後：改以快慢指標尋找佇列中位數。

+    int size = q_size(head);
+    int count = 0;
     struct list_head *mid = head->next;
-    struct list_head *fast = head->next->next;
-    while (fast != head && fast->next != head) {
+    size /= 2;
+    while (count <= size - 1) {
         mid = mid->next;
-        fast = fast->next->next;
+        count++;

}

second commit 3aa4d57

改進你的漢語表達
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。

q_delete_dup

遍歷每一個節點時查看右方所有節點，若有相同者先將右方所有重複節點刪除，跳出迴圈後再將原本重複的節點也刪除。

這裡遇到過許多次的 segmentation fault ，對於鏈結串列的釋放以及 safe 的更改需要多加注意，才能不產生迴圈執行過程指向錯誤目標的問題。

while (safe != head) {
    node_e = list_entry(node, element_t, list);
    safe_e = list_entry(safe, element_t, list);
    safe = safe->next;
    if (strcmp(node_e->value, safe_e->value) == 0) {
        list_del(safe->prev);
        q_release_element(safe_e);
        dup_flag = true;
    } else {
        break;
    }
}
safe = node->next;
if (dup_flag) {
    list_del(node);
    q_release_element(node_e);
    dup_flag = false;
}

commit 9c88029

q_swap

根據佇列的實作特性，僅需要交換 list_head 的指標而不需要去對 element_t 做交換位址的動作，因為 element_t 的位址透過 list.h 定義的巨集 list_entry 完成，而非直接造訪。

原本想另外配置一新的記憶體 struct list_head *tmp = malloc(sizeof(struct list_head)); 發現若不給他賦值會出現 FATAL ERROR: Calls to malloc disallowed，因此決定更換一種交換方式。

tmp->prev = odd->prev;
odd->next = even->next;
odd->prev = even;
even->next = odd;
even->prev = tmp->prev;

更改為

odd->next = even->next;
even->prev = odd->prev;
even->next = odd;
odd->prev = even;
even->prev->next = even;
odd->next->prev = odd;

odd = odd->next;
even = odd->next;

考慮到目前僅有： odd, even 兩個指標，必須先做 odd->prev, even->prev 的修改，否則將會導致丟失相鄰節點的指標。

commit e3f6629

善用 List API 撰寫更精簡的程式碼。

q_reverse

透過遍歷拜訪每一個節點後將其放置於第一個位置，以達成反轉的目的。

struct list_head *current = head->next;
while (current != head) {
    struct list_head *tmp;
    tmp = current;
    current = current->next;
    list_move(tmp, head);
}

first commit 3e53ce5

q_reverseK

大抵與 q_reverse 相同，改良了多餘的變數 tmp 使用，且發現可以運用 list.h 的 list_for_each_safe，除此之外僅多了一計數器去做大小為 K 的分區動作。

list_for_each_safe (first, safe, head) {
    int count = 0;
    while (count < k - 1 && safe != head) {
        safe = safe->next;
        list_move(safe->prev, first->prev);
        first = first->prev;
        count++;
    }
}

commit 5e5ecae

q_ascend

原本會引發 bus error。

出處呢？能否用你對作業系統認知來解釋？能否用更精簡的程式碼重現 (reproduce)？

access 的翻譯是「存取」，而非「訪問」

~~經查詢~~ ， bus error 發生在嘗試訪問位於非對齊地址上的資料時，或者嘗試訪問不存在的記憶體位置時，在我原本的這段程式碼中，問題發生在 safe = node->next; 之前，若將最後一個節點刪除，將會在這一行引發 bus error ，因為此處的 node 已被刪除。

list_for_each_safe (node, safe, head) {
    all_nodes++;
    while (safe != head && node != head) {
        node_e = list_entry(node, element_t, list);
        safe_e = list_entry(safe, element_t, list);
        safe = safe->next;
        if (strcmp(node_e->value, safe_e->value) >= 0) {
            safe = node->next;
            list_del(node);
            q_release_element(node_e);
            del_nodes++;
            break;
        }
    }
    safe = node->next;
}
return all_nodes - del_nodes;

後來又想過先以 safe 保存 node->prev ，當節點被釋放後此時的 safe->next 將會是原本的 node->next 以繼續遍歷整個佇列，但若是該次的節點並沒有被刪除， safe 會是原本的 node。

     safe_e = list_entry(safe, element_t, list);
-    safe = safe->next;
+    safe = node->prev;


-    safe = node->next;
+    safe = safe->next;
}
return all_nodes - del_nodes;

功能部分完成 (問題紀錄)：

list_for_each_safe (node, safe, head) {
    all_nodes++;
    while (safe != head && node != head) {
        node_e = list_entry(node, element_t, list);
        safe_e = list_entry(safe, element_t, list);
        safe = safe->next;
        if (strcmp(node_e->value, safe_e->value) >= 0) {
            safe = node->next;
            list_del(node);
            q_release_element(node_e);
            del_nodes++;
            del = true;
            break;
        }
    }
    if (!del)
        safe = node->next;
}
return all_nodes - del_nodes;

錯誤紀錄

更新：發現改為不嚴格遞增/遞減就不會跑出錯誤訊息

l = [1 1 2]
cmd> ascend
l = [1 ... ]
ERROR:  Queue has more than 1 elements

commit 4c28e6c

最終版，修改判斷式

- strcmp(node_e->value, safe_e->value) >= 0
+ strcmp(node_e->value, safe_e->value) > 0

second commit 30e8bd5

q_descend

與 q_ascend 大抵相同，僅有 strcmp 之判斷式改變。

- strcmp(node_e->value, safe_e->value) > 0
+ strcmp(node_e->value, safe_e->value) < 0

q_sort

使用merge sort 實現排序，做的過程中發現升、降序最好能在 void merge 內做調整，因為若要再進行 q_sort 後反轉還需要多餘的判斷式，比較沒有效率。

實作透過快慢指標求得佇列的中間位置後使用 list.h 內定義的 list_cut_position 將中點之前的所有節點取出並移至 left 內，而 list_splice_init 將原本 head 剩餘的節點全部移至 right ，這麼做是為了在之後的 merge 可以直接合併回原本的 head。

LIST_HEAD(left);
LIST_HEAD(right);
list_cut_position(&left, head, mid);
list_splice_init(head, &right);

q_sort(&left, descend);
q_sort(&right, descend);

merge(head, &left, &right, descend);

merge

比較兩個佇列中第一個元素，並將較大的拼接回 head ，當一個佇列為空時，將另一個佇列拼接回 head ，由此完成最終的排序。

if (strcmp(left_first_node->value, right_first_node->value) >= 0)
    list_move(left->next, head->prev);
else
    list_move(right->next, head->prev);

...
    
if (left->next == left)
        list_splice_tail(right, head);
else
    list_splice_tail(left, head);

commit 6de00de

q_merge

透過 list_entry(node, queue_contex_t, chain) 去尋找 chain 之上級結構後將全部的佇列拼接到 head->next 的佇列裡，最後進行 q_sort 完成排序。

list_for_each_safe (node, safe, head) {
    // skip first iteration
    if (node != head->next) {
        queue_contex_t *next_block =
            list_entry(node, queue_contex_t, chain);
        total_elements += next_block->size;
        list_splice_init(next_block->q, first_queue);
    }
}

q_sort(first_queue, descend);

commit 2308658

研讀論文〈Dude, is my code constant time?〉後改進 lab0-c

文中介紹了一款稱做 dudect 的工具，用以在平台上透過程式執行時間的分布去判斷他是否在常數時間內進行，以防止 Timing attacks 導致一些敏感訊息被透過密碼學的方式反向推導。

這個工具的執行過程大概可以分為以下三個部分：

根據 fix-vs-random 類別定義，對執行時間進行多次採樣，模擬不同的測試環境下，執行時間的分布情形。
透過 prepare_percentiles 去統計執行時間的分布，計算出設定的閾值，並對執行時間的樣本做修剪，以消除那些執行時間較長的極端情況，從而提高測試的準確性。
在 update_statistics 中，透過 Welch's t-test 去判斷修剪前後執行時間的平均值差異，將產生一個預估值 't' ，若得到的 't' 超過設定的臨界值即判斷程式的執行時間不是常數時間。

student's t-distribution

student's t-distribution 通常用於樣本數小或是標準差未知的情形，型態接近於常態分布，根據自由度，越大會越接近常態分布，在 lab0-c 中，我們使用 is_insert_tail_const() 與 is_size_const() 進行採樣，而就我的理解， is_insert_tail_const() 的執行時間應是固定的，因此並不符合 t-distribution ，但在 fix-vs-random 測試資料中的佇列長度屬於隨機分布， is_size_const() 因此屬於連續的隨機操作，即符合 t-distribution。

當我們得到 t-distribution 的樣本後，即可透過上述的步驟三去進行 Welch's t-test 以檢驗執行時間是否為常數時間。

改善 lab0-c 中關於 percentile 的處理

在 dudect 專案中，對於一些不可靠的樣本(可能因為執行時被OS中斷)，會去做一些 post-processing 將其去除，而在目前的實作中缺少了 percentile 的設定，這部分對應到作者提供的專案中的 prepare_percentiles，因此在實作中的 dudect/fixture.c 補上以下 :

-    differentiate(exec_times, before_ticks, after_ticks);
-    update_statistics(exec_times, classes);
-    ret &= report();
+    bool first_time = percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
+    if (first_time) {
+        prepare_percentiles(exec_times, percentiles);
+    } else {
+        differentiate(exec_times, before_ticks, after_ticks);
+        update_statistics(exec_times, classes);
+        ret &= report();
+    }

指出論文和程式碼實作的出入。

研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案

list_sort.c 原始程式碼閱讀

count 變化	count 二進位	merge	pending 上的節點
0 $\to$ 1	0000 $\to$ 0001	no（ $2^{0}$ ）	1
1 $\to$ 2	0001 $\to$ 0010	no（ $2^{1}$ ）	1 $\leftarrow$ 1
2 $\to$ 3	0010 $\to$ 0011	yes	(2) $\leftarrow$ 1
3 $\to$ 4	0011 $\to$ 0100	no（ $2^{2}$ ）	2 $\leftarrow$ 1 $\leftarrow$ 1
4 $\to$ 5	0100 $\to$ 0101	yes	2 $\leftarrow$ (2) $\leftarrow$ 1
5 $\to$ 6	0101 $\to$ 0110	yes	(4) $\leftarrow$ 1 $\leftarrow$ 1
6 $\to$ 7	0110 $\to$ 0111	yes	4 $\leftarrow$ (2) $\leftarrow$ 1
7 $\to$ 8	0111 $\to$ 1000	no（ $2^{3}$ ）	4 $\leftarrow$ 2 $\leftarrow$ 1 $\leftarrow$ 1
8 $\to$ 9	1000 $\to$ 1001	yes	4 $\leftarrow$ 2 $\leftarrow$ (2) $\leftarrow$ 1
9 $\to$ 10	1001 $\to$ 1010	yes	4 $\leftarrow$ (4) $\leftarrow$ 1 $\leftarrow$ 1
10 $\to$ 11	1010 $\to$ 1011	yes	4 $\leftarrow$ 4 $\leftarrow$ (2) $\leftarrow$ 1
11 $\to$ 12	1011 $\to$ 1100	yes	(8) $\leftarrow$ 2 $\leftarrow$ 1 $\leftarrow$ 1
12 $\to$ 13	1100 $\to$ 1101	yes	8 $\leftarrow$ 2 $\leftarrow$ (2) $\leftarrow$ 1
13 $\to$ 14	1101 $\to$ 1110	yes	8 $\leftarrow$ (4) $\leftarrow$ 1 $\leftarrow$ 1
14 $\to$ 15	1110 $\to$ 1111	yes	8 $\leftarrow$ 4 $\leftarrow$ (2) $\leftarrow$ 1
15 $\to$ 16	1111 $\to$ 10000	no（ $2^{4}$ ）	8 $\leftarrow$ 4 $\leftarrow$ 2 $\leftarrow$ 1 $\leftarrow$ 1

根據這張圖，可以看到當本次 count 增加為 2 的冪次時都不會有 merge 的動作，這部分也可以在原始碼的核心部分看到，如下：

do {
    size_t bits;
    struct list_head **tail = &pending;

    /* Find the least-significant clear bit in count */
    for (bits = count; bits & 1; bits >>= 1)
        tail = &(*tail)->prev;
    /* Do the indicated merge */
    if (likely(bits)) {
        struct list_head *a = *tail, *b = a->prev;

        a = merge(priv, cmp, b, a);
        /* Install the merged result in place of the inputs */
        a->prev = b->prev;
        *tail = a;
    }

    /* Move one element from input list to pending */
    list->prev = pending;
    pending = list;
    list = list->next;
    pending->next = NULL;
    count++;
} while (list);

可以看到 if (likely(bits)) 不會被觸發的情況，只有在 count 為 2^k - 1 時，這邊有個巧妙的設計，考慮到鏈結串列的分區方式，如 2 ← 2 ← 1 也就是 count = 5 時，可以發現每一區都是透過 prev 去連接，所以這邊透過

for (bits = count; bits & 1; bits >>= 1)
        tail = &(*tail)->prev;

來取得要執行 merge 的兩個節點，這邊對應到的是表格中的 count 4-5, 0101 中，在 count 的二進位中，後面有幾個 1 即代表 merge 的起點需要往前幾個節點，像這一步就是要往前一個節點，起點為 2 ← (2) ← 1 ，並與他的 prev 也就是 (2) ← 2 ← 1 做 merge。

再來就是所有的節點都移至 pending 之後，將會執行以下，將所有的區塊合併成最後剩下兩個區塊，如在 4 ← 2 ← 1 結束時，將從尾端開始，合併為 4 ← 3 的區間，然而此時 next 指向頭部的 prev ，即 NULL ，而停止。

list = pending;
pending = pending->prev;
for (;;) {
    struct list_head *next = pending->prev;

    if (!next)
        break;
    list = merge(priv, cmp, pending, list);
    pending = next;
}

最後，做最後的 merge_final ，這裡不同於先前的 merge ，還會進行雙向鏈結串列的重建，將所有的分區合併為同一個整體。

merge_final(priv, cmp, head, pending, list);

於 lab0-c 實作 List_sort 與 Tim_sort

參考 yu-hisennn。

在 Linux 核心的鏈結串列排序中提供的 lib/list_sort.c 中，可以觀察到在串列的結構上與我們本次實作內容是相同的 (都是來自Linux 核心原始程式碼) ，但在導入本次實作的過程中發現了因為這個專案本身是執行在 Linux 的 kernal space ，因此有些導入的函式庫在我們的實作中就不能使用了，也導致有些巨集或是型態需要我們自己去定義，如下的 unlikely 原本在 <linux/compiler.h> 中被定義，但在我們的實作中需要去 "list_sort.h" 中透過 GCC 的內建函數 builtin_expect 去定義 #define unlikely(x) __builtin_expect(!!(x), 0) ；另外也知道了 __attribute__((nonnull(2,3))) 是為了讓某些函式的參數不為 NULL 而設定的。

list_sort.c:86:7: error: implicit declaration of function ‘unlikely’ [-Werror=implicit-function-declaration]
   86 |   if (unlikely(!++count))
      |       ^~~~~~~~
list_sort.c: In function ‘list_sort’:
list_sort.c:219:7: error: implicit declaration of function ‘likely’ [-Werror=implicit-function-declaration]
  219 |   if (likely(bits)) {
      |       ^~~~~~

接下來需要在 "qtest.c" 中實作 do_sort_list ，這邊是直接參考 do_sort 的流程，然後作些許修改，基本上差異只在原本呼叫 q_sort 改變為 list_sort ，並調整輸入參數。

if (!current || !current->q)
    report(3, "Warning: Calling sort on null queue");
else
-    cnt = q_size(current->q);
+    list_sort(NULL, current->q, list_cmp);
error_check();

這裡還可以改進，加入 ascend 及 descend 的參數

最後在 console_init 的部分加上 ADD_COMMAND(list_sort, "Use list_sort in Linux to sort the queue in ascending order", ""); 完成改動，從這邊也去觀察了 console.h 中 #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) 將剛剛定義的 do_list_sort 加入 console_init 內，然後在 "driver.py" 中就可以透過讀取 traces ~~資料夾~~ 目錄的指令 .cmd 檔去執行，大概理解了 qtest 是如何被執行的。

diretory 的翻譯是「目錄」，而非「資料夾」(folder)

最終在 make 後執行 ./qtest

l = [2 4 2 3 1]
cmd> list_sort
l = [1 2 2 3 4]

commit 0f77419

可以加入原始 q_sort 與 list_sort 之間的效能比較

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

marvin0102

效能比較與分析

為了使用 perf 效能測試工具寫了兩個檔案 sort_test.c 與 qsort_test.c 用以測試 timsort, list_sort 與 qsort 的效能，其中在資料的設計中，透過 create_sample 可以產出完全隨機或是以排序好的資料集，透過註解的方式去調整。

// elem->val = rand();
elem->val = i;

除此之外，在排序好的資料集中，又另外做了兩個函式以產生不同的分布情形

q_create_runs

在一個已排序好的資料裡，分成多個區間，且每隔一個個區間就反轉，如
0 1 2 3 4 8 7 6 5 9 10 11 12 ，此為為了適配 timsort 特性的資料集。

void q_create_runs(struct list_head *head)
{
    if (head == NULL || head->next == head)
        return;
    struct list_head *first;
    struct list_head *safe;
    list_for_each_safe (first, safe, head) {
        int count = 0;
        while (count < rand() % 3 + 3 - 1 && safe != head) {
            safe = safe->next;
            list_move(safe->prev, first->prev);
            first = first->prev;
            count++;
        }
    }
}

shaffle_partially

每隔幾個節點，將目前的節點與尾端節點互換，並將目前位置設定為尾端，這樣的結果會是類似 0 8 2 3 4 1 6 7 5 ，部分被打亂，較無法從資料集看出效能的關聯，暫時廢棄。

static void shaffle_partially(struct list_head *head)
{
    int offset = 0;
    int limit;
    struct list_head *tail = head->prev;
    struct list_head *current = tail;
    struct list_head *tmp;
    while(current != head && current->prev != head) {
        limit = rand() % 3 + 3;
        offset = 0;
        while (offset <= limit) {
            if(current->prev == head) {
                break;
            }
            current = current->prev;
            offset++;
        }
        tmp = current->prev;
        list_move(current, tail);
        list_move(tail, tmp);
        current = tail;
    }
}

在 "`SAMPLES 1000`"、"資料集為 `sorted` "、"套用 `q_create_runs` "的情況：

這裡令人疑惑的點是 timsort cache-misses 的表現竟然是這邊最差的，檢查過後資料集的分布與預想也相同，另外在比較次數的方面來觀察 timsort, list_sort ，可以看到 timsort 的比較次數竟然較多，這點不符合他創建 runs 以避免多次比較的特性。

更新：
在改變測試次數後，雖然還是有一定的浮動範圍，但明顯可以觀察出 timsort 出現的範圍會較其他兩者較小許多。

對於 timsort 比較次數較高的情形，我給出的解釋是在實作中 find_run 過程中的比較也會記錄在此 Comparisons 內，但在上述的討論中，比較次數可能僅限於 merge 的過程中，所以這裡才無法良好的反映出 timsort 比較次數較少的這個特性。

timsort 的表現為
Comparisons 約在 (9000, 10000) 範圍區間

==== Testing tim_sort ====
  Comparisons:    9250
  List is sorted

Performance counter stats for './sort_test' (1000 runs):

             2,376      cpu_core/cache-misses/                                        ( +-  2.99% )
            20,762      cpu_core/cache-references/                                     ( +-  0.40% )
         1,783,135      cpu_core/instructions/                                        ( +-  0.03% )
         1,211,219      cpu_core/cycles/                                              ( +-  0.28% )
                74      page-faults                                                   ( +-  0.04% )

         0.0012438 +- 0.0000219 seconds time elapsed  ( +-  1.76% )

list_sort 的表現為
Comparisons 約在 (8600, 8800) 範圍區間

==== Testing list_sort ====
  Comparisons:    8726
  List is sorted

Performance counter stats for './sort_test' (1000 runs):

     3,305      cpu_core/cache-misses/                                        ( +-  1.99% )
    23,908      cpu_core/cache-references/                                     ( +-  0.34% )
 1,795,388      cpu_core/instructions/                                        ( +-  0.03% )
 1,167,131      cpu_core/cycles/                                              ( +-  0.28% )
        72      page-faults                                                   ( +-  0.04% )

 0.0014723 +- 0.0000206 seconds time elapsed  ( +-  1.40% )

q_sort 的表現為

Performance counter stats for './qsort_test' (1000 runs):

     4,364      cpu_core/cache-misses/                                        ( +-  1.43% )
    23,055      cpu_core/cache-references/                                     ( +-  0.35% )
 1,958,077      cpu_core/instructions/                                        ( +-  0.03% )
 1,173,050      cpu_core/cycles/                                              ( +-  0.26% )
        72      page-faults                                                   ( +-  0.05% )

 0.0013430 +- 0.0000217 seconds time elapsed  ( +-  1.61% )

在 "`SAMPLES 1000`"、"資料集為 `sorted` " 的情況：

出現了一個令人費解的情況，根據 timsort 的特性，可以確定的是他從頭到尾只會產生一個 run ，由比較次數為 999 也可以看出他一次就做完排序了，但不知道為什麼 timsort cache-misses 還是這裡面最高的，且 list_sort 的 bottom up 特性較傳統 merge_sort ，即此處的 q_sort 對 cache 較為友善，但在這邊測試出來的表現中，卻發現 q_sort 相較於 list_sort 的 cache misses 更低。

更新：
後來發現原本的 sort_test.c 中，另外還有 Warm up 的動作，所以相對於 q_sort ，共是三倍的執行量，推測原本的 warm up 是為了在實際執行前將 cache 使用狀態初始化，讓測量結果浮動值相對減少，實際上當註解掉 Warm up 之後多次使用 perf stat --repeat 100 的結果確實有很大的浮動範圍， cache-misses 從 1000-9000 都有可能出現，因此在這裡將測量次數改為 1000 ，以取代原本的 Warm up 功能，以前幾次的測量作為初始化 cache 的角色。

回頭測試當有 Warm up 時的執行效能，發現浮動值依然巨大， cache-misses 也約是 1000-9000 的範圍，不知道 Warm up 使否實際對 cache 的使用統計有幫助

上面所提到 timsort cache-misses 是這裡面最高，後來測試改為 1000 次後，發現他的浮動範圍整體會低於其他兩者，另外 q_sort 表現將會是最差的，較符合預期結果。

timsort 的表現為

==== Testing tim_sort ====
  Comparisons:    999
  List is sorted

 Performance counter stats for './sort_test' (1000 runs):

     2,089      cpu_core/cache-misses/                                        ( +-  2.91% )
    21,309      cpu_core/cache-references/                                     ( +-  0.36% )
 1,557,116      cpu_core/instructions/                                        ( +-  0.03% )
 1,162,575      cpu_core/cycles/                                              ( +-  0.29% )
        73      page-faults                                                   ( +-  0.04% )

 0.0014325 +- 0.0000177 seconds time elapsed  ( +-  1.24% )

list_sort 的表現為

==== Testing list_sort ====
  Comparisons:    5036
  List is sorted

 Performance counter stats for './sort_test' (1000 runs):

     2,282      cpu_core/cache-misses/                                        ( +-  2.93% )
    20,830      cpu_core/cache-references/                                     ( +-  0.39% )
 1,705,274      cpu_core/instructions/                                        ( +-  0.03% )
 1,092,431      cpu_core/cycles/                                              ( +-  0.33% )
        73      page-faults                                                   ( +-  0.04% )

 0.0011818 +- 0.0000218 seconds time elapsed  ( +-  1.84% )

q_sort 的表現為

 Performance counter stats for './qsort_test' (1000 runs):

     3,955      cpu_core/cache-misses/                                        ( +-  1.64% )
    23,143      cpu_core/cache-references/                                     ( +-  0.36% )
 1,870,709      cpu_core/instructions/                                        ( +-  0.03% )
 1,230,617      cpu_core/cycles/                                              ( +-  0.28% )
        72      page-faults                                                   ( +-  0.05% )

 0.0011824 +- 0.0000195 seconds time elapsed  ( +-  1.65% )

在 "`SAMPLES 1000`"、"資料集為 `random` " 的情況：

在這個情況中 timsort, list_sort 這兩個 bottom up 的 merge sort 演算法中， cache-misses 的差異不大，但 q_sort 的 cache-misses 相對來說就比較多。

timsort 的表現為
Comparisons 約在 (9000, 10000) 範圍區間

==== Testing tim_sort ====
  Comparisons:    9474
  List is sorted

 Performance counter stats for './sort_test' (1000 runs):

     3,148      cpu_core/cache-misses/                                        ( +-  2.17% )
    21,937      cpu_core/cache-references/                                     ( +-  0.37% )
 1,871,182      cpu_core/instructions/                                        ( +-  0.03% )
 1,320,028      cpu_core/cycles/                                              ( +-  0.25% )
        74      page-faults                                                   ( +-  0.04% )

 0.0015920 +- 0.0000204 seconds time elapsed  ( +-  1.28% )

list_sort 的表現為
Comparisons 約在 (8600, 8800) 範圍區間

==== Testing list_sort ====
  Comparisons:    8725
  List is sorted

Performance counter stats for './sort_test' (1000 runs):

     3,195      cpu_core/cache-misses/                                        ( +-  2.27% )
    22,494      cpu_core/cache-references/                                     ( +-  0.40% )
 1,844,444      cpu_core/instructions/                                        ( +-  0.03% )
 1,280,199      cpu_core/cycles/                                              ( +-  0.27% )
        73      page-faults                                                   ( +-  0.04% )

 0.0016114 +- 0.0000207 seconds time elapsed  ( +-  1.29% )

q_sort 的表現為

 Performance counter stats for './qsort_test' (1000 runs):

     3,727      cpu_core/cache-misses/                                        ( +-  1.61% )
    22,137      cpu_core/cache-references/                                     ( +-  0.40% )
 1,957,399      cpu_core/instructions/                                        ( +-  0.03% )
 1,258,764      cpu_core/cycles/                                              ( +-  0.26% )
        74      page-faults                                                   ( +-  0.05% )

 0.0015677 +- 0.0000200 seconds time elapsed  ( +-  1.28% )

commit 0caab3b

目前僅有二種資料集，能否針對 Timsort (及其變種演算法) 提出更通用的測試資料產生器？

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

亂數 + 論文閱讀

在 qtest 提供新的命令 shuffle

利用 Fisher–Yates shuffle 演算法來實作洗牌（shuffle）

for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

tic-tac-toe

蒙地卡羅搜尋 ( Monte Carlo tree search )

MCTS 為前段時間裡火紅的 AlphaGo 中使用的主體演算法，被廣泛運用在多個選擇中找出模擬過程中最為恰當的一個，像是 tic-tac-toe 、棋類競賽，更不同的甚至是自走車導航，都可以看見 MCTS 的身影。

而 MCTS 的評估過程，主要可以分為三個部分：

select

選擇下一步模擬的節點，而每一次的選擇都會透過 UCB 去計算出較適當的節點，此處為了讓選擇能夠同時兼顧不同路線的可能性以及最佳策略的準確性，也就是要同時有 exploration 與 exploitation ，最終的搜尋樹才有機會探索更多路徑且保持良好的效率。
$U C B = \frac{w_{i}}{n_{i}} \times C \sqrt{\frac{l n (N_{i})}{n_{i}}}$

其中 $w_{i}$ 為經過此節點後獲勝的次數、 $n_{i}$ 為選擇該節點的總次數、 $N_{i}$ 為該點的 parent 被選擇的總次數。

從 $U C B$ 可以看出，透過左項與右項的相互對抗，在選擇節點上就是在探索與偏好勝率較高這兩點做平衡。

expand or rollout

根據選擇到的節點，若該節點已被選擇過，則將進行 expand ，生成新的子節點以模擬更多樣的情況，若沒被選擇過，會進行 rollout ，也就是一直隨機進行選擇直至出現結果，這邊的過程其實也可以透過計算 $U C B$ 而看出何時會進行 expand 或 rollout。

backpropagate

當我們選擇到一個全新的節點時，將一直重複的 rollout 直到產出結果，而根據這個結果去更新所有經過節點的 $n_{i}$ 、 $w_{i}$ 即為 backpropagate ，一般來說若是分成 "勝利、平手、落敗" 的三種結果，會以 (-1, 0, 1) 去更新 $w_{i}$ 的數值。

最後，根據這三點去更新完搜尋樹之後，實際上在選擇下一步時，會去選擇 $w i n_r a t e = \frac{w_{i}}{n_{i}}$ 最高者。

僅以 (1, 0) 去表示輸贏，且沒有平手的狀況，展示 MCTS 的圖像化過程 (C = $\sqrt{2}$ )：

initial

first select

second select

third select

建立完蒙地卡羅搜尋樹後，將會去選擇 $w i n_r a t e = \frac{w_{i}}{n_{i}}$ 最高者做為下一步，因此在在第一步，將選擇左邊節點。

觀察 MCTS 的模擬過程之後，我發現越遠的節點，因為 $U C B$ 中若節點未被選擇過，將會是無限大的關係，他被選擇的次數必然會較低，反之越接近 root 的節點將有較多種的可能性，這可能導致若 MCTS 的迭代次數過少，在樹的某一層 (第 n 次選擇節點) 後，將來的路線將有很大的侷限性，或許可以透過 $U C B$ 中 exploration 與 exploitation 的調整去做取捨。

提出更系統的討論，解釋 MCTS 的局限和對運算的要求。

fixed_power_int 簡記

基本的功能可以拆解成兩部分，這個部分是為了檢測 $x^{2^{n}}$ 項是否為一，其中的 n 為次方樹，以 $x^{5}$ 為例， $n = 101_{2}$ ，因此在第一次、第三次的遞迴都會進入這個判定內。

if (n & 1) {
    result *= x;
    result += 1UL << (frac_bits - 1);
    result >>= frac_bits;
}
n >>= 1;

另一部分則是為了在檢查 $n$ 的每個二進位 bits 後，讓 $x$ 的次方項乘二，即為了配合 $n$ 的二進位表示方式， $n = 101_{2} = 1 \cdot 2^{0} + 0 \cdot 2^{1} + 1 \cdot 2^{2}$ ，
舉例來說在檢查 $n$ 的第一個 bits 時， $x$ 相對應的就是 ${x^{2}}^{0}$ ，檢查第三個 bits 的時候 $x$ 相對應的就是 ${x^{2}}^{2} = x^{4}$ ，這邊在做的就是更新 $x$ 的次方。

x *= x;
x += 1UL << (frac_bits - 1);
x >>= frac_bits;

這裡有一個疑惑是為何在每次的乘法過後都要進行無條件進位，這樣的做法與我做無條件捨去在精度上會有很大的差異嗎。

上面的推理已有答案，你應該自行計算。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

定點數 log2 計算

參考 Shawn531

為了計算 $l o g_{2} (x)$ ，首先以二進位科學記號的方式將 $x$ 的冪次與剩餘部分分離為 $x_{m}, x_{n}$ ，若 $x = 11$ ，則分離為 $2^{3} * 1.375$ 在取 log2 時 $2^{3}$ 將不納入計算中，且 $y_{m} = 3$ ，此處即對應到 "log2_fix" 中的：

while (x < 1U << precision) {
    x <<= 1;
    y -= 1U << precision;
}

while (x >= 2U << precision) {
    x >>= 1;
    y += 1U << precision;
}

前處理後，設定
$y_{n} = l o g_{2} (x_{n})$ $x_{n} = 2^{y_{n}}$

因 $1 \leq x_{n} \leq 2$ ， $0 \leq y_{n} \leq 1$ ， $y_{n}$ 的值將可以表示為:
$y = y_{1} \cdot 2^{- 1} + y_{2} \cdot 2^{- 2} + y_{3} \cdot 2^{- 3} + y_{4} \cdot 2^{- 4} + . . .$

整理過後
$y = 2^{- 1} (y_{1} + 2^{- 1} (y_{2} + 2^{- 1} (y_{3} + 2^{- 1} (y_{4} + . . .))))$

將 $y_{n}$ 帶入 $x_{n} = 2^{y_{n}}$
$x = 2^{2^{- 1} (y_{1} + 2^{- 1} (y_{2} + 2^{- 1} (y_{3} + 2^{- 1} (y_{4} + . . .))))}$

為了求得 $y_{n}$ 之近似值，將兩側平方
$x^{2} = 2^{y_{1}} \cdot 2^{2^{- 1} (y_{2} + 2^{- 1} (y_{3} + 2^{- 1} (y_{4} + . . .)))}$

且這裡已知 $2^{- 1} (y_{2} + 2^{- 1} (y_{3} + 2^{- 1} (y_{4} + . . .)))$ 必小於 1，即 $1 \leq 2^{2^{- 1} (y_{2} + 2^{- 1} (y_{3} + 2^{- 1} (y_{4} + . . .)))} \leq 2$ ，因此可以透過 $x^{2}$ 是否大於 2 來判斷 $y_{n}$ 部分第一項 $y_{1}$ 是否為 0。

為以下兩種情況：
$x^{2} \leq 2, y_{1} = 1$ or $x^{2} > 2, y_{1} = 0$

完成後，將 $x^{'}$ 設定為 $\frac{x^{2}}{2}$ ，如此是為了繼續執行
$x^{'} = 2^{2^{- 1} (y_{2} + 2^{- 1} (y_{3} + 2^{- 1} (y_{4} + . . .)))}$

進行多次逼近後，即可得 $y_{n}$ 各個位數的值，已求得完整的 $y = y_{m} . y_{n}$ ，即程式碼中這一部分：

for (size_t i = 0; i < precision; i++) {
    z = z * z >> precision;
    if (z >= 2U << precision) {
        z >>= 1;
        y += b;
    }
    b >>= 1;
}

此處的 z 即 $x^{2}$ ，並在每次的迭代後 z >>= 1 即將下一次的 $x^{'}$ 設定為 $\frac{x^{2}}{2}$ ，而 b 則為更新目前的 $y_{n}$ ，在這裡是直接在本體 $y$ 進行運算，沒有分離成 $y = y_{m} . y_{n}$ 。

在不同精度下，與原本浮點數運算的 $l o g_{2}$ 比較圖：

可以看到在 fraction bit 大於 8 之後，基本上與浮點數在精度的差距就不會到太大。

commit 71d0120

TODO: ttt 的引入，定點數與浮點數運算的效能分析、log2_lshift16 之改進。

2024q1 Homework1 (lab0)

Reviewed by mervin0102

開發環境

針對佇列操作的程式碼實作

q_new

q_insert_head and q_insert_tail

q_insert_head

q_insert_tail

q_free

q_remove_head and q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_ascend

q_descend

q_sort

merge

q_merge

研讀論文〈Dude, is my code constant time?〉後改進 lab0-c

student's t-distribution

改善 lab0-c 中關於 percentile 的處理

研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案

list_sort.c 原始程式碼閱讀

於 lab0-c 實作 List_sort 與 Tim_sort

效能比較與分析

q_create_runs

shaffle_partially

在 "SAMPLES 1000"、"資料集為 sorted "、"套用 q_create_runs "的情況：

在 "SAMPLES 1000"、"資料集為 sorted " 的情況：

在 "SAMPLES 1000"、"資料集為 random " 的情況：

亂數 + 論文閱讀

在 qtest 提供新的命令 shuffle

tic-tac-toe

蒙地卡羅搜尋 ( Monte Carlo tree search )

fixed_power_int 簡記

定點數 log2 計算

在不同精度下，與原本浮點數運算的 log2 比較圖：

Read more

2024q1 Homework5 (assessment)

2024q1 Homework6 (integration)

2024q1 Homework4 (quiz3+4)

2024q1 Homework2 (quiz1+2)

Reviewed by `mervin0102`

`q_new`

在 "`SAMPLES 1000`"、"資料集為 `sorted` "、"套用 `q_create_runs` "的情況：

在 "`SAMPLES 1000`"、"資料集為 `sorted` " 的情況：

在 "`SAMPLES 1000`"、"資料集為 `random` " 的情況：

在不同精度下，與原本浮點數運算的 $l o g_{2}$ 比較圖：