2025q1 Homework1 (lab0)

# 2025q1 Homework1 (lab0) contributed by <`thwuedwin`> {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發環境 ```shell $ 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: 46 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 20 On-line CPU(s) list: 0-19 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i7-12700 CPU family: 6 Model: 151 Thread(s) per core: 2 Core(s) per socket: 12 Socket(s): 1 Stepping: 2 CPU(s) scaling MHz: 35% CPU max MHz: 4900.0000 CPU min MHz: 800.0000 BogoMIPS: 4224.00 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 con stant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault e pb ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflu shopt clwb intel_pt sha_ni xsaveopt xsavec xgetbv1 xsaves split_lock_detect user_shstk avx_vnni dtherm ida arat pln pts hwp hwp_notify hwp_act_window hw p_epp hwp_pkg_req hfi vnmi umip pku ospke waitpkg gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_clear serialize pconfig arch_lbr ibt flush_l1d ar ch_capabilities Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 512 KiB (12 instances) L1i: 512 KiB (12 instances) L2: 12 MiB (9 instances) L3: 25 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-19 Vulnerabilities: Gather data sampling: Not affected Itlb multihit: Not affected L1tf: Not affected Mds: Not affected Meltdown: Not affected Mmio stale data: Not affected Reg file data sampling: Mitigation; Clear Register File 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 BHI_DIS_S Srbds: Not affected Tsx async abort: Not affected ``` ## 佇列操作的實作 ### q_new > commit [78d7552](https://github.com/sysprog21/lab0-c/commit/78d755205535e02783795494cc9a392f8d6ae3d9) `struct list_head *q_new()` #### 參數此函式不接受參數 #### 回傳值 `struct list_head *`：指向佇列起始節點的指標 #### 描述 - `q_new` 會動態配置一個大小為 `sizeof(struct list_head)` 位元組的記憶體空間，並將其初始化，作為佇列的起始節點。 - 此實作會回傳一個可以由 `q_free` 釋放的指標，使用後需要呼叫 `q_free` 來釋放記憶體空間。 ### q_free > commit [78d7552](https://github.com/sysprog21/lab0-c/commit/78d755205535e02783795494cc9a392f8d6ae3d9), [b574a09](https://github.com/sysprog21/lab0-c/commit/b574a09e18dce80aaec2847fc2d53b80f9734602) `void q_free(structure list_head* head)` #### 參數 - `struct list_head *head`：指向佇列起始節點的指標 #### 回傳值此函式不回傳任何值（`void`） #### 描述 - 若傳入 NULL，直接結束 - 此函式需接受由 `q_new` 配置並回傳的指標 `head` ，並迭代釋放該佇列的每一個元素。若傳入的指標不是由 `q_new` 建立，或已被釋放則會造成未定義行為。 - 由 `head` 所指向的鏈結串列必須要維護正確的單向環狀結構，並且不能有內部的環，否則會造成未定義行為。 - `q_free` 需負責釋放以下函式配置的記憶體空間： - `q_new`：配置 `struct list_head` 的記憶體空間。 - `q_insert_head` / `q_insert_tail`：配置 element_t 結構的記憶體空間，並額外分配字串存儲所需的 char* 記憶體空間。在 commit *78d7552* 中，我在迭代釋放鏈結串列元素後嘗試初始化 `head`，但發現 `head` 已經被釋放，因此 `head->next` 和 `head->prev` 指向未定義的記憶體位置，導致 Valgrind 報錯。在 commit *b574a09*，我移除了這兩行修改來避免非法記憶體存取。 ```c head->prev->next = head->next; head->next->prev = head->prev; free(head); ``` ### q_insert_head / q_insert_tail > commit [bd856f7](https://github.com/sysprog21/lab0-c/commit/bd856f79445c468ef47b155346ebe32b8b767105) `bool q_insert_head(struct list_head *head, char *s);` `bool q_insert_tail(struct list_head *head, char *s);` #### 參數 - `struct list_head *head`：指向首節點的指標 - `char *s`：節點內儲存的字串 #### 回傳值 `bool`：插入是否成功 - 成功回傳 true - 失敗回傳 false #### 描述若傳入 NULL，直接回傳 `false` 此函式會動態配置 1. element_t 結構的記憶體空間 2. 傳入字串長度加 1 個字元的記憶體空間將該節點插入 `head` 所指向的鏈結串列的**開頭**或**結尾**。動態配置出的記憶體空間由 `head` 統一管理，需呼叫 `q_free` 釋放配置出的空間。 #### 實作 1. 使用 malloc 分配 element_t 結構的記憶體空間，並額外分配 strlen(s) + 1 大小的空間來儲存字串 2. 使用 strncpy 將字串複製到分配的記憶體中，並確保字串以 '\0' 結尾 3. 將新節點插入至指定的位置 ### q_remove_head / q_remove_tail > commit [b32500c](https://github.com/sysprog21/lab0-c/commit/b32500c75fc86dfb51d66a8c5645611dd5541251) #### 功能從 `head` 所指向的鏈結串列中移除**首節點**或**尾節點**，並將節點內儲存的字串複製至 `sp`。 #### 參數 - `strcut list_head *head`：指向首節點的指標 - `char *sp`：用於存放被移除節點的字串 - `size_t bufsize`：`sp` 可用的緩衝區大小 #### 回傳值 `element_t*` 指向被移除節點的指標，若佇列為空則回傳 NULL #### 實作 1. 若 `head` 為 NULL 或鏈結串列為空，直接回傳 NULL 2. 利用 lish.h 提供的巨集 list_first_entry 或 list_last_entry 找出要移除的節點 3. 利用 strncpy 將節點內的字串複製到 `sp`，並確保字串以 '\0' 結尾 4. 從鏈結串列中移除該節點，並利用 list.h 提供的巨集 INIT_LIST_HEAD 初始化該節點以保證安全性（以下範例為 q_remove_head） ```c struct list_head *next = element->list.next; head->next = next; next->prev = head; INIT_LIST_HEAD(&(element->list)); ``` ### q_size > commit [e36af1b](https://github.com/sysprog21/lab0-c/commit/e36af1bc6642a3ef160e8f559aca1300e858567d) #### 功能回傳 `head` 指向的鏈結串列的大小 #### 參數 - `struct list_head *head`：指向首節點的指標 #### 回傳值 `int` 鏈結串列的大小 #### 實作 **此實作來自[2025 年 Linux 核心設計課程作業 —— lab0 (A)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a?fbclid=IwY2xjawI5NVFleHRuA2FlbQIxMQABHdgrW8RmuXD1xu6d3vJpoAqKlBhC3CoWvmC4R2hrC-xm5kri6sh3gcWDaQ_aem_GvDGHttg-U_pIgp--9s7pA)** - 若 `head` 為 NULL 或空鏈結串列，回傳 0 - 否則使用 list.h 提供的巨集 list_for_each 迭代計算鏈結串列大小 ### q_delete_mid > commit [abb7e1e](https://github.com/sysprog21/lab0-c/commit/abb7e1eccbf50d92bcc428ac7788698c81e8b183) #### 功能刪除 `head` 指向的鏈結串列的**中間節點**，若鏈結串列包含 n 個節點，則中間節點為第 $\lfloor n/2\rfloor$ 個節點（以 0 為起始索引） #### 參數 - `struct list_head *head`：指向首節點的指標 #### 回傳值 `bool`： - 成功刪除節點則回傳 true - 若 `head` 為 NULL 或空鏈結串列，回傳 false #### 實作最初的實作方式是先使用 q_size 取得鏈結串列的長度，然後透過除法計算中間節點的索引，最後使用 for 迴圈找到該節點： ```c int target = (q_size(head) + 1) / 2; struct list_head *node = head; for (int i = 0; i < target; i++) { node = node->next; } ``` 然而，此方法的時間複雜度為 $O(n)$，且使用了除法運算。此外，鏈結串列**本質上不支援隨機存取**，計算節點索引的方式與鏈結串列的特性不符。因此，我改用**快慢指標**來尋找中間節點： - 快指標 (fast) 每次前進兩步，慢指標 (slow) 每次前進一步。 - 當快指標到達鏈結串列的結尾時，慢指標正好指向中間節點。 ```c fast = slow = head; do { slow = slow->next; fast = fast->next->next; } while (fast != head && fast->next != head); ``` 快慢指標的概念很簡單，善用了鏈結串列的性質以避免除法運算，雖然複雜度同樣是 $O(n)$，但這個方法更加優雅。此外，在我對 q_reverseK 一籌莫展時，快慢指標給了我很好的靈感。定位出中間節點後就只要簡單的移除，並正確釋放記憶體空間。 ### q_delete_dup > commit [2bcccee]([2bcccee](https://github.com/sysprog21/lab0-c/commit/2bcccee04b3a8f94b4bc63c16ffefa28a3af51c5)) #### 功能刪除 `head` 所指向的鏈結串列中重複的節點，假設此鏈結串列已排序。 #### 參數 - `struct list_head *head`：指向佇列起始節點的指標 #### 回傳值 `bool`： - 成功刪除節點則回傳 true - 若 `head` 為 NULL 或空鏈結串列，回傳 false #### 實作在這個實作中，我使用了一個整數變數 `dup_flag` 來標記節點是否為重複。若 `dup_flag` 為 0，代表該節點是第一次出現，否則為重複節點，需要將其刪除。為了保證在移除節點時仍能正確遍歷整個鏈結串列，我使用了 list_for_each_entry_safe 巨集。這個巨集可以在遍歷過程中修改鏈結串列，確保節點不會因為移除而導致遍歷錯誤。在遍歷過程中，我將第一個節點保存在 `first_appear` 變數中，然後逐一與後續節點（`entry`）進行比較。如果 `first_appear` 和 `entry` 的內容相同，則表示 `entry` 為重複節點，應該將其移除。若兩個節點的內容不同，則更新 `first_appear` 為當前節點。不過，這樣的實作無法正確處理最後一個節點的情況，因為在 list_for_each_entry_safe 巨集中並不會處理最後一個節點。因此，需要額外檢查最後一個節點是否為重複節點，並根據需要進行刪除。 #### 待修正 - 目前的實作中，為了避免將首節點當作特例，`first_appear` 被初始化為 NULL。在進行比較之前，需要檢查 `first_appear` 是否為 NULL。但這樣的邏輯有些混亂，並且包含許多判斷式，應該能進一步簡化。 ```c if (first_appear && strcmp(first_appear->value, entry->value) == 0) { // duplicated // ... } else { // ... } ``` - 目前的實作需要特別處理最後一個節點，但我認為應該有更簡便的方法來避免這樣的特殊處理，應該進一步思考並找出更優的解法。 ### q_swap > commit [a7fb6da](https://github.com/sysprog21/lab0-c/commit/a7fb6daeed7fb980499111a28572fa1e1eb4853b) #### 功能將 `head` 所指向的鏈結串列的**節點兩兩交換**。 #### 參數 - `struct list_head *head`：指向佇列起始節點的指標 #### 回傳值此函式不回傳任何值（`void`） #### 實作這個函式是 `q_reverseK` 在 $k=2$ 的特例，直接呼叫 `q_reverseK(head,2)` ### q_reverse > commit [ceb06a2](https://github.com/sysprog21/lab0-c/commit/ceb06a2d3037b9c1f1d2b3baf618f1b93dbf674a) #### 功能 **反轉** `head` 所指向的鏈結串列。 #### 參數 - `struct list_head *head`：指向佇列起始節點的指標 #### 回傳值此函式不回傳任何值（`void`） #### 實作 1. 使用 list_for_each_safe 迭代遍歷鏈結串列 - list.h 提供的 list_for_each_safe 巨集允許在迭代過程中修改鏈結串列，確保不影響後續的遍歷。 - 這對於反轉鏈結串列特別重要，因為我們需要調整每個節點的指向。 2. 交換每個節點的 `next` 和 `prev` 指標 - 透過遍歷鏈結串列，逐一交換每個節點的 `next` 和 `prev`，達成反轉的效果。 3. 處理 head 的特殊情況 - 由於 list_for_each_safe 不會修改首節點（head），因此在遍歷結束後，需額外調整 head 的 next 和 prev 以確保正確性。 #### 待修正 - ~~若 `head` 為 NULL，直接存取其成員（如 `head->next` 或 `head->prev`）將導致 segmentation fault，需在函式開頭加入 NULL 檢查以避免錯誤。~~ 已修正 commit [0fcea66](https://github.com/sysprog21/lab0-c/commit/0fcea6622b066e7c06865d43f2d36d0f6c5626f6) ### q_reverseK > commit [a7fb6da](https://github.com/sysprog21/lab0-c/commit/a7fb6daeed7fb980499111a28572fa1e1eb4853b) #### 功能將 `head` 所指向的列節串列分成多個長度為 $k$ 的子串列，並**反轉每個子串列**。 #### 參數 - `struct list_head *head`：指向佇列起始節點的指標 - `int k`：每個子串列的長度 #### 回傳值此函式不回傳任何值（`void`） #### 實作在學習快慢指標時，我的第一個想法是，若能調整快慢指標的走速，應該能找到不同的切割點，而不僅限於 1/2。這個想法啟發了此功能的實作。我讓快指標每次前進 $k$ 步，慢指標每次前進一步，這樣就能定位出長度為 $k$ 的子串列。接著，我使用 q_reverse 反轉每個子串列。主回圈 `while(1)` 會持續切出長度為 $k$ 的子串列，並將其反轉。以下程式碼用來定位子串列的起始與結尾位置，其中 fast 初始值設為 head： ```c slow = fast->next; for (int i = 0; i < k; ++i) { fast = fast->next; if (fast == head) { end = 1; break; } } ``` 接著，為了將反轉後的子串列接回原位置，我需要儲存子串列前後的位置。這是通過 `before` 和 `after` 來完成的。然後，我更新指標 `fast` 和 `slow` 來確保子串列變為環狀串列，接著用 q_reverse 反轉子串列： ```c struct list_head *before, *after; before = slow->prev; after = fast->next; slow->prev = fast; fast->next = slow; q_reverse(slow); ``` 最後，我將子串列接回原位置，並更新快慢指標，以繼續處理下一個子串列。 #### 待修正 - ~~若 `head` 為 NULL，直接存取其成員（如 `head->next` 或 `head->prev`）將導致 segmentation fault，需在函式開頭加入 NULL 檢查以避免錯誤。~~ 已修正 commit [0fcea66](https://github.com/sysprog21/lab0-c/commit/0fcea6622b066e7c06865d43f2d36d0f6c5626f6) ### q_sort ### q_ascend / q_descend > commit [e481d50](https://github.com/sysprog21/lab0-c/commit/e481d5052441edb716f9b0b83deaaa7d73d8946d) #### 功能使 `head` 指向的鏈結串列為**單調遞增**或**單調遞減**，並刪除不符合規定的節點。 #### 參數 - `struct list_head *head`：指向首節點的指標 #### 回傳值 `int` 修改後的鏈結串列大小 #### 實作此實作參考了 [Leetcode Problem: Remove Nodes from Linked List - solution](https://leetcode.com/problems/remove-nodes-from-linked-list/editorial/)該方法透過將節點逐一加入堆疊（stack），並在加入時維護堆疊的遞增性或遞減性來實現。以下以遞增（ascend）為例： 1. 透過 list_for_each_entry_safe 巨集逐一走訪鏈結串列元素 `entry`，並將其加入堆疊。 2. 在加入元素時，會將當前要加入的元素 `entry` 和堆疊頂端的元素比較。如果 `entry` 較小，則移除堆疊頂端的元素，重複此過程直到 `entry` 大於堆疊頂端元素，或堆疊為空。這樣可保證堆疊保持遞增順序。以下程式碼展示了如何將 `entry` 加入堆疊： ```c while (stack_head != head && strcmp(list_entry(stack_head, element_t, list)->value, entry->value) > 0) { struct list_head *cur = stack_head; stack_head = cur->prev; stack_head->next = NULL; q_release_element(list_entry(cur, element_t, list)); } ``` 由於我使用原始串列的首節點作為堆疊的起始點，因此當 `stack_head != head` 時，堆疊仍為非空。 3. 在處理堆疊時，保證串列的雙向性，最後將串列的頭尾相接形成環狀串列。完成後，使用 q_size 計算新串列的大小並回傳。這樣的做法能夠高效且安全地完成串列的遞增或遞減處理。 ### q_merge > commit [412afd0](https://github.com/sysprog21/lab0-c/commit/412afd0d18d6a23333c587d0e710ed30e60a2522), [22b8ea5](https://github.com/sysprog21/lab0-c/commit/22b8ea5c692d5034db48c163dae9a5b206bf94b4), [24c1c33](https://github.com/sysprog21/lab0-c/commit/24c1c3306799c50077429829e692119d56338615) #### 功能將 `head` 所指向的**佇列串列（chain）**合併至第一個佇列。 #### 參數 - `struct list_head *head`：指向一個佇列串列的開頭，除了 `head` 之外，每個節點都連接著一個已排序的佇列。 - `bool descend`：若為降序排列則值為 true，否則為 false。 #### 回傳值 `int`：合併後佇列的大小 #### 複雜度分析以**降序排序**為例，假設共有 $k$ 個佇列，第 $i$ 個佇列的大小為 $n_i$，其中 $i=0,1,\dots,k-1$。定義最大佇列大小 $N = \max(n_i)$，並考慮最壞情況：假設所有佇列大小皆為 $N$。即便某些佇列大小極端，例如 $n_i \gg n_j,\ \forall j \neq i$，由於鏈結串列的特性，這不會影響合併過程的複雜度，因為**所有方法的時間複雜度皆與 $N$ 成正比。** 最直覺的實作方式是： 1. 每次掃描所有佇列，找到當前的最大值，插入新佇列。 2. 重複此過程，直到所有佇列被清空。但這種方法每次掃描需要 $O(k)$，且總共操作 $O(kN)$ 次，因此時間複雜度為： $$ O(k^2N) $$ 這顯然不夠高效。因此，我採用了分治（Divide & Conquer）的方式，類似於合併排序（Merge Sort），讓佇列兩兩合併，並重複這個過程： - 第 1 次合併：$k/2$ 次，每次處理 $2N$ 個節點 - 第 2 次合併：$k/4$ 次，每次處理 $4N$ 個節點 - 第 3 次合併：$k/8$ 次，每次處理 $8N$ 個節點 - … - 最後一次合併：$1$ 次，處理 $kN$ 個節點總共需要 $\log_2 k$ 次合併，因此最終時間複雜度為： $$ O(Nk\log k) $$ 這是一個較優的解法，適用於大規模佇列合併。 #### 初始實作 commit [412afd0](https://github.com/sysprog21/lab0-c/commit/412afd0d18d6a23333c587d0e710ed30e60a2522) 1. **計算 $k$ 值（佇列個數）** - 由於我們的合併過程共需 $\log_2 k$ 次，因此可以透過位元運算來追蹤當前合併的次數： ```c int k = q_size(head); k--; while (k != 0) { k >>= 1; // ... } ``` 2. **遍歷佇列串列，逐一合併** - 使用 list_for_each_entry 走訪整個 head，找到兩個尚未合併的佇列，將它們合併至第一個佇列，並將第二個佇列標記為空： ```c list_for_each_entry (entry, head, chain) { if (!qctx1 && entry->q) { qctx1 = entry; continue; } if (!entry->q) continue; qctx2 = entry; /* merge */ // ... } ``` - 在第一次迴圈結束後，所有索引為奇數的佇列都會被合併至它前面的佇列（索引以 0 為起點）。 3. **合併排序好的佇列** - 由於所有佇列本身已排序，合併時只需比較兩個佇列的首節點大小，即可有效地合併： 4. **完成合併，回傳佇列大小** - 當 $k=0$ 時，代表所有佇列已完成合併，最後使用 q_size 取得最終佇列大小並回傳這個方法能正確合併多個佇列，但在測試時發現存在記憶體洩漏。問題出在合併後將佇列的首節點設為 NULL，然而這些節點是透過 malloc 分配的，未正確釋放將導致記憶體無法回收。 #### 修改方案 commit [22b8ea5](https://github.com/sysprog21/lab0-c/commit/22b8ea5c692d5034db48c163dae9a5b206bf94b4), [24c1c33](https://github.com/sysprog21/lab0-c/commit/24c1c3306799c50077429829e692119d56338615) 原先的合併策略在合併後會將佇列的首節點設為 NULL，但這樣會導致記憶體洩漏（memory leak）。在 commit 22b8ea5 中，這個問題被修正，改為將合併後的佇列初始化為空佇列（INIT_LIST_HEAD），這樣能確保記憶體正確釋放。此外，尋找待合併佇列的方式也從「尋找非 NULL 佇列」改為「尋找非空佇列」，以確保合併時的正確性。 **相關程式碼變更：** ```git diff --git a/queue.c b/queue.c index cad6631..a155257 100644 --- a/queue.c +++ b/queue.c @@ -408,11 +408,11 @@ int q_merge(struct list_head *head, bool descend) k >>= 1; queue_contex_t *entry = NULL, *qctx1 = NULL, *qctx2 = NULL; list_for_each_entry (entry, head, chain) { - if (!qctx1 && entry->q) { + if (!qctx1 && !list_empty(entry->q)) { qctx1 = entry; continue; } - if (!entry->q) + if (list_empty(entry->q)) continue; qctx2 = entry; @@ -458,7 +458,7 @@ int q_merge(struct list_head *head, bool descend) /* after merge */ qctx1->size += qctx2->size; qctx2->size = 0; - qctx2->q = NULL; + INIT_LIST_HEAD(qctx2->q); qctx1 = qctx2 = NULL; } } ``` 這個修改讓程式通過了 valgrind 的測試，但隨之也引入了一個額外問題：若第一個佇列為空佇列，則合併結果不會存入第一個佇列，而是存入第一個非空佇列，導致後續刪除佇列時清除所有資料。這是因為合併的流程如下： 1. 呼叫 q_merge，將合併後的佇列存入第一個佇列。 2. 刪除除第一個佇列外的所有佇列。如果第一個佇列一開始是空的，那麼 q_merge 會將結果存入另一個佇列，而刪除時會將其釋放，導致資料遺失。 Commit 24c1c33 修正了這個問題： 1. 計算非空佇列的數量 $k'$，並用 $k'$ 取代 $k$。若 $k'$ 為 $0$，則無須合併，直接回傳 $0$。 2. 若第一個佇列為空，則尋找第一個非空佇列，並將其搬移至第一個佇列。 **關鍵程式碼變更：** ``` queue_contex_t *qct1, *qct2; qct1 = list_entry(head->next, queue_contex_t, chain); if (list_empty(qct1->q)) { list_for_each_entry (qct2, head, chain) if (!list_empty(qct2->q)) break; // move qct2 to qct1 // ... } ``` 這項修正後，合併邏輯變得更加嚴謹，但仍有改量空間。目前，將 $k$ 改為 $k’$ 對降低時間複雜度影響不大，僅從 $O(Nk log k)$ 降至 $O(Nk log k’)$。若能在合併前先將空佇列暫時移除，則可將複雜度進一步降低為 $O(Nk’ log k’)$，在空佇列數量較多的情況下能大幅提升效能。不過，目前尚未確認改變佇列串列順序是否會導致不可預期的影響，因此尚未進一步實作這個調整。如果確認能安全變更順序，則合併流程可進一步簡化，使程式碼更精簡高效。 ## Dude, is my code constant time?研讀 & dudect 分析 ### 相關理論分析論文本文中提到 > We first measure the execution time for two different input data classes, and then check whether the two timing distributions are statistically different. 意即是他會執行兩組不同的測試，並且用統計方法分析這兩組機率分布 **「是否足夠相似？」** 搭配 Welch's t-test 的公式會更清楚 $$ t=\frac{\Delta\bar X}{s_{\Delta\bar X}}=\frac{\bar X_0-\bar X_1}{\sqrt{\frac{s_1^2}{N_1}+\frac{s_0^2}{N_0}}} $$ 其中下標 $0,1$ 分別代表兩組不同的實驗，$\bar X_i$ 為平均值，$s_i$ 為樣本標準差。分子是兩者平均的差異，分母是各自標準差的方均根。我沒有去深究這個模型是否是用在這個系統，但不難看出 $t$ 值某種程度上反映兩組實驗的差異。標準差代表分佈的「寬度」，平均值代表分佈的「位置」，$t$ 值反應了兩者的重疊程度。如下示意圖，上半部的兩個分佈的重疊較少，$t$ 值會比較大，而下半部兩個分佈的重疊較多 $t$ 值較小。註：寬度是一個和標準差相關的值，圖中的標準差只是示意，並不代表真實寬度就是標準差。 ![IMG_CFCC5AB25976-1](https://hackmd.io/_uploads/ry0GYSoo1g.jpg) ### deduct 相關程式碼分析跟著作業要求的 [lab0(D)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#-%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89%E9%87%8D%E9%BB%9E%E6%8F%90%E7%A4%BA) 的提示找到 `is_insert_tail_constant`，發現他呼叫了函式 `doit(0)` 負責實驗主流程。分析 `doit` 1. `prepare_inputs()` 會產生隨機的 `input_data` 和 `classes`。 - `input_data`：這個值決定了該次實驗的佇列長度，若為實驗 0，會在這邊被設為 0。 - `classes`：該次實驗要進行哪一種實驗。其中，實驗 0 為在長度為 0 的佇列插入節點，而實驗 1 則會在隨機長度的佇列插入節點。也就是說，每次進行哪種實驗也是隨機的。 2. `measure()` 會量測實驗時間，這邊可以看到很多前綴為 dut 的函式，不難猜出他們會做同樣的功能多次。以`dut_insert_head` 舉例。定義如下： ```c #define dut_insert_head(s, n) \ do { \ int j = n; \ while (j--) \ q_insert_head(l, s); \ } while (0) ``` 他會在佇列中插入 n 個字串為 s 的節點。至此實驗就準備好了，接下來用 `cpucycles()` 記錄當前的 cpu cycle。 3. 最後只要處理資料就可以計算出 $t$ 值。 ### 參考資料 - https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#-%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89%E9%87%8D%E9%BB%9E%E6%8F%90%E7%A4%BA - [〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.