2024q1 Homework1 (lab0)

contributed by < YaRu056 >

開發環境

$gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

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

實作指定佇列操作

q_delete_dup

在實作 q_delete_dup 時以為只要出現重複值的節點都要刪除，透過測資才發現是連續重複的值才需要刪除。

l = [1 3 3 5 6 7 3]
cmd> dedup
l = [1 5 6 7 3]

q_reverse

在實作 q_reverse 時，先畫圖理解了鏈結之間的關係，實作成功後，才看到 list.h 中看到有 list_move_tail 的函式可以使用

程式碼

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    struct list_head *tmp = NULL;
    struct list_head *cur = head;
    int size = q_size(head);
    while (size >= 0) {
        tmp = cur->prev;
        cur->prev = cur->next;
        cur->next = tmp;
        cur = cur->prev;
        size--;
    }
}

1. cur 指向目前我們要處理的節點，tmp則是指向 cur 前一個節點

2. 先把 cur->prev做更新， cur->prev=cur->next

digraph "reverse1"
{
    node[shape=plaintext];
    cur [fontcolor="red"];
    tmp[fontcolor="blue"];    
    node[shape=circle ,width=0.5];
    head [fontcolor="black"];
    A [fontcolor="black"];
    B [fontcolor="black"];
    C [fontcolor="black"];
    {
        rankdir="LR";
        rank="same";
        head:nw->A:ne[color="red"];
        C:se->head:sw;
        head->A;
        A->B->C;
        C->B->A->head;
    }
    cur->head;
    tmp->C;
}  
abort(9). Build with -s ASSERTIONS=1 for more info.

3. 再更新 cur->next=tmp

4. 再更新 cur 和 tmp 重複上面步驟，直到遍歷 ??? 完所有的節點

注意用語。

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

最後遍歷 完所有節點

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

q_reverseK

先建立一個新的佇列，以 size=k 個大小切成一段，反轉後，加在新的佇列的結尾，重複執行 q_size(head)/k 次後結束，最後將新的佇列移到 head 前面

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

q_sort

本例中，應指「測試項目」(test item)，而非「測試資料」(test data)。

在實作 q_sort 時發現他不是單純看值的大小，查看 qtest.c 後在第 614 行中 strcmp(item->value, next_item->value)發現需要藉由 strcmp 去作排序的判斷，測試項目時得到了以下的結果。

> l = [24 13 99 2 5 3]
cmd> sort
l = [13 2 24 3 5 99]

因為用既定的印象去寫排序，除錯了好一陣子，查看規格和測試內容真的很重要，可以少走一些錯路！

原先使用泡沫排序法，但因測試中會要求排序的時間複雜度，因此改為合併排序法。

不要裝可愛。

q_merge

誠實面對自己。

不要說「時間快不夠了，先寫了一個粗糙的版本」，要是 Apple 工程師用這種態度開發軟體，你敢把 iPhone 放在你的口袋嗎？本課程重視工程的嚴謹，你的起步高低是一回事，但持續投入並謹慎面對各式工程議題，是「工程」不該少的態度。

避免贅詞。

queue

q_new()

q_insert_head()

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

測試結果：
最後測試17 trace-17-complexity 始終無法通過

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
---     trace-17-complexity     0/5
---	TOTAL		95/100

研讀指定的論文。

分析 Linux 核心的 lib/list_sort.c

特點：

• 在排序前會先將 circular 變成 doubly linked list，排序完成後在轉為 circular
• 每個已排序的子串列的大小都是 2 的冪次方
• 任一時間點串列的大小都是由小到大
• 它在待合併的元素數量與它們的大小相等時進行兩個子串列的合併，確保每次最終合併大小最差情況下都是 2:1，可以降低比較次數
• 使用 DFS 順序合併，減少 cache thrashing 現象，提升快取的使用率

確保每次執行至少 2:1 的平衡合併

當有三個大小為

$2^k$ 的待處理子列表，我們會合併前兩個

$2^k$ 個節點，它們就會合併成一個大小為

$2^{(k+1)}$ 的列表，這可以有效降低比較次數，另外，list_sort 和 在 commit b5c56e0 中提及的 論文 Queue-Mergesort 方法不同，前者則是出現兩個

$2^k$ 大小的串列不會立即合併，會一直等到下一個

