# 2020q3 Homework1 (lab0)
contributed by < `KairC` >
[Github](https://github.com/KairC/lab0-c)
## 開發環境
### CPU
```
$sudo lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 36 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 42
Model name: Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
Stepping: 7
CPU MHz: 1292.842
CPU max MHz: 3100.0000
CPU min MHz: 800.0000
BogoMIPS: 4988.67
Virtualization: VT-x
L1d cache: 64 KiB
L1i cache: 64 KiB
L2 cache: 512 KiB
L3 cache: 3 MiB
NUMA node0 CPU(s): 0-3
Vulnerability Itlb multihit: KVM: Mitigation: VMX disabled
Vulnerability L1tf: Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable
Vulnerability Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Vulnerability Meltdown: Mitigation; PTI
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2: Mitigation; Full generic retpoline, IBPB conditional, IBRS_FW, STIBP conditional, RSB filling
Vulnerability Srbds: Not affected
Vulnerability Tsx async abort: Not affected
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx lahf_lm epb pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid xsaveopt dtherm ida arat pln pts md_clear flush_l1d
```
### Memory
```
$sudo lsmem
RANGE SIZE STATE REMOVABLE BLOCK
0x0000000000000000-0x00000000afffffff 2.8G online yes 0-21
0x0000000100000000-0x000000024fffffff 5.3G online yes 32-73
Memory block size: 128M
Total online memory: 8G
Total offline memory: 0B
```
### 作業系統
```
$uname -a
Linux kai-K53SV 5.8.0-43-generic #49~20.04.1-Ubuntu SMP Fri Feb 5 09:57:56 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
```
### 編譯器
```
$gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 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.
```
## 開發工具
### Makefile
[Makefile 語法和示範](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FSySTMXPvl)
* 專案中有一堆檔案要編譯、連結，就需要用make+Makefile，不然會累死人
```
$sudo apt-get install make
$vim Makefile
$make
```
* 需要建立一個檔案叫做`Makefile`，裡面寫一些需要用到的指令，以下為example
* 假設情境：以C寫成的三份原始碼`q1.c`, `q2.c`, `q3.c`要連結成一個可執行的檔案`myprog`，則需要先產生這三個檔案的 object file，再連結成`myprog`。 好處是當只有`q3.c`要修改時，就不用再去重新編譯未修改的`q1.c`, `q2.c`。
```
myprog: q1.o q2.o q3.o
gcc -o myprog q1.o q2.o q3.o
q1.o: q1.c
gcc -c q1.c
q2.o: q2.c
gcc -c q2.c
q3.o: q3.c
gcc -c q3.c
```
### Cppcheck
* 靜態程式碼分析工具
* [Cppcheck](http://cppcheck.sourceforge.net/)
```
$sudo apt-get install cppcheck
$cppcheck file.c
```
### Valgrind
* 動態程式分析工具，包含一堆工具
* [Valgrind](https://valgrind.org/)
```
$sudo apt-get install valgrind
```
### Massif-Visualizer
* 對 Valgrind 裡頭的 Massif 工具所產生的分析結果做視覺化
* [Massif-Visualizer](https://apps.kde.org/en/massif-visualizer)
### Clang-Format
* [Clang-Format](https://clang.llvm.org/docs/ClangFormat.html)
* `$sudo apt-get install clang-format`
* `$cd ~/sbin` :任意選一個要存放的資料夾, 這裡用sbin做例子
* `$wget https://raw.githubusercontent.com/llvm/llvm-project/master/clang/tools/clang-format/clang-format.py`:下載clang-format.py
* 將以下function加入.vimrc，因為ubuntu是用Python3編譯vim，所以要用py3f而不是官方網站寫的pyf
```
function! Formatonsave()
let l:formatdiff = 1
py3f <path to your clang-format.py>/clang-format.py
endfunction
autocmd BufWritePre *.h,*.hpp,*.c,*.cc,*.cpp call Formatonsave()
```
## 實作細節
:::danger
:cry: 文字訊息不要用圖片，下次改進
:::
### q_new
如果`malloc`回傳 NULL，代表沒辦法allocate space，判斷 q 為 NULL後 return NULL。
```clike=
...
if(!q)
return NULL;
...
```
### q_free
利用 while loop 不斷釋放 linked list 上的節點，直到 q 為empty。
```clike=
...
while(q && q->head){
list_ele_t *tmp;
tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
...
```
### q_insert_head
在為 Linked list 建立新節點時，需要為節點配置記憶體，而節點內儲存字串的`char *value`也要配置記憶體，如果在連續配置記憶體時失敗，需要將先前配置成功的記憶體釋放掉。
```cpp=
...
/* TODO: What should you do if the q is NULL? */
if (!q || !s)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
char *tmp = malloc(sizeof(char) * (strlen(s) + 1));
if (!tmp) {
free(newh);
return false;
}
newh->value = tmp;
strlcpy((newh->value), s, strlen(s) + 1);
newh->next = q->head;
(q->size)++;
q->head = (q->size == 1 ? (q->tail = newh) : newh);
return true;
...
```
:::info
* [Common vulnerabilities guide for C programmers : strlcpy](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)
:::
:::danger
:bell:在為`newh->value`配置記憶體空間時，不能夠寫成
```cpp=
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
```
否則在`$git commit`時會出現 memory leak 的錯誤訊息
同樣問題出現在下面`q_insert_tail`
看過別人的共筆，一樣的寫法似乎不會出錯
不知道為何?
:::
### q_insert_tail
為了達成時間複雜度 $O(1)$ ，在`struct queue_t`中新增`list_ele_t *tail`，用來指向串列尾端，可以省下從頭走訪到尾端的時間。
然而在進行第17筆測試時會有偶爾無法通過的問題。(待解決)
```cpp=
...
/* TODO: You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
/* TODO: Remove the above comment when you are about to implement. */
if (!q || !s)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
char *tmp = malloc(sizeof(char) * (strlen(s) + 1));
if (!tmp) {
free(newh);
return false;
}
newh->value = tmp;
strlcpy(newh->value, s, strlen(s) + 1);
newh->next = NULL;
(q->size)++;
q->tail = (q->size == 1 ? (q->head = newh) : (q->tail->next = newh));
return true;
...
```
### q_remove_head
移除 head 節點須要將字串複製到`char *sp`這個 parameter 中，雖然寫了一行程式碼，作用是在`sp`的最後寫入`\0`，但是在查看`qtest.c`後發現`sp`在傳入`q_remove_head`前，會在頭尾各寫入一個`\0`，因此第7行程式碼可以刪除，經測試後也確定不影響執行結果。
```cpp=
...
/* TODO: You need to fix up this code. */
/* TODO: Remove the above comment when you are about to implement. */
if (!q || !(q->head) || !sp)
return false;
strlcpy(sp, q->head->value, bufsize);
*(sp + bufsize - 1) = '\0';
list_ele_t *tmp;
tmp = q->head;
q->head = (q->size == 1 ? (q->tail = q->tail->next) : (q->head->next));
free(tmp->value);
free(tmp);
(q->size)--;
return true;
...
```
### q_size
為了達成時間複雜度 $O(1)$ ，在`struct queue_t`中新增`int size`，在新增、刪除節點時對`size`做增減，因此直接 return `q->size`即可得到 Linked list 的大小。
```cpp=
...
/* TODO: You need to write the code for this function */
/* Remember: It should operate in O(1) time */
/* TODO: Remove the above comment when you are about to implement. */
if (!q || !(q->head))
return 0;
return q->size;
...
```
### q_reverse
常見的反轉方法，在要反轉的節點前後各用一個 pointer 指著。
```cpp=
...
if (!q || !(q->head))
return;
if (q->size == 1) {
return;
} else {
list_ele_t *lhead;
list_ele_t *rhead;
lhead = NULL;
rhead = q->head->next;
q->tail = q->head;
while (rhead != NULL) {
q->head->next = lhead;
lhead = q->head;
q->head = rhead;
rhead = rhead->next;
}
q->head->next = lhead;
}
...
```
### q_sort
原先利用 [linked list 和非連續記憶體操作：2020q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz1) 中的方法寫的
Merge sort，執行
`$make SANITIZER=1`
`$make test`
在第15, 16 ,17筆測資皆出錯，而前兩者都是跟 sort 有關的測試，先嘗試從第15筆開始解決，執行`$./qtest -v 3 -f traces/trace-15-perf.cmd`後可以得知是在執行`q_sort`的過程中產生錯誤。
錯誤訊息：
進一步以`$make valgrind`檢測
可以知道首要問題是 **Stack overflow**，開始著手修改Merge sort。
**修正 q_sort**：
參考自：
* [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
* [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list?type=view)
```cpp=
void q_sort(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* TODO: Remove the above comment when you are about to implement. */
if (!q || !(q->head) || q->size == 1)
return;
q->head = split_list(q->head);
q->tail = q->head;
while (q->tail->next) {
q->tail = q->tail->next;
}
}
list_ele_t *split_list(list_ele_t *head)
{
if (!(head->next))
return head;
list_ele_t *right = head->next;
list_ele_t *left = head;
// split list
while (right && right->next) {
left = left->next;
right = right->next->next;
}
right = left->next;
left->next = NULL;
// sort each list
list_ele_t *l1 = split_list(head);
list_ele_t *l2 = split_list(right);
// merge sorted l1 and sorted l2
return merge_sort(l1, l2);
}
list_ele_t *merge_sort(list_ele_t *l1, list_ele_t *l2)
{
//"merge" actually is changing the address in 'next' field.
//'head' is no different with the 'next' field in list_ele_t.
list_ele_t *head = NULL;
list_ele_t **tmp = &head;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
(*tmp) = l1;
l1 = l1->next;
} else {
(*tmp) = l2;
l2 = l2->next;
}
tmp = &((*tmp)->next);
}
if (l1) {
(*tmp) = l1;
} else {
(*tmp) = l2;
}
return head;
}
```
執行結果:
重作`q_sort`後，第15、16筆測資已通過
## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
* 第 01~16 筆測資都會有類似下面的訊息
```
==719793== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==719793== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==719793== by 0x4A4E54E: strdup (strdup.c:43)
==719793== by 0x110118: linenoiseHistoryAdd (linenoise.c:1237)
==719793== by 0x110CE7: linenoiseHistoryLoad (linenoise.c:1326)
==719793== by 0x10C22C: main (qtest.c:769)
==719793==
==719793== 135 bytes in 18 blocks are still reachable in loss record 2 of 3
==719793== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==719793== by 0x4A4E54E: strdup (strdup.c:43)
==719793== by 0x110074: linenoiseHistoryAdd (linenoise.c:1237)
==719793== by 0x110CE7: linenoiseHistoryLoad (linenoise.c:1326)
==719793== by 0x10C22C: main (qtest.c:769)
==719793==
==719793== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==719793== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==719793== by 0x1100C0: linenoiseHistoryAdd (linenoise.c:1225)
==719793== by 0x110CE7: linenoiseHistoryLoad (linenoise.c:1326)
==719793== by 0x10C22C: main (qtest.c:769)
==719793==
```
可以在`linenoise.c`裡找到`static char **history`與`char *linecopy`，錯誤訊息都是因為這兩個變數直接或間接的執行了`malloc()`，卻沒有對應的`free()`而出現錯誤。
==解決== :
改寫原有的`freeHistory (linenoise.c:1190)`，將`static`去掉才能讓別的 .c 檔案呼叫，並將該 function 加入`linenoise.h`。
再加入額外變數`static bool history_isFree`來確認是否有跑過`freeHistory()`，否則在執行`$./scripts/debug.py -d`後的 debug 模式中會有 double free 的問題。
最後在 qtest.c 的程式碼結束前呼叫該函式。
### 利用 massif-visualizer 對 Massif 的結果做視覺化
#### 實驗
```
$valgrind --tool=massif --max-snapshots=1000 ./qtest -v 3 -f ./traces/trace-01-ops.cmd
$massif-visualizer massif.out.*
```
* 如果沒有把 malloc 的記憶體釋放掉，如下圖最右邊的尾端，程式依然佔據了 300B 的記憶體空間
* 下圖為有執行釋放記憶體的程式，可以看到最右邊的尾端降到了 0 ，也就是程式在結束前已將 malloc 得到的記憶體空間釋放掉。
#### 透過 Massif 視覺化 “simulation” 過程中的記憶體使用量
```
$valginrd --tool=massif --max-snapshots=1000 ./qtest
$cmd> it
$cmd> quit
$massif-visualizer massif.
out.*
```
## trace-17-complexity的錯誤與解決
### **錯誤 1 : global-buffer-overflow**
開啟 Address Sanitizer 可以看到下圖出現的錯誤訊息
首先可以知道問題是 global-buffer-overflow 發生在某個記憶體位置，發生原因是在該記憶體位置讀了 4 bytes 。接下來看到問題發生在`console.c:369`，是跟傳入的 parameter `int *valp`有關。往回找到呼叫`add_param`的地方，可以看到`simulation`的記憶體位置傳入了函式， 這個變數是`bool` type，在`init_cmd()`時會將變數的記憶體位置傳遞給`add_param()`，再來因為`add_param()`的 parameter 接收的是`int *` type ，需要將`&simulation`強制轉型成`int *`。
接下來`add_param()`裡面會以`int`解讀`simulation`傳進來的記憶體位置中儲存的資料，這時會從傳進函式的記憶體位置往後取 4 bytes 去讀取，然而`simulation`作為`bool` type ，在我的開發環境下實際上只佔用了 1 byte ，若以`int`去解析會超過允許範圍，讀取到不合法的記憶體位置。
==解決 global-buffer-overflow== :
把`console.c`、`console.h`裡的`static bool echo`、`bool simulation`改為`int` type ，即可正常傳遞及使用。雖然會浪費多餘的 byte 來存`bool` type 的資料。
### **錯誤 2 :**
:::info
(挑戰題：思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target))
:bell:遇到的問題：
`$make`
`$make test`
第17筆有時成功有時失敗
`$make SANITIZER=1`
`$make test`
第17筆會出錯
`$make valgrind`
第17筆會對 (因為預設關閉 SANITIZER ，多跑幾次可能也會失敗。)
:::
:::warning
接下來花點時間研讀 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
:::
母體 : $(X_1,\ X_2,\ X_3,\ ...\ ,\ X_N)$
母體的 mean : $\begin{split}\mu = \dfrac{X_1 + X_2 + ... + X_N}{N}\end{split}$
若母體為連續隨機變數：$\begin{split}\mu = E(X) = \int_{b}^{a}xf(x)dx，f(x)為機率密度函數\end{split}$
母體的 Variance : $\begin{split}\sigma^2 = \dfrac{\sum_{i=1}^{N}\left({X_i-\mu}\right)^2}{N}\end{split}$
若母體為連續隨機變數：$\\ \begin{split} \sigma^2 = Var(X) &= \int_{b}^{a}(x-\mu^2)\cdot f(x)dx \\
&= \int_{b}^{a}x^2\cdot f(x)dx - \mu^2 \\
&= E\left(\left(x_i-\mu\right)^2\right) \\
&= E(X^2) - \left[ E(X) \right]^2\end{split}$
樣本的 mean : $\begin{split}\bar{x} = \dfrac{x_1 + x_2 + ... + x_n}{n}\end{split}$
樣本的 Variance : $\begin{split}S_x{^2} = \dfrac{\sum_{i=1}^{n}(x_i - \bar{x})^2}{n-1}\end{split}$
取樣一次，樣本數為 $n$，得到的 Variance : $\begin{split}S_x{^2} = \dfrac{\sum_{i=1}^{n}(x_i - \bar{x})^2}{n-1}\end{split}$，$n-1$ 代表 degree of freedom。
取 m 次樣本，每個樣本數為 $n$，對 Variance 的期望值 : $E(S^2) = \dfrac{S_1{^2} + S_2{^2} + S_3{^3} + ... + S_m{^2}}{m} = \sigma{^2}$
當一個母體的 $X_i$ 互不影響的連續隨機變數，得到各自相對應的相對頻度 (relative frequency) $f\left(X_i\right)$ 後，畫在 $XY$ 座標系上即可得到母體中數值的分布狀況為一常態分布。
對不同的常態分布 $X \sim N\left(\mu,\sigma^2\right)$，由於 $\mu$ 和 $\sigma$ 都不一定相同，在 $X$ 相同範圍的面積也會不盡相同，再來要求某些數值發生的機率每次都要對不同的分布面積做積分，這樣太麻煩了，因此需要做標準化，這樣就能直接查表。
標準常態分布 (Standard normal distribution)：將 $N\left(\mu,\sigma^2\right)$ 轉換 $N\left(0,1\right)$，此過程稱作
Z-transformation，標準常態分布的連續隨機變數稱為 Z-score。
Z轉換 (Z-transformation) ： 也就是標準化。$Z = \dfrac{X-\mu}{\sigma}$
取樣分布 (Sampling distribution)：隨機取樣得到的平均數 $\bar{x}$ 是隨機變數，經過多次取樣可以得到 $\bar{x}$ 的所有可能值，他們的機率分布即稱為取樣分布。
* 取樣分布的特性：
* $E\left(\bar{x}\right)$ = $\mu$
* 要如何知道取樣分布的標準差 (在可重複取樣的條件下)？$\sigma_x = \dfrac{\sigma}{\sqrt{n}}\ \ ,\ \sigma\ is\ the\ standard\ deviation\ of\ population\ and\ n\ is\ the\ sample\ size.$
如果不知道 $\sigma$ ，就用一次採樣得到的標準差 $S_x$ 來做為估計，估計標準差 $S = \dfrac{S_x}{\sqrt{n}}$
當母體為常態分布時，樣本的分布也會是常態分布。
當母體不為常態分布時，可以依據中央極限定裡找出樣本的分布情形，此時 $\bar{x} \sim N\left(\mu,\dfrac{\sigma{^2}}{n}\right)$。
點估計 (point estimation)：根據採樣的資料去估計母體的 parameter，估計結果為單一點的值，作為對一個未知的 parameter 的最佳估計值，稱為點估計。
當一點估計恰好等於母體的 parameter，則稱為 unbiased estimator。
又 $E\left(\bar{x}\right) = \mu$，所以 $E\left(\bar{x}\right)$ 樣本平均數的期望值，恰好就是一個 unbiased estimator。
#### Test of Ｈypothesis
想要知道一個母體 $\left( X_1,\ X_2,\ X_3,\ ...\ ,\ X_N \right)$的分布情形，需要找出 parameter ，也就是母體的平均數、變異數之類的，這會是一個固定的值 (constant)。
方法為先做出假設 (Hypothesis)，再從母體中取出樣本，統計出 Statistic ，也就是樣本的平均數、變異數之類的，由於根據取出的樣本群不同會造成得到的 Statistic 不同，所以這會是一個隨機變數 (random variable)。
利用 Statistic 去驗證假說，進而推論出母體實際上的分布情形。
* **Step 1 :** 提出 Hypothesis :
* **Null Hypothesis $H_0$：** 假設母體的 parameter ， $H_0 : \mu=\mu_0$，$\mu_0$ 為 educated guess ，根據經驗或理論得到的估計值。
* **Alternative Hypothesis $H_a$：** 如果驗證後結果是拒絕 Null Hypothesis 的假設，那麼應該應該怎麼辦？會有其他三種形成**不拒絕 (Fail to reject)** 的可能性，根據要驗證的目標選擇其一
* $H_a:\mu\neq\mu_0$ ( **Non-directional Hypothesis** or **Two-tailed Hypothesis** )
* $H_a:\mu > \mu_0$ ( **Directional Hypothesis** or **One-tailed Hypothesis** )
* $H_a:\mu < \mu_0$ ( **Directional Hypothesis** or **One-tailed Hypothesis** )
* **Step 2 :** Type I error : 選擇一個 Significance level ($\alpha$)，通常是 5% 或 1% ，只要低於這個機率，就拒絕 $H_0$ 的假設。即使 $H_0$ 實際上是 true 也要拒絕，但是這樣是錯誤的，所以又叫作 Type I error 的機率。
Why do this ? 根據 $H_0$ 可以畫出一個常態分布 ，從樣本可以得到 sample mean 並且可以在分布中畫出它的位置，假如今天 sample mean 離 $H_0$ 太遠，例如位在常態分布的兩端，雖然 $H_0$ 有可能是對的，但因為根據採樣結果，我們認為發生的機率太低，沒有足夠的信心去不拒絕假設。
* **Step 3 :** 選定適當的 test ，例如 Z-test、t-test。
* **Step 4 :** 假設 $H_0:\mu = \mu_0$ 成立且取樣數為大樣本的情況下，$\bar{x}$ 的取樣分布近似常態分布， $\bar{x} \sim N\left(\mu,\dfrac{\sigma^2}{n}\right)$可以根據 Z-test 的公式得出檢定統計量 (test statistic) $Z$ ，也就是將該次取樣的平均值做標準化，可能是常態分布 (母體的標準差已知) 或 t-distribution (母體的標準差未知)。
* 例如要對母的平均數做假設檢定時：
* 當母體的標準差已知，可用 $Z = \dfrac{\bar{x}-\mu}{\sigma / \sqrt{n}}$ 得到經過標準化後該次取樣的平均值，做為檢定統計量。
* 當母體的標準差未知，可用 $Z = \dfrac{\bar{x}-\mu}{S / \sqrt{n}}$ ，$S$ 為取樣分布的標準差，得到經過標準化後該次取樣的平均值，做為檢定統計量。
* **Step 5 :** 按照 $\alpha$、$H_a$，可以查詢 $\alpha$ 在 Z-score 表上的值，再根據假設是不是左尾檢定 ($H_0 : \mu \gt \mu_0$) 來決定要不要加負號，在母體的標準常態分布上畫出拒絕的範圍，稱為 critical region。 e.g. 若 $\alpha$ 為 0.05 ，代表左右各 0.025 ，查表可得到 Z-score 為 1.96 ，可以找到小於 -1.96 及大於 1.96 的兩個範圍。
* **Step 6 :** 計算採樣做出的檢定統計量 $Z_{obs}$。
* **Step 7 :** 查詢 $Z_{obs}$ 在 Z-score 表上的值，畫在母體的標準常態分布上，看看有沒有落在 critical region。
又或者是用檢定統計量 $t_{obs}$ 查詢在 p-value 表格上的值，可以直接用 p-value 去跟 $\alpha$ 比較，若 $\alpha \gt p-value$ 則拒絕 $H_0$，若 $\alpha \leq p- value$ 則不拒絕 $H_0$。 p.s. 如果是雙尾檢定，p-value 要乘以 2。
#### Student's t-distribution
Student's t-distribution 是一組經過標準化的連續機率分布，這是因為樣本變異數的分母是自由度，當自由度不同時會呈現不同長相的 t-distribution ，每一個都是屬於 student's t-distribution。會用在要估計常態分布的母體的平均值時，當樣本數較少且母體標準差未知的情況下用此分布得到檢定統計量 $t_{obs}$
$t = \dfrac{\bar{x} - \mu_0}{S / \sqrt{n}} \sim t\left(n-1\right)$
t-distribution 的分母為 n-1 ，也就是 degree of freedom，當這個值越大，呈現出的 t-distribution 就會越接近常態分布。
在做假設檢定要查表的時候，就必須要知道樣本數 n ，以自由度 n-1 和 $t_{obs}$ 去查表。
#### Student's t-test
目的：
* 單樣本檢定：檢定一個常態分布的母體的平均數是否不拒絕虛無假設
* 獨立雙樣本檢定：用來比較兩組資料的母體平均值是否有顯著的差異，虛無假設為兩個母體的平均值之差是否為某一實數。
* 當兩個母體的變異數相同：為 Student's t-test ，此時自由度為 $\left(sample\ size\ A + sample\ size\ B\right)-2$ 。
* 當兩個母體的變異數不相同：為 Welch's t-test ，此時自由度為 Welch 自由度。
使用前提：
1. 取樣的樣本數為小樣本 (n<30)
2. 母體為常態分布
3. 母體的標準差 $\sigma$ 未知
這時候就要用 t-distribution 來做為檢定統計量，稱作 t-test 。
$t=\dfrac{signal}{noise} = \dfrac{difference\ between\ group \ means}{variability\ of\ groups}$
* 單樣本檢定：$t = \dfrac{\bar{x}-\mu_0}{S/\sqrt{n}}\sim t\left(n-1\right)\ ,\ S_x = \sqrt{\dfrac{\sum_{i=1}^{n}(x_i - \bar{x})^2}{n-1}}$
* 獨立雙樣本檢定：
* 當兩母體變異數相同：
$\begin{split} t = \dfrac{\bar{x_1}-\bar{x_2}-\mu_0}{\sqrt{S_p{^2}/n_1 + S_p{^2}/n_2}}\sim t\left(n_1+n_2-2\right)\ ,
S_p{^2} &= \dfrac{\sum_{i=1}^{n_1}(x_{1i} - \bar{x_1})^2 + \sum_{j=1}^{n_2}(x_{2j} - \bar{x_2})^2}{n_1 + n_2 - 2}\\
&= \dfrac{\left(n_1-1\right)S_1{^2} + \left(n_2-1\right)S_2{^2}}{n_1+n_2-2}\end{split}$
$\ i = 1\ ...\ n_1\ ,\ x_{1i}\ =participants\ in\ group\ A\\
\ j = 1\ ...\ n_2\ ,\ x_{2j}\ =participants\ in\ group\ B$
$S_p$ is an estimator of the pooled standard deviation of the two samples: it is defined in this way so that its square is an unbiased estimator of the common variance whether or not the population means are the same.
* 當兩母體變異數不相同： (Welch's t-test)
$t = \dfrac{\bar{x_1} - \bar{x_2}}{s_{\bar{\Delta}}} \sim t\left(d.f.\right)\\
s_{\bar{\Delta}} = \sqrt{\dfrac{S_1{^2}}{n_1} + \dfrac{S_2{^2}}{n_2}}\\
degree\ of\ freedom\ ,\ d.f.\ =\ \dfrac{\left(\dfrac{S_1{^2}}{n_1} + \dfrac{S_2{^2}}{n_2}\right)^2}{\dfrac{\left(\dfrac{S_1{^2}}{n_1}\right)^2}{n_1-1} + \dfrac{\left(\dfrac{S_2{^2}}{n_2}\right)^2}{n_2-1}}$
Reference：
* [臺灣通識網General Education TW-開放式課程GET](https://www.youtube.com/watch?v=1t-mlrMp4Bo)
* [NSYSUOCW](https://www.youtube.com/watch?v=R8H7WEtdKXA&list=PLuz2BOX_eyHGm8F0Dx7k60lUwvgVf7Mnd&index=3)
* [母體變異數v.s.樣本變異數](https://highscope.ch.ntu.edu.tw/wordpress/?p=69367)
* [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test)
* [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)
**To be continued..**
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet