# 2024q1 Homework1 (lab0)
contributed by < [`YaRu056`](https://github.com/YaRu056) >
## 開發環境
```shell
$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` 的函式可以使用
:::spoiler 程式碼
```clike
/* 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` 前一個節點**
```graphviz
digraph "reverse"
{
node[shape=circle ,width=0.5];
head [fontcolor="black"];
A [fontcolor="black"];
B [fontcolor="black"];
C [fontcolor="black"];
node[shape=plaintext];
cur [fontcolor="red"];
tmp[fontcolor="blue"];
{
rankdir = "LR";
rank="same";
C:se->head:sw;
head:nw->C:ne
head->A->B->C;
C->B->A->head;
}
cur->head;
tmp->C;
}
```
**2. 先把 `cur->prev`做更新， `cur->prev=cur->next`**
```graphviz
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;
}
```
**3. 再更新 `cur->next=tmp`**
```graphviz
digraph "reverse2"
{
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;
head:se->C:s [color="red"];
A->B->C;
C->B->A->head;
head->A;
C:se->head:sw;
}
cur->head;
tmp->C;
}
```
**4. 再更新 `cur` 和 `tmp` 重複上面步驟，直到<s>遍歷</s> ??? 完所有的節點**
```graphviz
digraph "reverse3"
{
node[shape=circle ,width=0.5];
head [fontcolor="black"];
A [fontcolor="black"];
B [fontcolor="black"];
C [fontcolor="black"];
node[shape=plaintext];
tmp[fontcolor="blue"];
cur [fontcolor="red"];
{
rankdir = "LR";
rank="same";
head:nw->A:ne;
head:se->C:s ;
A->B->C;
C->B->A->head;
C:se->head:sw;
}
tmp->head;
cur->A;
}
```
:::danger
注意用語。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
最後<s>遍歷</s> 完所有節點
```graphviz
digraph "reverse4"
{
node[shape=circle ,width=0.5];
head[fontcolor="black"];
C [fontcolor="black"];
B [fontcolor="black"];
A [fontcolor="black"];
node[shape=plaintext];
cur [fontcolor="red"];
tmp [fontcolor="blue"];
{
rankdir = "LR";
rank="same";
head:nw->A:ne;
A:se->head:sw;
head->C->B->A;
A->B->C->head;
}
tmp->B;
cur->C;
}
```
:::danger
使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記。
:::
#### `q_reverseK`
先建立一個新的佇列，以 size=k 個大小切成一段，反轉後，加在新的佇列的結尾，重複執行 `q_size(head)/k` 次後結束，最後將新的佇列移到 head 前面
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
#### `q_sort`
:::danger
本例中，應指「測試項目」(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]
```
因為用既定的印象去寫排序，除錯了好一陣子，查看規格和測試內容真的很重要，可以少走一些錯路！
原先使用泡沫排序法，但因測試中會要求排序的時間複雜度，因此改為合併排序法。
:::warning
不要裝可愛。
:::
#### `q_merge`
:::danger
誠實面對自己。
不要說「時間快不夠了，先寫了一個粗糙的版本」，要是 Apple 工程師用這種態度開發軟體，你敢把 iPhone 放在你的口袋嗎？本課程重視工程的嚴謹，你的起步高低是一回事，但持續投入並謹慎面對各式工程議題，是「工程」不該少的態度。
:::
:::danger
避免贅詞。
:::
#### `queue`
**q_new()**
```graphviz
digraph "queue_context_t"
{
rankdir="LR";
node[shape=plaintext];
chain_head[fontcolor="red"];
node[shape=record];
head [label = "<m>list_head | {<p> prev |<n> next}", group = list];
rankdir = "LR"
subgraph "cluster queue"
{
id [shape = box];
size [shape = box];
node[shape = record];
q [label = "<m>q | {<p> prev |<n> next}", group = list];
chain [label = "<m>chain | {<p> prev |<n> next}", group = list];
}
{
q : n : e ->head : m ;
head : p :w ->head : w;
head : n :e-> head : e;
chain_head-> chain : m
}
}
```
**q_insert_head()**
```graphviz
digraph "queue_context_t"
{
rankdir="LR";
node[shape=plaintext];
chain_head[fontcolor="red"];
node[shape=record];
head [label = "<m>list_head | {<p> prev |<n> next}", group = list];
ele1 [label = "<m>element_t| value | {<p> prev |<n> next}", group = list];
rankdir = "LR"
subgraph "cluster queue"
{
id [shape = box];
size [shape = box];
node[shape = record];
q [label = "<m>q | {<p> prev |<n> next}", group = list];
chain [label = "<m>chain | {<p> prev |<n> next}", group = list];
}
{
q : n : e ->head : m ;
head : n -> ele1 : p;
ele1 : p ->head : n ;
ele1 : n: s -> head : p : w;
head : p : s -> ele1 : n : e ;
chain_head-> chain : m
}
}
```
:::danger
使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記中。
:::
**測試結果：**
最後測試17 `trace-17-complexity` 始終無法通過
```text
+++ 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
```
:::warning
研讀指定的論文。
:::
## 分析 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](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 中提及的 論文 [Queue-Mergesort](https://doi.org/10.1016/0020-0190(93)90088-q) 方法不同，前者則是出現兩個 $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
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
Null [fontcolor="black"];
head[fontcolor="red"];
list[fontcolor="red"];
pending[fontcolor="red"];
tail [fontcolor="red"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir ="LR" ;
head,5,3,1,2,8,6,7,9,0;
start [style=invis];
start->head->5->3 [style=invis];
head :se -> 5:sw;
5->3->1->2->8->6->7->9->0;
0->9->7->6->8->2->1->3->5;
head :ne->5 :nw [dir=back];
}
{
rank=same;
list->5;
tail->pending->Null;
}
}
```
此時`count`= 1 = $1_2$
--> `count + 1` = $2^0$+$2^0$ (不做合併)
因為 `bits` 為 1，`tail` = `&(*tail)->prev`;
此時 `tail` 指向 `5->prev`
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
head[fontcolor="red"];
pending[fontcolor="red"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start [style=invis];
start->head[style=invis];
5->3 [dir=back];
}
{
rankdir ="LR" ;
head,5,3,1,2,8,6,7,9,0;
3->1->2->8->6->7->9->0;
0->9->7->6->8->2->1->3;
head->5
}
{
rank=same;
pending->5;
}
{
rank=same;
list->3;
}
}
```
此時`count` = 2 = $10_2$
--> `count + 1` = $2^1$+$2^0$ (做指定串列合併)
此時合併的串列大小是 1+1
`*a` = `*tail`, `*b` = `a->prev`;
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
tail [fontcolor="red"];
head[fontcolor="red"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start [style=invis];
start->head->5->3[style=invis];
head:e->5;
}
{
rankdir ="LR" ;
5,3,1,2,8,6,7,9,0;
5:e->3[dir=back];
3:e->1[dir=back];
1->2->8->6->7->9->0;
0->9->7->6->8->2->1;
}
{
rank=same;
tail->pending->3;
}
{
rank=same;
list->1;
}
}
```
```graphviz
digraph "mergesort2"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
tail [fontcolor="red"];
head[fontcolor="red"];
a [fontcolor="red"];
b [fontcolor="blue"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5->3[style=invis];
head:e->5;
start2->b->a[style=invis];
a->3;
b->5;
}
{
rankdir ="LR" ;
5,3,1,2,8,6,7,9,0;
5:e->3[dir=back];
3:e->1[dir=back];
1->2->8->6->7->9->0;
0->9->7->6->8->2->1;
}
{
rank=same;
tail->pending->3;
}
{
rank=same;
list->1;
}
}
```
**Merge**
`a` = `merge(priv, cmp, b, a)`
```graphviz
digraph "merge"
{
rankdir="LR";
node[shape=plaintext];
head[fontcolor="red"];
tail [fontcolor="red"];
a [fontcolor="red"];
b [fontcolor="blue"];
null1 [fontcolor="black",label="Null"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
{
rank=same;
a->5;
}
{
rank=same;
b->3;
}
{
rank=same;
tail->head->null1;
}
{
rankdir="LR";
start [style=invis];
start->tail->a->b[style=invis];
}
}
```
**a>b**
```graphviz
digraph "merge"
{
rankdir="LR";
node[shape=plaintext];
head[fontcolor="red"];
tail [fontcolor="red"];
a [fontcolor="red"];
b [fontcolor="blue"];
null1 [fontcolor="black",label="Null"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
{
rank=same;
tail->a->5;
}
{
rank=same;
head->3;
}
{
rank=same;
b->null1;
}
{
rankdir="LR";
start [style=invis];
start->head->a->b[style=invis];
3->5;
}
}
```
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$ (不做合併)
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
tail [fontcolor="red"];
head[fontcolor="red"];
a [fontcolor="red"];
b [fontcolor="blue"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start [style=invis];
start->head->5[style=invis];
head:e->5:w;
3:e->1 ->2[dir=back];
b->5;
}
{
rankdir ="LR" ;
1,2,8,6,7,9,0;
2->8->6->7->9->0;
0->9->7->6->8->2;
}
{
rank=same;
3:s->5:n;
}
{
rank=same;
pending->1;
}
{
rank=same;
tail->a->3;
}
{
rank=same;
list->2;
}
}
```
`bits` = 3 時，`tail` 指向 `3->prev`，`bits` = 1 時，`tail` 指向 `5->prev`
此時`count`= 4 = $100_2$
--> `count + 1` = $2^1$+$2^1$+$2^0$ (做指定串列合併)
此時合併的串列大小是 1+1
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
a [fontcolor="red"];
b [fontcolor="blue"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->3->1->2[style=invis];
3:e->1->2:w [dir=back];
}
{
rankdir ="LR" ;
1,2,8,6,7,9,0;
8->6->7->9->0;
0->9->7->6->8;
2->8[dir=back];
}
{
rank=same;
3:s->5:n;
}
{
rank=same;
pending->2;
}
{
rank=same;
list->8;
}
a->2b->1
}
```
合併後的結果
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
a [fontcolor="red"];
tail [fontcolor="red"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start [style=invis];
start->head->5[style=invis];
head:e->5:w;
3:e->1 [dir=back];
}
{
rankdir ="LR" ;
1,2,8,6,7,9,0;
6->7->9->0;
0->9->7->6;
1->8->6[dir=back];
}
{
rank=same;
3:s->5:n;
}
{
rank=same;
tail->a->1->2;
}
{
rank=same;
pending->8;
}
{
rank=same;
list->6;
}
}
```
此時`count`=5 = $101_2$
--> `count + 1` = $2^2$+$2^0$+$2^0$ (做指定串列合併)
此時合併的串列大小是 2+2
`tail` = `&(*tail)->prev`;
此時 `*tail` 指向 `1`
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
tail [fontcolor="red",label="*tail"];
a [fontcolor="red"];
b [fontcolor="blue"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start,start2 [style=invis];
start->head->5[style=invis];
start2->3->1 [style=invis];
head:e->5:w;
3:e->1 [dir=back];
a->1;
b->3;
}
{
rankdir ="LR" ;
1,2,8,6,7,9,0;
6->7->9->0;
0->9->7->6;
1->8->6[dir=back];
}
{
rank=same;
3:s->5:n;
}
{
rank=same;
tail->1->2;
}
{
rank=same;
pending->8;
}
{
rank=same;
list->6;
}
}
```
合併後的結果
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
a[fontcolor="red"];
tail [fontcolor="red",label="tail"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->1[style=invis];
}
{
rankdir ="LR" ;
1,8,6,7,9,0;
7->9->0;
0->9->7;
1->8->6->7[dir=back];
}
{
rank=same;
tail->a->1->2->3->5;
}
{
rank=same;
pending->6;
}
{
rank=same;
list->7;
}
}
```
此時`count`=6 = $110_2$
--> `count + 1` = $2^2$+$2^1$+$2^0$ (做指定串列合併)
此時合併的串列大小是 1+1
`tail` = `&(*tail)->prev`;
此時 `*tail` 指向 `1`
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
a[fontcolor="red"];
b[fontcolor="blue"];
tail [fontcolor="red",label="tail"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->b->a->pending->list[style=invis];
a->6;
b->8;
}
{
rankdir ="LR" ;
1,8,6,7,9,0;
7->9->0;
0->9->7;
1->8->6->7[dir=back];
}
{
rank=same;
1->2->3->5;
}
{
rank=same;
tail->pending->6;
}
{
rank=same;
list->7;
}
}
```
合併後
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
a[fontcolor="red"];
tail [fontcolor="red",label="tail"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->a->pending->list[style=invis];
}
{
rank=same;
1->2->3->5;
}
{
rankdir ="LR" ;
1,6,7,9,0;
9->0;
0->9;
1->6->7->9[dir=back];
}
{
rank=same;
tail->a->6->8;
}
{
rank=same;
pending->7;
}
{
rank=same;
list->9;
}
}
```
此時`count`= 7 = $111_2$
--> `count + 1` = $2^2$+$2^1$+$2^0$+$2^0$ (不合併)
`tail` = `&(*tail)->prev`;
此時 `tail` 會指向 `1->prev`
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->pending->list[style=invis];
}
{
rank=same;
1->2->3->5;
}
{
rankdir ="LR" ;
1,6,7,9,0;
1->6->7->9->0[dir=back];
}
{
rank=same;
6->8;
}
{
rank=same;
pending->9;
}
{
rank=same;
list->0;
}
}
```
此時`count`= 8 = $1000_2$
--> `count + 1` = $2^2$+$2^1$+$2^0$+$2^0$ (做指定串列合併)
此時合併的串列大小是 1+1
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
a[fontcolor="red"];
b[fontcolor="blue"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->b->a->pending->list[style=invis];
a->9;
b->7
}
{
rank=same;
1->2->3->5;
}
{
rankdir ="LR" ;
1,6,7,9,0;
1->6->7->9->0[dir=back];
}
{
rank=same;
6->8;
}
{
rank=same;
pending->9;
}
{
rank=same;
list->0;
}
}
```
合併後
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
tail [fontcolor="red"];
a[fontcolor="red"];
Null[fontcolor="black"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->a->pending->list[style=invis];
}
{
rank=same;
1->2->3->5;
}
{
rankdir ="LR" ;
1,6,7,9,0;
1->6->7->0[dir=back];
}
{
rank=same;
6->8;
}
{
rank=same;
tail->a->7->9;
}
{
rank=same;
pending->0;
}
{
rank=same;
list->Null;
}
}
```
當走遍 list 後，將所有 `pending list` 合併在一起
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
next [fontcolor="red"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->next->pending->list[style=invis];
}
{
rank=same;
1->2->3->5;
}
{
rankdir ="LR" ;
1,6,7,9,0;
1->6->7->0[dir=back];
}
{
rank=same;
6->8;
}
{
rank=same;
7->9;
}
{
rank=same;
pending->7;
}
{
rank=same;
list->0;
}
{
rank=same;
next->6;
}
}
```
合併
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
next [fontcolor="red"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->next->pending->list[style=invis];
}
{
rank=same;
1->2->3->5;
}
{
rankdir ="LR" ;
1,6,7,9,0;
1->6->0[dir=back];
}
{
rank=same;
6->8;
}
{
rank=same;
0->7->9;
}
{
rank=same;
pending->6;
}
{
rank=same;
list->0;
}
{
rank=same;
next->1;
}
}
```
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
list[fontcolor="red"];
pending[fontcolor="red"];
head[fontcolor="red"];
next [fontcolor="red"];
Null [fontcolor="black"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start ,start2[style=invis];
start->head->5[style=invis];
head:e->5:w;
start2->next->pending->list[style=invis];
}
{
rank=same;
1->2->3->5;
}
{
rankdir ="LR" ;
1,6,7,9,0;
1->0[dir=back];
}
{
rank=same;
0->6->7->8->9;
}
{
rank=same;
pending->1;
}
{
rank=same;
list->0;
}
{
rank=same;
next->Null;
}
}
```
當`next` 指向 Null 時，做最終合併，並且恢復成`circular`
```graphviz
digraph "mergesort"
{
rankdir="LR";
node[shape=plaintext];
head[fontcolor="red"];
node[shape=circle ,width=0.5];
5 [fontcolor="black"];
3 [fontcolor="black"];
1 [fontcolor="black"];
2 [fontcolor="black"];
8 [fontcolor="black"];
6 [fontcolor="black"];
7 [fontcolor="black"];
9 [fontcolor="black"];
0 [fontcolor="black"];
{
rankdir="LR";
start[style=invis];
start->head->0->1->2->3->5->6->7->8->9[style=invis];
}
{
rankdir ="LR" ;
head->0->1->2->3->5->6->7->8->9->head;
head->0->1->2->3->5->6->7->8->9->head[dir=back];
}
}
```
相比之下，`Linux/lib/list_sort.c` 使用的是 in-place 演算法，且透過維持每次最終合併大小在最差情況下都是 2:1 去降低比較次數，同時避免 cache thrashing 的發生。
針對 比較次數 和 cache miss rate 來分析，這邊參考[此篇分析方法](https://hackmd.io/@sysprog/linux2022-sample-lab0#%E7%A0%94%E8%AE%80-liblist_sortc)，我先用 ADD_COMMAND 加入了 <s>ㄔㄛlistSort</s> ?? 這到命令，執行時會呼叫引入 qtest.c 的 list_sort 。選擇 260000 以及 270000 這兩個排序數量，一個在
$2^{18}$(262144) 前，一個在 $2^{18}$ 後，可以看出佇列的長度對於比較次數的影響，用以下命令測量執行時間。
```shell
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 倍。
#### 比較次數
對於比較次數的探討，我們可寫成以下形式：
$nlog_2n-K_n+O(1)$
其中，以下 merge sort 的變形 (variants)，領導係數 (leading coefficient) 皆為 $log_2{n!}$，探討的著重點在於一次項係數 K。
## 針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式
## 透過 perf 分析程式效能
:::danger
command 是「命令」，而非「指令」(instruction)
:::
用 `lscpu` <s>指令</s> 來查看快取大小
```shell
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.
可搭配視覺化工具展現給定程式在執行時期的記憶體行為
:::danger
command 的翻譯是「命令」，而非「指令」
:::
命令如下
```shell
$ valgrind --tool=massif ./qtest -f traces/trace-massif.cmd
```
其中 `traces/trace-massif.cmd` 的內容只要複製 traces/trace-17-complexity.cmd 並稍做修改即可，例如測試 `q_insert_tail`
利用 `ms_print` 可以輸出此檔案內容
```shell
$ 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 工具，產生記憶體使用情形的時間分佈圖：
```shell
massif-visualizer massif.out.<pid>
```
:::warning
附上你的解讀
:::
## 實作 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` 就結束。
```text
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](https://hackmd.io/@sysprog/linux2024-lab0-d) 提供之測試程式進行實驗，結果如下
**1. 先計算 chi-squared test statistic $X^2$**
$$
\begin{split}X^2&=\displaystyle\sum_{i=1}^{n}\dfrac{(O_i-E_i)^2}{E_i}\end{split}
$$
$X^2$ : Pearson's cumulative test statistic
$O_i$: the number of observations of type i
$E_i$: the expected count of type i
```text
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 次後，二十四種結果各自的頻率如下表：
| | 觀察到的頻率 | 期待的頻率 | $\dfrac{（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
從[卡方分布表](http://www.obhrm.net/index.php/%E5%8D%A1%E6%96%B9%E5%88%86%E5%B8%83%E8%A1%A8_Chi-Square_Probabilities)找合適的 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" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度
這種方法是通過**實際執行程式碼**並測量執行時間來評估其時間複雜度，而不是僅僅依靠理論分析或推導。透過模擬實際執行程式碼，可以更貼近真實世界的情況，考慮到各種因素對執行時間的影響。
:::warning
所謂的「各種因素」，包含哪些？
:::
在 "simulation" 模式中，程式會執行特定的測試案例或操作序列(就像這次 lab 的 qtest)，並記錄每個操作的執行時間。通過執行多次測試並收集大量數據，可以獲得對程式碼執行時間的統計信息，例如平均執行時間、變異性等。這些數據可以用來評估程式碼的時間複雜度，並檢測是否存在不穩定的執行時間模式。
透過實驗驗證時間複雜度的優勢在於可以考慮到實際執行環境中的各種因素，例如硬體特性、軟體環境、系統負載等。這種實驗驗證方法更貼近實際應用場景，能夠提供更具參考價值的結果，幫助評估程式碼的性能和安全性。
**解釋 Student's t-distribution 及程式實作的原理**
:::danger
改進你的漢語表達。
:::
**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](https://github.com/oreparaz/dudect) 有三步驟:
1. 將 dudect.h 複製到您的包含目錄
2. 從來源檔案中新增#include“dudect.h”。
3. 有關完整包含的範例，請參閱這個最小範例。 您需要編寫以下函數：
* do_one_computation(),
* prepare_inputs()
* call dudect_main() from your main function
:::danger
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 也得到滿分。
```diff
+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:**
:::danger
改進你的漢語表達。
:::
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]` 中。
:::danger
對應到數學公式，function 應翻譯為「函數」，後者就像是台「機器」，它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中，function 未必具備數學函數的意涵，也就是缺乏「唯一對應」的特性，例如對於 [time](https://man7.org/linux/man-pages/man2/time.2.html) 來說，給定同樣的輸入，卻會在不同時間點得到不同的結果，在 C 語言一類的通用程式語言中，甚至可省略傳回值，後者就不符合「函數」的行為。因此，當在通用的程式設計中，function 應翻譯為「函式」，表示「衍生自數學函數的常式 (routine)」。另外，對於更一般的描述，function 會指「功能」一類的意涵，應合適挑選譯詞。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
這個函式準備執行時間的百分位數資料以供進一步分析或使用。百分位數可以深入了解執行時間的分佈，例如中位數（第 50 個百分位數）、四分位數（第 25 個百分位數和第 75 個百分位數）等。
## 整合網頁伺服器
### 研讀 select(2)以及相關的 signal(7) 使用方式
---
## tic-tac-toe
在 qtest 中新增 `ttt` 指令，並且實作 `do_ttt` 函式，其作用是執行與人類對弈的井字遊戲，並使用 Monte Carlo tree search (MCTS) 演算法
**切換「人 vs.電腦」或「電腦 vs. 電腦」**
在執行 `ttt` 電腦 vs. 電腦 的過程中，跳出下方的錯誤
```shell
Failed to open state value table, train first: No such file or directory
```
查看 `Readme` 後發現在使用 reinforcement learning (RL) 演算法 時，需要先執行 `train`，去生成 state_value.bin
因此在 makefile 中新增 train 的指令
```makefile
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](https://viewsourcecode.org/snaptoken/kilo/) 此篇文章來處理終端機畫面，這邊使用 `Escape sequences` 來指示終端機執行文字格式化的任務。
文章中提到在更新畫面時，執行多次 `small write()`可能會出現不預期的停頓，導致有閃爍的效果，為了避免此現象發生，將要寫入的字串加到緩衝區中替換所有的 `write()`，最後在 `write()`此快緩衝區的內容。因 C 語言沒有動態字串，所以要自己建立一個動態字串的類別，並實作`append` 和 `free` 兩個方法。
:::danger
你該闡述為何需要「動態字串」？解決問題之前，應當闡述其必要性。
:::
`append`：
確保分配足夠的記憶體去保存新字串
`free`：
釋放緩衝區使用的動態記憶體
:::danger
避免參照中文的 Wikipedia，其資訊通常落後於對應的英語條目。
:::
參考[此篇](https://zh.wikipedia.org/wiki/ANSI%E8%BD%AC%E4%B9%89%E5%BA%8F%E5%88%97)來查詢 `Escape sequence` 代碼所代表的意義
---
## 〈[Teach Yourself Programming in Ten Years](https://norvig.com/21-days.html)〉
短時間內學習程式語言或技能是不切實際的，真正學習程式，就像在學習其他領域一樣，需要多年的專注練習和學習，就如同研究所指出的在任何領域成為專家需要大約十年的時間。
:::danger
下面的「體悟」在你閱讀〈[Teach Yourself Programming in Ten Years](https://norvig.com/21-days.html)〉之前，就已在你腦海中，到底有什麼洞見是閱讀該文後，你才體會到的？
如果你不能清楚闡述「自己的不足」，那麼就算給你更長的時間，你可能還是在原地打轉。
查詞典以理解「內化」的意涵和適用場景。
:::
有效學習程式設計需要時間和刻意練習，類似於掌握其他技能，像是學習樂器......等，短期課程可以學習浮於表面的知識，但不能有深刻的理解或專業技能，程式設計的精通不僅涉及學習語法，還包括理解基本原理和概念。在上老師的課時。因為繳交的作業都是公開的，可以在觀摩別人的作業時發現自己的不足之處，也能找到可以改進的地方。 特別是在 code review 的過程中，可以從同學老師的建議中了解自己的不足，進而改進。 讓我有機會學習到同學好的實務經驗。之前在老師的「資訊科技產業專案設計」課程中，作業模擬面試就是一種刻意練習的方式，透過這種刻意練習，我可以將所學 <s>內化></s> ??，很認同不管學習哪個領域的專業都需要時間和刻意練習，長期成長和學習的重要性。另外，以前在學習程式時，很常會有"舉燭"的情況，但沒有想過為什麼在這個場景下選擇使用這樣的資料結構或演算法，但這種學習方法在 「Linux 核心設計」中，無法讓我去理解 Linux kernel 中的程式碼，必須要了解實際應用場景，所帶來的效益，才不會陷入程式碼的漩渦，發現實務經驗、參與專案的重要性。
## Reference
* [2024 年 Linux 核心設計/實作課程作業 —— lab0](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a)
* [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh)
* [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
* [dudect](https://github.com/oreparaz/dudect)
* massif 與 dudect 的作法：[vax-r](https://hackmd.io/@vax-r/linux2024-homework1)
* [Bottom-up Mergesort: A Detailed Analysis]( https://doi.org/10.1007/BF01294131)
* [The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules](https://doi.org/10.1006/jagm.1998.0986)
* [Queue-Mergesort](https://doi.org/10.1016/0020-0190(93)90088-q)
* [listsort 的說明文件](https://github.com/python/cpython/blob/main/Objects/listsort.txt)
* [How to Write a Git Commit Message](https://cbea.ms/git-commit/)
* [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github)
* [Teach Yourself Programming in Ten Years](https://norvig.com/21-days.html)
* [The Linux Programming Interface](https://man7.org/tlpi/)
* [select(2)](https://man7.org/linux/man-pages/man2/select.2.html)
* [signal(7)](https://man7.org/linux/man-pages/man7/signal.7.html)
Sign in with Wallet
Connect another wallet