$2^k$ 大小的串列出現後，前面的兩的鍊結串列才會被合併起來，後者則是將每個要排序的節點放入一個獨立的鍊結串列中，形成一個串列集合，每次從串列集合中取出兩個串列並合併成一個新的已排序的列表，在將新的已排序列表加入到串列集合的尾端，重複合併操作直到串列集中只剩下一個串列，而前者 確保 2:1 的串列合併方式，可以避免 cache thrashing 的發生。

控制 2:1 合併：
count 的值決定了何時進行合併，count 是紀錄待處理串列 pending 中的節點數量。當目前的 count + 1 後，會設置第 k 個位元為 1，0～k-1 個位元為 0 ，這時兩個長度為

$2^k$ 的 list 會做合併，並留下一個長度為

$2^k$ 的 list 。
當 count+1 不等於

$2^k$時，就會做合併。
下面舉一個簡單的例子來看
以 [5,3,1,2,8,6,7,9,0] 為例，排序為升序

count= 0
–> count + 1 =

$2^0$
因為 bits 為 0，不需 merge。list->prev = pending 因為 pending 為 NULL，所以 list->prev 也指向 NULL。
pending 節點數量 + 1，list 節點數量 - 1，count + 1，pending->next = NULL

此時count= 1 =

$1_2$
–> count + 1 =

$2^0$+

$2^0$ (不做合併)
因為 bits 為 1，tail = &(*tail)->prev;
此時 tail 指向 5->prev

此時count = 2 =

${10}_2$
–> count + 1 =

$2^1$+

$2^0$ (做指定串列合併)
此時合併的串列大小是 1+1
*a = *tail, *b = a->prev;

Merge
a = merge(priv, cmp, b, a)

a>b

return head
因 b->prev = NULL,a->prev = b->prev,所以 a->prev = NULL ，*tail = a;

此時count= 3 =

${11}_2$
–> count + 1 =

$2^1$+

$2^0$+

$2^0$ (不做合併)

bits = 3 時，tail 指向 3->prev，bits = 1 時，tail 指向 5->prev
此時count= 4 =

${100}_2$
–> count + 1 =

$2^1$+

$2^1$+

$2^0$ (做指定串列合併)
此時合併的串列大小是 1+1

合併後的結果

此時count=5 =

${101}_2$
–> count + 1 =

$2^2$+

$2^0$+

$2^0$ (做指定串列合併)
此時合併的串列大小是 2+2
tail = &(*tail)->prev;
此時 *tail 指向 1

合併後的結果

此時count=6 =

${110}_2$
–> count + 1 =

$2^2$+

$2^1$+

$2^0$ (做指定串列合併)
此時合併的串列大小是 1+1
tail = &(*tail)->prev;
此時 *tail 指向 1

合併後

此時count= 7 =

${111}_2$
–> count + 1 =

$2^2$+

$2^1$+

$2^0$+

$2^0$ (不合併)
tail = &(*tail)->prev;
此時 tail 會指向 1->prev

此時count= 8 =

${1000}_2$
–> count + 1 =

$2^2$+

$2^1$+

$2^0$+

$2^0$ (做指定串列合併)
此時合併的串列大小是 1+1

合併後

當走遍 list 後，將所有 pending list 合併在一起

合併

當next 指向 Null 時，做最終合併，並且恢復成circular

相比之下，Linux/lib/list_sort.c 使用的是 in-place 演算法，且透過維持每次最終合併大小在最差情況下都是 2:1 去降低比較次數，同時避免 cache thrashing 的發生。

針對 比較次數 和 cache miss rate 來分析，這邊參考此篇分析方法，我先用 ADD_COMMAND 加入了 ㄔㄛlistSort ?? 這到命令，執行時會呼叫引入 qtest.c 的 list_sort 。選擇 260000 以及 270000 這兩個排序數量，一個在

$2^{18}$(262144) 前，一個在

$2^{18}$ 後，可以看出佇列的長度對於比較次數的影響，用以下命令測量執行時間。

cmd> new
cmd> it RAND 260000
cmd> time sort
Delta time = 0.188
cmd> free
l = NULL
cmd> new
cmd> it RAND 270000
cmd> time sort
Delta time = 0.195
cmd> free
l = NULL
cmd> new
cmd> it RAND 260000
cmd> time listSort
Delta time = 0.129
cmd> free
l = NULL
cmd> new
cmd> it RAND 270000
cmd> time listSort
Delta time = 0.139
cmd> free
l = NULL

在 260000 的長度下，兩者差了 1.46 倍。 而在 270000 的長度下，則差了 1.4 倍。

比較次數

對於比較次數的探討，我們可寫成以下形式：

$nlo{g}_{2}n-K_n+O(1)$
其中，以下 merge sort 的變形 (variants)，領導係數 (leading coefficient) 皆為

$lo{g}_{2}n!$，探討的著重點在於一次項係數 K。

針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式

透過 perf 分析程式效能

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

用 lscpu 指令 來查看快取大小

L1d cache:                          288 KiB (6 instances)
L2 cache:                           7.5 MiB (6 instances)
L3 cache:                           18 MiB (1 instance)

測試環境 L3 Cache 大小為 18 MB，而 sizeof(element_t) = 24 ，因此測試時故意使用大約兩倍 L3 Cache 大小的資料量來製造 cache miss ，36 * 1024 個 sorted list，每個 sorted list 有 64 個 node 。

Massif 可分析以下:

• Heap blocks;
• Heap administration blocks;
• Stack sizes.

可搭配視覺化工具展現給定程式在執行時期的記憶體行為

command 的翻譯是「命令」，而非「指令」

命令如下

$ valgrind --tool=massif ./qtest -f traces/trace-massif.cmd

其中 traces/trace-massif.cmd 的內容只要複製 traces/trace-17-complexity.cmd 並稍做修改即可，例如測試 q_insert_tail
利用 ms_print 可以輸出此檔案內容

$ ms_print massif.out.<pid>

# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
option simulation 1
it
option simulation 0

    MB
1.234^  #                                                                     
     |  #                                                                     
     |  #                                                      :              
     |  #                                      :      :        :              
     |  #    :  :                              :      :        :              
     |  #    :  :               :           :  :      :        :             :
     |  #    :  :               :           :  :      :        :             :
     |  #    :  :               :           :  :   :  :        :             :
     |  #    :  : :        :    :           :  ::  :  :        :         :   :
     |  #    :  : :  :     :    :  : :  :   :  ::  : :::       @         :  ::
     |  #    :  : :  :     :    :  : :: :   :  ::  : :::     : @         :: ::
     |  #:   :: :::  : :   ::   :  : :: :   :  ::  : :::  @  ::@         :: ::
     |  #    :: :::  : :   ::   :@ : :: :   :: ::  : :::: @  ::@         :: ::
     |  #    :: :::  : :   ::   :@ : :: :   :  ::  : :::: @ :::@   :     :: ::
     |  #  : ::::::  : :   ::   :@ : :: :   :  ::  : :::: @ :::@ : :     :: ::
     |  #  : ::::::  : : : ::   :@:: :: :   :  ::  : :::::@::::@ :::     :: ::
     | :#  ::::::::  : ::: ::   :@::::: :   :  ::  : :::::@::::@::::  :  :: ::
     | :#  ::::::::::: ::: :::: :@::::: :   :  ::@@: :::::@::::@:::: ::  :: ::
     | :#  ::::::::: :@::::::::::@::::: ::  :  ::@ : :::::@::::@:::::@: ::@:::
     | :# :::::::::: :@::::::::::@::::::::@@: @::@ : :::::@::::@:::::@::::@:::
   0 +----------------------------------------------------------------------->Gi
     0                                                                   14.66

Number of snapshots: 95
 Detailed snapshots: [2 (peak), 17, 30, 40, 43, 46, 58, 68, 78, 88]

. : normal snapshot
@: detailed snapshot
#: peak snapshot, only taken after a deallocation happens
可以使用由 KDE 社群開發的 Massif-Visualizer 工具，產生記憶體使用情形的時間分佈圖：

massif-visualizer massif.out.<pid>

附上你的解讀

實作 shuffle 命令

Fisher-Yates Shuffle：
這邊使用 Fisher-Yates Shuffle 來實作 shuffle 命令

1. 先用 q_size 取得 queue 的大小 len。
2. 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。
3. 隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束。

cmd> new
l = []
cmd> ih RAND 10
l = [oyfgt zeueulokh kxqsrp hxewjmlv epatczl jmlwes bahsdmycm txzree zjdjv syfxcrxt]
cmd> shuffle
l = [epatczl oyfgt syfxcrxt jmlwes zjdjv kxqsrp txzree bahsdmycm hxewjmlv zeueulokh]

