2025q1 Homework1 (lab0)

contributed by < yunchieh0227 >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   8
  On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
  Model name:             11th Gen Intel(R) Core(TM) i7-11370H @ 3.30GHz
    CPU family:           6
    Model:                140
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             1
    CPU(s) scaling MHz:   22%
    CPU max MHz:          4800.0000
    CPU min MHz:          400.0000
    BogoMIPS:             6604.80
    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 ss ht tm pbe
                           syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmpe
                          rf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2ap
                          ic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb cat_l2 cdp_l2 ss
                          bd ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms i
                          nvpcid rdt_a avx512f avx512dq rdseed adx smap avx512ifma clflushopt clwb intel_pt avx512cd sha_ni avx512bw avx512vl xsa
                          veopt xsavec xgetbv1 xsaves split_lock_detect user_shstk dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp 
                          hwp_pkg_req vnmi avx512vbmi umip pku ospke avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq
                           rdpid movdiri movdir64b fsrm avx512_vp2intersect md_clear ibt flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    192 KiB (4 instances)
  L1i:                    128 KiB (4 instances)
  L2:                     5 MiB (4 instances)
  L3:                     12 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-7
Vulnerabilities:          
  Gather data sampling:   Mitigation; Microcode
  Itlb multihit:          Not affected
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Not affected
  Reg file data sampling: Not affected
  Retbleed:               Not affected
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop, KVM SW loop
  Srbds:                  Not affected
  Tsx async abort:        Not affected

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

q_new

目標

初始化一個新的 queue
分配記憶體並正確初始化 list_head
若記憶體分配失敗，回傳 NULL

實作

-    return NULL;
+    struct list_head *head = malloc(sizeof(struct list_head));
+    if (!head) 
+        return NULL;
+    INIT_LIST_HEAD(head);
+    return head;

使用 malloc()分配 list_head 記憶體
使用 INIT_LIST_HEAD() 初始化，確保它是空的

q_free

目標

q_free 負責釋放 queue 所有的節點，確保沒有記憶體洩漏。
如果 head 為 NULL，則不做任何操作。
需要正確釋放：

每個節點 element_t
每個字串 value
佇列本身 head

實作考量

使用 list_for_each_entry_safe 而不是 list_for_each_entry，因為刪除節點時，list_for_each_entry 會存取 next，可能導致指標失效或記憶體區段錯誤 list_for_each_entry_safe 會先存好下一個節點，確保刪除當前節點後仍能安全走訪
將 free(head); 放在最後，因為 head 代表佇列本身，必須確保所有節點都已經刪除後，才釋放它

q_insert_head

目標

在 queue 的開頭正確插入新的節點

實作考量

使用 list_add 而不是手動調整 next，list_add 會確保 new_elem 的 prev 和 next 都正確設定

記憶體管理與錯誤處理

檢查點	錯誤處理方式
`head` 或 `s`	若失敗，返回 `false`
`malloc(sizeof(element_t))`	若失敗，返回 `false`
`strdup`	若失敗，釋放 `new_elem`，返回 `false`

如果 strdup 失敗，但 new_elem 已經分配了記憶體，必須釋放 new_elem，否則會發生記憶體洩漏。

q_insert_tail

記憶體管理與錯誤處理方法與 q_insert_head 邏輯相同，其餘差別如下：

比較項目	`q_insert_head`	`q_insert_tail`
插入位置	佇列開頭	佇列尾端
插入方式	`list_add`	`list_add_tail`

q_remove_head

q_remove_head 用來移除佇列的第一個節點，首先檢查 head 是否為 NULL 或佇列是否為空若是則直接返回 NULL，接著使用 list_first_entry 取得佇列的第一個節點，並用 list_del 將該節點從佇列中移除，但不釋放記憶體

element_t *old_head = list_first_entry(head, element_t, list);
    list_del(&old_head->list);

若 sp 不為 NULL，則用 strncpy 將 value 複製到 sp，確保長度不超過 bufsize - 1，並手動加上 '\0' 以避免字串溢出。