統計方法驗證 shuffle

利用 lab0-d 提供之測試程式進行實驗，結果如下

1. 先計算 chi-squared test statistic

$X^2$

$$\begin{array}{rl}{X}^2& ={\displaystyle \sum _{i=1}^n{\displaystyle \frac{(O_i-E_i{)}^2}{E_i}}}\end{array}$$

$X^2$ : Pearson's cumulative test statistic

$O_i$: the number of observations of type i

$E_i$: the expected count of type i

Expectation:  41666
Observation:  {'1234': 41861, '1243': 41825, '1324': 41576, '1342': 41526, '1423': 41796, '1432': 41420, '2134': 41761, '2143': 41855, '2314': 41914, '2341': 41710, '2413': 41755, '2431': 41911, '3124': 41709, '3142': 41795, '3214': 41577, '3241': 41252, '3412': 41649, '3421': 41650, '4123': 41447, '4132': 41378, '4213': 41691, '4231': 41561, '4312': 41689, '4321': 41692}
chi square sum:  16.480247683962947

在測試 shuffle 1000000 次後，二十四種結果各自的頻率如下表：

	觀察到的頻率	期待的頻率	${\displaystyle \frac{（O_i-E_i{)}^2}{E_i}}$
1234	41627	41666	0.9126146018336293
1243	42002	41666	0.6067537080593289
1324	41855	41666	0.1944031104497672
1342	42132	41666	0.4704075265204243
1423	41482	41666	0.4056064897038353
1432	41520	41666	1.4524072385158162
2134	41368	41666	0.2166034656554505
2143	41550	41666	0.8573177170834734
2314	41334	41666	1.4761196179138867
2341	41902	41666	0.0464647434358950
2413	41743	41666	0.1901070417126674
2431	41413	41666	1.4406230499687995
3124	41671	41666	0.0443767100273604
3142	41739	41666	0.3993903902462440
3214	41094	41666	0.1901070417126674
3241	41718	41666	4.1135698171170736
3412	41877	41666	0.0069361109777756
3421	41554	41666	0.3010608169730716
4123	41271	41666	1.1510824173186771
4132	41996	41666	1.9906878510056161
4213	41513	41666	0.0150002400038401
4231	41993	41666	0.2646042336677387
4312	41719	41666	0.0126962031392502
4321	41855	41666	0.0162242595881534
Total			16.480247683962947

$X^2$=16.480247683962947

2. 決定自由度（degrees of freedom）
對於 N 個隨機樣本而言，自由度為 N - 1。我們 shuffle 4 個數字會有二十四種結果，因為加起來機率為 1 ，所以實際上可以自由變換的變數只有二十三個，其中一個結果的機率為 1 減去另外二十三個結果發生的機率，所以自由度為 23。

3. 選擇顯著水準

• 顯著水準（Significance level）α 代表在虛無假說（
  $H_0$）為真下，錯誤地拒絕 （
  $H_0$）的機率，即型一錯誤發生之機率。
  α = P(拒絕
  $H_0$ |
  $H_0$ 為真)
  我們 alpha 設定為常見的 0.05。
• P value
  從卡方分布表找合適的 P value，我們的自由度為 23，
  為 16.480247683962947，因為 14.848 < 16.480247683962947 < 32.007，於是 P value 介於 0.9 和 0.1 之間。
  
  

4. 統計檢定的結果不拒絕虛無假說
對於要拒絕的虛無假說（

$H_0$），觀察到的結果必須具有統計顯著性，即觀察到的 P value 小於預先指定的顯著水準 α。

因為 P value（0.9~0.1）> alpha（0.05），統計檢定的結果不拒絕虛無假說（

$H_0$）也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻。

從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的。

---

研讀論文〈Dude, is my code constant time?〉

解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度

這種方法是通過實際執行程式碼並測量執行時間來評估其時間複雜度，而不是僅僅依靠理論分析或推導。透過模擬實際執行程式碼，可以更貼近真實世界的情況，考慮到各種因素對執行時間的影響。

所謂的「各種因素」，包含哪些？

在 "simulation" 模式中，程式會執行特定的測試案例或操作序列(就像這次 lab 的 qtest)，並記錄每個操作的執行時間。通過執行多次測試並收集大量數據，可以獲得對程式碼執行時間的統計信息，例如平均執行時間、變異性等。這些數據可以用來評估程式碼的時間複雜度，並檢測是否存在不穩定的執行時間模式。