strncpy(sp, old_head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';

最後，釋放 old_head->value 來避免記憶體洩漏，並釋放該節點記憶體，確保佇列的結構維持完整

list_first_entry

#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)

取得佇列中的第一個 element_t 節點，透過 head->next 找到 element_t 結構體，member 指的是 element_t 裡的 list_head

list_del

將 entry 從佇列的鍊結串列中移除，且不會釋放 entry 的記憶體，這樣佇列結構不會被破壞，但 entry 還存在，必須手動釋放

q_remove_tail

q_remove_tail 的邏輯與 q_remove_head 相同，唯移除的節點位置不同：

q_remove_head 透過 list_first_entry 取得第一個節點 head->next
q_remove_tail 透過 list_last_entry 取得最後一個節點 head->prev

q_size

目標

計算 queue 內的節點數量，但不修改 queue 的內容

實作

檢查佇列是否為 NULL ，如果是，代表佇列未初始化，直接回傳 0
逐一走訪佇列，計算數量

int count = 0;
element_t *entry;
list_for_each_entry(entry, head, list)
    count++;

list_for_each_entry 是一個 for 迴圈，會逐一走訪佇列的所有節點，每次 count++

for (entry = list_first_entry(head, element_t, list);
     &entry->list != head;
     entry = list_next_entry(entry, list))

list_first_entry 取得佇列第一個 element_t 節點
list_next_entry 取得下一個 element_t，直到回到 head

走訪完所有節點後，回傳 count，表示佇列內的元素個數

q_delete_mid

目標

q_delete_mid 用來刪除佇列中間的節點，但不影響佇列內其他元素，並確保記憶體正確釋放

實作

計算佇列的長度，取得中間節點索引

int mid_index = q_size(head) / 2;

透過 q_size() 計算 queue 的長度，並用 size / 2 找到中間節點的位置

使用 list_for_each_entry 逐一走訪佇列

list_for_each_entry(entry, head, list) {
    if (i == mid_index) { /* 進入中間節點 */

遍歷佇列的所有 element_t 節點，當 i 達到 mid_index，代表找到中間節點

從佇列中移除該節點

list_del(&entry->list);

list_del 會讓佇列結構維持完整，但不釋放記憶體

釋放節點記憶體，確保 queue 乾淨

q_release_element(entry);

透過 q_release_element 統一管理記憶體釋放，避免 double free 或 memory leak

q_delete_dup

目標

刪除佇列內所有重複的元素，確保佇列中~~所有 value 都是唯一的~~所有重複的元素都被刪除

實作

如果佇列為空或沒有元素，則無須刪除，直接回傳 false
使用 list_for_each_entry_safe 逐一走訪整個佇列，確保當前節點 cur 被刪除時，不影響迴圈的執行

element_t *cur, *next;
list_for_each_entry_safe (cur, next, head, list) {

比較 cur 和 next 的 value 是否相同：

if (&next->list != head && strcmp(cur->value, next->value) == 0) {

相同，則 cur 是重複的節點，應該刪除
不同，則繼續走訪下一個節點

刪除重複的節點：
先用 list_del 把 cur 從佇列的鏈結串列中移除，再用 q_release_element 釋放該節點的記憶體，確保 cur->value 也被正確釋放
如果有刪除任何節點，回傳 true，否則回傳 false

更改q_delete_dup邏輯

更改為刪除所有重複的元素，包括第一次出現的節點，確保佇列內不會保留任何重複的值

+    bool duped = false;
     list_for_each_entry_safe (cur, next, head, list) {
+    
+        if(&next->list != head && duped && strcmp(cur->value, next->value) != 0){
+            list_del(&cur->list);
+            q_release_element(cur);
+            duped = false;
+            continue;
+        }
         if (&next->list != head && strcmp(cur->value, next->value) == 0) {
             list_del(&cur->list);
             q_release_element(cur);
             removed = true;
+            duped = true;
         }
     }
+    if(duped){
+        q_remove_tail(head, NULL, 0);
+        duped = false;
+    }

使用 duped 變數來標記當前是否處於重複狀態
cur 與 next 值相同時，刪除 cur，並將 duped 設為 true。
duped == true 代表曾經發現並刪除重複元素且 cur 不再與 next 相同時，也就是該重複元素已被刪除至最後一個時，確保第一個重複的元素也被移除
最後如果 duped == true，代表佇列的尾端仍有重複元素，刪除最後一個重複元素

q_swap

目標

交換佇列內的相鄰節點，且不改變節點內的 value

實作

list_move

先將 entry (要移動的節點) 從佇列中刪除：

__list_del(entry->prev, entry->next);

entry->prev->next = entry->next; 讓前一個節點跳過 entry 直接連到 entry->next
entry->next->prev = entry->prev; 讓後一個節點的 prev 直接連回 entry->prev

將 entry 加回佇列的新位置 head->next：

list_add(entry, head);

entry->next = head->next; 讓 entry 的 next 指向原來 next 的後一個，即head->next
entry->prev = head; 讓 entry 的 prev 指向 head
head->next->prev = entry; 讓 entry 的 next ，即原來 next->next 連回 entry
head->next = entry; 讓 head 的 next 變成 entry

q_reverse

目標

轉佇列內所有的節點順序，且不改變節點的 value。

實作

如果佇列為空或只有一個節點，則無須反轉，直接返回。
使用 list_for_each_entry_safe 逐一走訪佇列

struct list_head *cur, *next;
    list_for_each_entry_safe (cur, next, head, list)

cur 指向目前的節點，next 指向 cur->next
使用 _safe 版本，確保當 cur 被移動後，不影響走訪

list_move(cur, head);

將 cur 放到 head->next ，使每個遍歷的節點都會被依序插入到佇列開頭，達成反轉效果

`list_for_each_entry_safe` 的必要性

不使用 list_for_each_entry 而要使用 _safe 版本

-    element_t *cur;
-    list_for_each_entry (cur, head, list)
+    element_t *cur, *next;
+    list_for_each_entry_safe (cur, next, head, list)

因為我們在迴圈內對 cur 進行 list_move，這會改變 cur 的 next 和 prev 指標list_for_each_entry_safe 會在每次迴圈開始前，就先把 cur->next 儲存到 next，確保即使 cur 被刪除或移動，仍然可以安全地訪問下一個節點

-#define list_for_each_entry(pos, head, member)                 \
-    for (pos = list_first_entry(head, typeof(*pos), member);   \
-         &pos->member != (head);                               \
-         pos = list_next_entry(pos, member))

+#define list_for_each_entry_safe(pos, safe, head, member)       \
+    for (pos = list_first_entry(head, typeof(*pos), member),    \
+         safe = list_next_entry(pos, member);                   \
+         &pos->member != (head);                                \
+         pos = safe, safe = list_next_entry(safe, member))

如果使用 list_for_each_entry，當 cur 被移動到 head->next 時，原來的 cur->next 會發生變化，導致記憶體訪問邏輯錯誤

比較項目	`list_for_each_entry`	`list_for_each_entry_safe`
走訪方式	直接訪問下一個節點	`safe` 儲存下一個節點，確保 `pos` 被刪除後仍能繼續
允許刪除節點？	❌ 不允許刪除，否則 `pos->next` 失效	✅ 允許刪除，不影響走訪
允許移動節點？	❌ `list_move` 會影響 `pos->next`	✅ `list_move`不影響迴圈
適用場景	只讀取、不刪除佇列	需要刪除或移動佇列節點
可能問題	`Use After Free`、`無窮迴圈`、`Segmentation Fault`	無此問題，走訪能正常運作

q_reverseK

目標

給定一個鏈結串列的 head 節點，請每 k 個節點為一組進行反轉，並返回修改後的鏈結串列

k 是一個正整數，且 k ≤ 鏈結串列的長度
如果鏈結串列的節點數不是 k 的倍數，則最後剩餘的節點保持原樣，不進行反轉

實作

檢查基本條件

若 head 為 NULL、空鏈結串列 list_empty ，或 k < 2，則不進行反轉
初始化變數
- cur：當前處理的 k 組的起點
- tail：用來找到這組的最後一個節點
- next_group：記錄下一組的開始
- prev_tail：指向前一組的尾部，用於連接前後區塊

檢查是否有足夠的 k 個節點

tail = cur;
int count = 1;
while (count < K && tail->next != head) {
    tail = tail->next;
    count++;
}
if (count < K)
    break; // 剩餘的節點不足 K 個，停止反轉

tail 移動 k-1 步，確保有足夠的節點可以反轉

反轉 k 個節點

使用 list_move，將 cur->next 依序插入 prev_tail 之後，達成局部反轉

更新指標

prev_tail = cur; // 記錄當前 K 組的尾部
cur = next_group; // 移動 cur 到下一組的開始，繼續反轉

q_sort

修正排序穩定性問題

-(descend && strcmp(first->value, second->value) >= 0) ||
-(!descend && strcmp(first->value, second->value) <= 0)
+(descend && strcmp(first->value, second->value) > 0) ||
+(!descend && strcmp(first->value, second->value) < 0)

前後版本的差異就在等號上，儘管對這兩種寫法輸入測資答案看起來都會是正確的，但其實，原本的寫法在兩個字串完全相等時 strcmp == 0 仍然會將第一個節點移動到第二個節點之後，破壞了排序的穩定性 stable sorting ，導致具有相同字串的元素在排序前後相對位置可能改變

修改後的寫法，當兩個節點的值相等時，不會更動順序，因此保持穩定排序的特性，修正了原先 Not stable sort 的錯誤訊息。

q_ascend, q_descend

遍歷方向不同：
- q_ascend：從尾到頭
- q_descend：從頭到尾
比較邏輯不同：
- q_ascend：若前方存在更大的值則刪除當前節點。
- q_descend：若後面存在更大的值則刪除當前節點。

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

Dudect 透過「實驗測試 + 統計分析」來檢測程式是否符合 Constant-Time，而不是依賴傳統的靜態分析

步驟一 : 測量執行時間

定義測試輸入類別 (Classes Definition)
Dudect 採用 Fix-vs-Random 測試法：
- 第一組 Fixed Class：輸入值固定不變
- 第二組 Random Class：每次測試時，輸入值隨機變化
這種測試方式的優點：
✅ 可以觸發特殊的邊界條件，例如某些加法運算在 0000 的輸入會更快

若兩組輸入的執行時間分佈不同，則可能存在時間洩漏。

使用 CPU 時鐘來測量執行時間 (Cycle Counters)
現代 CPU 提供高精度的時鐘週期計數器 (Cycle Counter)：
- x86 架構：使用 TSC (Time Stamp Counter)
- ARM 架構：使用 Systick 計數器
- 若 CPU 沒有內建計時功能，可以使用高精度計時器 (High-Resolution Timer) 或外部設備 (External Equipment)
✅ 這些計數器可以準確地測量程式的執行時間，避免 OS 排程造成的影響
減少環境變數影響 (Environmental Conditions)
在測試過程中，環境因素，例如：作業系統調度、CPU 電源管理等，可能會影響測試結果，因此每次測試
- 隨機決定要執行固定輸入或隨機輸入，降低測試偏差
- 測試前，先準備好所有輸入數據，避免測試過程中因資料準備影響執行時間

步驟二：應用後處理

Cropping (去除異常值)
由於執行時間分佈通常會有向右偏移 (skewed distribution)，某些測量值可能特別高，這可能是：
- 測量誤差 (Measurement Artifacts)。
- OS 進程切換 (Interrupts from the OS)。
- 其他背景程式影響 (Extraneous Activities)。
為了確保數據準確，可以去除超過某個閾值的測量值，避免極端值影響統計結果
Higher-Order Preprocessing (高階數據處理)

依據使用的統計方法，可以應用非線性轉換來增強測試能力
例如 Centered Product Method，它模擬高階 DPA (Differential Power Analysis) 攻擊，用來捕捉更細微的變異

✅ 這些方法可以幫助檢測高階時間洩漏，使測試結果更準確

步驟三: 應用統計檢定 (Apply Statistical Test)

Dudect 工具中的 simulation 模式透過實驗，而非理論分析來驗證程式的時間複雜度是否為常數時間 (Constant-Time, CT)

此方法的核心概念是：

測量程式執行時間，對兩組不同輸入類別進行測試
進行統計分析，比較執行時間的變異性
使用 Student’s t-Distribution (t 分佈) 進行 Welch’s t-Test 來檢測執行時間是否受輸入影響。

Student’s t-Distribution (t 分佈)

什麼是 t 分佈？

Student’s t-Distribution 是一種 連續機率分佈，適用於 小樣本統計分析，特別在母體變異數未知時。當樣本數較少時，t 分佈比標準常態分佈更能反映數據變異性

t 分佈的特性如下：

對稱於 0，即其均值為 0
形狀類似於標準常態分佈，但尾部較厚，表示 t 分佈能夠適應較大的變異
當 自由度
$ν$ 增加時，t 分佈會趨近於標準常態分佈
$N (0, 1)$

t 分佈的機率密度函數 (PDF)

t 分佈的機率密度函數（Probability Density Function, PDF）定義如下：

f (t) = \frac{Γ (\frac{ν + 1}{2})}{\sqrt{π ν} Γ (\frac{ν}{2})} {(1 + \frac{t^{2}}{ν})}^{- \frac{ν + 1}{2}}

其中：

$t$ 是變數
$ν$ 是 自由度 (Degrees of Freedom, df)，通常為 樣本數 - 1
$Γ (x)$ 是 Gamma 函數，類似於階乘的擴展：

$Γ (n) = (n - 1)!$
當
$n$ 為整數時，Gamma 函數等於
$(n - 1)!$

期望值與變異數

期望值 (Mean)：
- 若
  $ν > 1$ ，則
  $E [t] = 0$ 。
- 若
  $ν \leq 1$ ，則無法定義（不存在有限的期望值）
變異數 (Variance)：
- 若
  $ν > 2$ ，則
  $V a r (t) = \frac{ν}{ν - 2}$ 。
- 若
  $1 < ν \leq 2$ ，則無法定義（趨向無窮大）

累積分佈函數 (CDF)

t 分佈的累積分佈函數（Cumulative Distribution Function, CDF）可表示為：

F (t) = \frac{1}{2} + t \cdot \frac{Γ (\frac{ν + 1}{2})}{\sqrt{π ν} Γ (\frac{ν}{2})}_{2} F_{1} (\frac{1}{2}, \frac{ν + 1}{2}; \frac{3}{2}; - \frac{t^{2}}{ν})

其中：

$_{2} F_{1} (a, b; c; z)$ 是 超幾何函數（Hypergeometric Function），用於表示累積分佈

t 分佈與標準常態分佈的關係

當
$ν \to \infty$ ，t 分佈的形狀逐漸趨近於標準常態分佈
$N (0, 1)$ 。
但當
$ν$ 小時，t 分佈的尾部較厚，表示其極端值出現的機率較高。

這表示：

當樣本數小時，使用 t 分佈可以更準確地描述變異性。
當樣本數增加時，可以直接使用標準常態分佈來進行推斷。

數學上：

lim_{ν \to \infty} t_{ν} = N (0, 1)

這說明當自由度無限大時，t 分佈會變成標準常態分佈。

t 分佈的應用

t 分佈主要應用於：

T-Test (t 檢定)：比較兩組數據的均值是否不同
信賴區間 (Confidence Interval, CI) 計算：當樣本數較少時，使用 t 分佈來估算均值的信賴區間
線性回歸分析 (Linear Regression Analysis)：在回歸模型中檢驗係數是否顯著

t 分佈的計算範例

假設有 10 個樣本，樣本均值

\bar{x} = 5

，樣本標準差

s = 2

，要求 95% 信賴區間，則：

CI = \bar{x} \pm t_{α / 2, ν} \times \frac{s}{\sqrt{n}}

查表得

t_{0.025, 9} = 2.262

，代入：

CI = 5 \pm 2.262 \times \frac{2}{\sqrt{10}}

計算後得到：

(3.57, 6.43)

這表示 在 95% 的信心水準下，母體均值落在 (3.57, 6.43) 的範圍內。

🔹 總結

t 分佈適用於小樣本統計分析，當母體變異數未知時使用
自由度
$ν$ 影響 t 分佈的形狀，當
$ν$ 增大時，t 分佈趨近於標準常態分佈
主要用於 t 檢定、信賴區間估計、回歸分析等統計推論
計算信賴區間時，t 分佈能提供更準確的區間估計，特別是小樣本時

在 simulation 模式中，Dudect 採用兩種統計方法來檢測時間變異性：

Welch’s t-Test (t 檢定)：檢測兩組數據的均值是否有顯著差異
- 若兩組數據的均值不同，則可能存在時間變異性
- t 檢定統計量計算公式：
  
  $t = \frac{{\bar{x}}_{1} - {\bar{x}}_{2}}{\sqrt{\frac{s_{1}^{2}}{n_{1}} + \frac{s_{2}^{2}}{n_{2}}}}$
- 若
  $| t |$ 足夠大，則拒絕零假設，表示兩組數據均值顯著不同
Kolmogorov-Smirnov (KS) Test (KS 檢定)：檢測兩組數據的整體分佈是否不同
- 透過計算累積分佈函數 (CDF) 的最大差異：
  
  $D = sup_{x} | F_{1} (x) - F_{2} (x) |$
- 若
  $D$ 過大，則表示兩組數據的分佈不同，可能存在非均值層面的時間變異

這兩種方法可以互補，t 檢定檢測均值差異，而 KS 檢定
關注整體分佈的不同，以確保測試結果的可靠性

2025q1 Homework1 (lab0)

開發環境

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

q_new

目標

實作

q_free

目標

實作考量

q_insert_head

目標

實作考量

記憶體管理與錯誤處理

q_insert_tail

q_remove_head

list_first_entry

list_del

q_remove_tail

q_size

目標

實作

q_delete_mid

目標

實作

q_delete_dup

目標

實作

更改q_delete_dup邏輯

q_swap

目標

實作

list_move

q_reverse

目標

實作

list_for_each_entry_safe 的必要性

q_reverseK

目標

實作

q_sort

修正排序穩定性問題

q_ascend, q_descend

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

步驟一 : 測量執行時間

步驟二：應用後處理

步驟三: 應用統計檢定 (Apply Statistical Test)

Student’s t-Distribution (t 分佈)

什麼是 t 分佈？

t 分佈的機率密度函數 (PDF)

期望值與變異數

累積分佈函數 (CDF)

t 分佈與標準常態分佈的關係

t 分佈的應用

t 分佈的計算範例

🔹 總結

Read more

影像處理

2025q1 Homework1 (ideas)

`list_for_each_entry_safe` 的必要性