透過實驗驗證時間複雜度的優勢在於可以考慮到實際執行環境中的各種因素，例如硬體特性、軟體環境、系統負載等。這種實驗驗證方法更貼近實際應用場景，能夠提供更具參考價值的結果，幫助評估程式碼的性能和安全性。

解釋 Student's t-distribution 及程式實作的原理

改進你的漢語表達。

Student’s t-distribution：
是統計學中常用的概率分佈，用於估計小樣本數據集的平均值之間的差異是否具有統計學上的意義(估計樣本平均值的不確定性)

在程式分析中，我們可以使用 Student’s t-distribution 來估計實驗數據的變異性，特別是當樣本數較小時。這有助於確定實驗結果的可靠性。
在程式實作中，實現 Student's t-distribution通常涉及計算t統計量（t statistic）以進行假設檢定。t統計量是用於比較兩個平均值之間差異的指標，計算方式涉及樣本平均值、標準誤差和樣本數等。通過計算t統計量並將其與臨界值進行比較，可以判斷兩個平均值之間的差異是否具有統計學上的意義。

根據此論文提出一套量測方法與對應原始碼 dudect，用以量測程式執行時間是否能在常數時間

$O(1)$ 完成，可以完成 qtest 中 Test 17 的測試。
檢查程式執行時間是否能在常數時間

$O(1)$ 完成，根據 dudect 有三步驟:

1. 將 dudect.h 複製到您的包含目錄
2. 從來源檔案中新增#include“dudect.h”。
3. 有關完整包含的範例，請參閱這個最小範例。 您需要編寫以下函數：
   • do_one_computation(),
   • prepare_inputs()
   • call dudect_main() from your main function

directory 的翻譯是「目錄」，而非「檔案夾」(folder)，後者是 Microsoft Windows 的發明，前者是 UNIX 世界通行的術語，歷史悠久。

而在 lab0 中已經有 dudect 的目錄，裡面已經存放需要修改的 fixture.c
我們可以根據 qtest 的標頭檔發現 fixture 定義了函式執行時間是否為常數時間的函式，打開fixture.c 後先去比對 doit 和 dudect.h 的dudect_main差異，發現主要缺少這個函式 prepare_percentiles(ctx)，以及作業要求中提到缺少 percentile 的處理，從dudect.h 複製部分程式修改型態後，執行 qtest 成功得到滿分，在比對程式碼時看到 update_statistics 這個函式 for 迴圈起始值不同，dudect.h update_statistics 這個函式 for 迴圈起始值為 10 而 fixture.c 則為 0，調整為 10 後執行 qtest 也得到滿分。

+static void update_statistics(const int64_t *exec_times, uint8_t *classes)
+{
+    for (size_t i = 10; i < N_MEASURES; i++) {
        int64_t difference = exec_times[i];
        /* CPU cycle counter overflowed or dropped measurement */
        if (difference <= 0)
            continue;

        /* do a t-test on the execution time */
        t_push(t, difference, classes[i]);
    }
}

update_statistics:

改進你的漢語表達。

Dudect 工具中的 update_statistics 函數負責更新用於偵測程式碼中 timing leaks 的統計測量。而起始值為 10 ，是為了丟棄前 10 個初始測量值，這樣做是為了避免初始執行時間的波動影響結果，確保我們可以得到更具代表性的平均執行時間。
prepare_percentiles:
用於計算和儲存給定參數中執行時間的百分位數值。
它先使用 qsort 函式對執行時間 (ctx->exec_times) 進行排序。 測量的數量由ctx->config->number_measurements指定，用於排序的比較函式是 cmp。然後，它計算排序後的執行時間的百分位值。 百分位數由 DUDECT_NUMBER_PERCENTILES 定義。
對於每個百分位數，它使用百分位數函式計算百分位數值。 百分位數排名的計算方式為 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES))，其中 i 是循環中的目前索引。
然後計算出的百分位值儲存在 ctx->percentiles[i] 中。

對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 time 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。另外，對於更一般的描述，function 會指「功能」一類的意涵，應合適挑選譯詞。

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

這個函式準備執行時間的百分位數資料以供進一步分析或使用。百分位數可以深入了解執行時間的分佈，例如中位數（第 50 個百分位數）、四分位數（第 25 個百分位數和第 75 個百分位數）等。

整合網頁伺服器

研讀 select(2)以及相關的 signal(7) 使用方式

---

tic-tac-toe

在 qtest 中新增 ttt 指令，並且實作 do_ttt 函式，其作用是執行與人類對弈的井字遊戲，並使用 Monte Carlo tree search (MCTS) 演算法

切換「人 vs.電腦」或「電腦 vs. 電腦」

在執行 ttt 電腦 vs. 電腦 的過程中，跳出下方的錯誤

Failed to open state value table, train first: No such file or directory

查看 Readme 後發現在使用 reinforcement learning (RL) 演算法 時，需要先執行 train，去生成 state_value.bin
因此在 makefile 中新增 train 的指令

train: $(TRAIN).c ttt/agents/reinforcement_learning.c ttt/game.c
	$(CC) $(CFLAGS) -o $(TRAIN) $^ 
	./ttt/train
	@mv state_value.bin ttt

顯示時間
對弈的過程中，要在螢幕顯示當下的時間 (含秒數)，並持續更新，這邊參考Build Your Own Text Editor 此篇文章來處理終端機畫面，這邊使用 Escape sequences 來指示終端機執行文字格式化的任務。

文章中提到在更新畫面時，執行多次 small write()可能會出現不預期的停頓，導致有閃爍的效果，為了避免此現象發生，將要寫入的字串加到緩衝區中替換所有的 write()，最後在 write()此快緩衝區的內容。因 C 語言沒有動態字串，所以要自己建立一個動態字串的類別，並實作append 和 free 兩個方法。

你該闡述為何需要「動態字串」？解決問題之前，應當闡述其必要性。

append：
確保分配足夠的記憶體去保存新字串
free：
釋放緩衝區使用的動態記憶體

避免參照中文的 Wikipedia，其資訊通常落後於對應的英語條目。

參考此篇來查詢 Escape sequence 代碼所代表的意義

---

〈Teach Yourself Programming in Ten Years〉

短時間內學習程式語言或技能是不切實際的，真正學習程式，就像在學習其他領域一樣，需要多年的專注練習和學習，就如同研究所指出的在任何領域成為專家需要大約十年的時間。

下面的「體悟」在你閱讀〈Teach Yourself Programming in Ten Years〉之前，就已在你腦海中，到底有什麼洞見是閱讀該文後，你才體會到的？

如果你不能清楚闡述「自己的不足」，那麼就算給你更長的時間，你可能還是在原地打轉。

查詞典以理解「內化」的意涵和適用場景。

有效學習程式設計需要時間和刻意練習，類似於掌握其他技能，像是學習樂器…等，短期課程可以學習浮於表面的知識，但不能有深刻的理解或專業技能，程式設計的精通不僅涉及學習語法，還包括理解基本原理和概念。在上老師的課時。因為繳交的作業都是公開的，可以在觀摩別人的作業時發現自己的不足之處，也能找到可以改進的地方。 特別是在 code review 的過程中，可以從同學老師的建議中了解自己的不足，進而改進。 讓我有機會學習到同學好的實務經驗。之前在老師的「資訊科技產業專案設計」課程中，作業模擬面試就是一種刻意練習的方式，透過這種刻意練習，我可以將所學 內化> ??，很認同不管學習哪個領域的專業都需要時間和刻意練習，長期成長和學習的重要性。另外，以前在學習程式時，很常會有"舉燭"的情況，但沒有想過為什麼在這個場景下選擇使用這樣的資料結構或演算法，但這種學習方法在 「Linux 核心設計」中，無法讓我去理解 Linux kernel 中的程式碼，必須要了解實際應用場景，所帶來的效益，才不會陷入程式碼的漩渦，發現實務經驗、參與專案的重要性。

Reference

• 2024 年 Linux 核心設計/實作課程作業 —— lab0
• Linux 核心專題: 改進 lib/list_sort.c
• Dude, is my code constant time?
• dudect
• massif 與 dudect 的作法：vax-r
• Bottom-up Mergesort: A Detailed Analysis
• The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules
• Queue-Mergesort
• listsort 的說明文件
• How to Write a Git Commit Message
• Git 教學和 GitHub 設定指引
• Teach Yourself Programming in Ten Years
• The Linux Programming Interface
• select(2)
• signal(7)