2025q1 Homework1 (lab0)

contributed by <allen741>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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

$ lscpu
Architecture:              x86_64
CPU Operating Modes:       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) i5-1135G7 @ 2.40GHz
CPU Family:           6
Model:                140
Threads per core:     2
Cores per socket:     4
Socket(s):            1
Process:              1
CPU(s) scaling MHz:   23%
CPU max MHz:          4200.0000
CPU min MHz:          400.0000
BogoMIPS:             4838.40
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:                      8 MiB (1 instance)
NUMA:
  NUMA nodes:             1
  NUMA node0 CPU(s):      0-7

實作 queue.c

`q_new`

  struct list_head *queue = malloc(sizeof(struct list_head));

  if (!queue) {
      return NULL;
  }

  INIT_LIST_HEAD(queue);

利用malloc()分配記憶體並使用list.h中的INIT_LIST_HEAD()初始化 head 中的指標 next 和 prev

`q_free`

commit a0f1662

利用list.h的巨集list_for_each_safe遍歷雙向鏈結串列並釋放元素，因為 element_t 中的成員 value 為字元指標，所以需要另外釋放它所指向的字元

`q_insert_head`

    element_t *new_element = malloc(sizeof(element_t));

    if (!new_element) {
        return false;
    }

    new_element->value = strdup(s);
    if (!new_element->value) {
        free(new_element);
        return false;
    }

    list_add(&(new_element->list), head);
    /* cppcheck-suppress memleak */

利用malloc()分配記憶體後使用 C 語言內建函式strdup()將字元複製到所分配的記憶體空間，使用list.h的函式list_add()加入元素並使用註解cppcheck-suppress memleak使程式通過靜態分析

`q_insert_tail`

return q_insert_head(head->prev, s);

利用q_insert_head實作函式

`q_remove_head`

Commit db4538e

利用list.h的函式list_del()刪除雙向鏈結串列的第一個元素使其無法透過雙向鏈結串列存取，並使用 C 語言內建函式strncpy()複製 bufsize-1 個字元到sp並在最後加入空字元\0代表字元結尾

`q_size`

Commit 9a4588b

利用list.h的巨集list_for_each計算雙向鏈結串列的元素數量

`q_delete_mid`

Commit 9d86eea

利用快慢指標找到串列的中間元素並釋放其記憶體

`q_delete_dup`

Commit 6c1b975

原先沒有仔細思考函式需要實作的功能，以為是刪除鄰近元素中含有相同字元的元素，經過make test測試後才發現問題所在並改成利用兩層迴圈檢查是否有重複的字元，其中使用 C 語言內建函式strcmp()比較字元指標所指到的字元是否相同，若相同則會回傳 0。針對回傳 0 的情況將串列中較後面的元素刪除。
之後由於make test的第六項測試trace-06-ops顯示 ERROR: Duplicate strings are in queue or distinct strings are not in queue，回去重新看題目發現有相同字元的元素並非留下一個，而是一個也不留全部刪除因此新增 commit 刪除第一個重複的元素

`q_swap`

    struct list_head *first, *second;
    for (first = head->next, second = first->next;
         first != head && second != head;
         first = first->next, second = first->next) {
        list_move(first, second);
    }

利用兩個指標 first 和 second 指向要交換的元素，並使用list.h的函式list_move()讓 first 所指向的元素插入到 second 所指向的元素後面達成元素兩兩互相交換，直到 first 或 second 指向 head 才停止繼續交換

`q_reverse`

Commit 0314fac

從串列的第二個元素開始將元素利用list.h的函式list_move()依序插入到 head 的後面完成串列反轉

`q_reverseK`

    for (struct list_head *group_first = head;;) {
        struct list_head *group_last = group_first;
        int check = 0;
        for (int i = 0; i < k; i++) {
            group_last = group_last->next;
            if (group_last == head) {
                check = 1;
                break;
            }
        }
        if (check == 1) {
            break;
        }
        struct list_head *tmp_next = group_last->next;
        struct list_head *tmp_prev = group_first->prev;
        group_last->next = group_first;
        group_first->prev = group_last;

        q_reverse(group_first);

        tmp_next->prev = group_first->prev;
        group_first->prev->next = tmp_next;
        struct list_head *tmp = group_first->prev;
        group_first->prev = tmp_prev;
        group_first = tmp;
    }

利用迴圈找到要反轉的串列開頭group_first(作為串列開頭因此之後不會被反轉)和結尾group_last，透過之前實做的函式q_reverse進行反轉，之後將group_first更新為反轉串列的最後一個元素用來作為下次反轉的開頭

`q_sort`

Commit f0226e0

仔細閱讀 linux 中的 list_sort.c 和 Linux 核心的鏈結串列排序按照 Linus Torvalds 的方法實作雙向鏈結串列排序，將 list_sort.c 的函式merge()利用巨集merge_two_list()代替，並將 list_sort.c 的函式merge_final()的功能直接寫在q_sort()中以減少參數傳遞

`q_ascend`

Commit 12d47ed

原先以為是將較前面元素小的元素刪除以確保之後的元素所儲存的字元大小會大於或等於前面的元素，但經過make test測試無法通過後重新閱讀Remove Nodes From Linked List才了解是若遇到後面元素小於前面的元素時要刪除前面的元素而非刪除後面的元素，因此我利用兩層迴圈檢查前面的元素所儲存的字元是否皆小於或等於後面的元素所儲存的字元，一旦發現有大於前面元素的元素則刪除前面的元素，並結束第二層迴圈

`q_merge`

    struct list_head *first_queue =
        list_entry(head->next, queue_contex_t, chain)->q;

    struct list_head *queue_ptr = head->next->next;
    while (queue_ptr != head) {
        struct list_head *queue =
            list_entry(queue_ptr, queue_contex_t, chain)->q;

        list_splice_init(queue, first_queue);
        list_entry(queue_ptr, queue_contex_t, chain)->size = 0;
        queue_ptr = queue_ptr->next;
    }
    q_sort(first_queue, descend);
    list_entry(first_queue, queue_contex_t, chain)->size = q_size(first_queue);
    return list_entry(first_queue, queue_contex_t, chain)->size;

將第一個串列之後的所有串列利用list.h的函式list_splice_init()依序插入到第一個串列的開頭之後，並將欲插入串列的size設為 0，最後利用上述實做的函式 q_sort()一次排序所有元素

閱讀 Dudect

Dudect 的主要目標是檢測函式是否能在常數時間執行完成，分成以下三個步驟檢測

1. 測量執行時間

a. 定義輸入數據類別

固定輸入: 測試資料設定為常數
隨機輸入: 每次測試時隨機產生測試資料

b. 測量執行時間

使用 CPU 週期計數器或外部計時設備

c. 減少測試環境影響

減少作業系統干擾
隨機分配測試時的輸入數據類別以減少測試偏差

2. 處理測量數據

計算百分位數

針對測試到的執行時間進行排序後，計算百分位數並將執行時間小於百分位數的數據納入統計分析

高階處理

使用 Centered Product 技術來強化統計檢測

3. 統計分析

Welch’s t-test

測試固定輸入和隨機輸入的執行時間的平均值是否相同，如果差異很大代表函式可能無法在常數時間執行完成

Kolmogorov-Smirnov Test

實作 Dudect percentile

觀察 Dudect 原始碼

主函式

dudect_state_t dudect_main(dudect_ctx_t *ctx) {
    prepare_inputs(ctx->config, ctx->input_data, ctx->classes);
    measure(ctx);

    bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;

    dudect_state_t ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
    if (first_time) {
      // throw away the first batch of measurements.
      // this helps warming things up.
      prepare_percentiles(ctx);
    } else {
      update_statistics(ctx);
      ret = report(ctx);
    }

    return ret;
}

對比老師實作的主函式可以發現在測量完執行時間後Dudect會透過prepare_percentiles(ctx) 進行快速排序並計算0~100的百分位數，之後透過update_statistics(ctx)針對不同數據結果進行統計分析，但在作業的fixture.c測量完執行時間後直接進行統計分析導致執行時間過長的數據大幅地影響結果，因此需實作prepare_percentiles(ctx) 使執行時間較短的數據能突顯在 t-test 的結果上

實作 prepare_percentiles

static void prepare_percentiles(int64_t *exec_times, int64_t *percentiles)
{
  qsort(exec_times, N_MEASURES, sizeof(int64_t),
        (int (*)(const void *, const void *)) cmp);
  for (size_t i = 0; i < 100; i++) {
      percentiles[i] =
          percentile(exec_times, 1 - (pow(0.5, 10 * (double) (i + 1) / 100)),
                     N_MEASURES);
  }
}

改善 update_statistics

-    for (size_t i = 0; i < N_MEASURES; i++) {
+    for (size_t i = 5; i < N_MEASURES; i++) {

因為執行時間受硬體和作業系統影響，因此Dudect在函式update_statistics(ctx)刻意丟棄前10次所計算的執行時間減少影響，因此我也將作業的update_statistics()函式丟棄前五次測試數據

+    // t-test on the execution time
+        for (size_t crop_index = 0; crop_index < 100; crop_index++) {
+            if (difference < percentiles[crop_index]) {
+                t_push(t, difference, classes[i]);
+            }
+        }

加入 percentiles 的計算結果使執行時間較短的數據能突顯在 t-test 的結果上

實作 q_shuffle 並探究亂度

利用 Fisher–Yates shuffle 演算法實作 q_shuffle 函式並利用 lab0 提供的 python 測試檔對鏈結串列1-2-3-4進行1百萬次的 shuffle，經過大約十五分鐘的執行後得到以下統計結果

	觀察到的頻率	期待的頻率		觀察到的頻率	期待的頻率
1 2 3 4	41666	41666	3 1 2 4	41958	41666
1 2 4 3	41822	41666	3 1 4 2	41727	41666
1 3 2 4	41676	41666	3 2 1 4	42091	41666
1 3 4 2	41814	41666	3 2 4 1	41691	41666
1 4 2 3	41723	41666	3 4 1 2	41964	41666
1 4 3 2	41540	41666	3 4 2 1	41534	41666
2 1 3 4	41472	41666	4 1 2 3	41320	41666
2 1 4 3	41868	41666	4 1 3 2	41377	41666
2 3 1 4	41557	41666	4 2 1 3	41563	41666
2 3 4 1	41387	41666	4 2 3 1	41812	41666
2 4 1 3	41468	41666	4 3 1 2	41692	41666
2 4 3 1	41672	41666	4 3 2 1	41606	41666

chi square sum:  21.330773292372676

對照卡方圖在自由度為23的清況下，得到 P value 在 0.1 ~ 0.9之間，大於預設常見的 P value = 0.05，因此我們可以說統計結果不拒絕虛無假說（

H_{0}

），代表目前的測試樣本不足以證明 shuffle 的結果不是均勻分布的，可能是測試次數不夠所以無法證明 shuffle 函式不是均勻分佈，或是 shuffle 函式真的為均勻分佈。從上方長條圖可以看出24項數據彼此差異不大，的確接近常態分佈

亂數

執行 option entropy 1 並搭配 ih RAND 10 得到以下結果

l = [txrinv(29.69%) nxcgyxn(26.56%) elgohm(29.69%) quxfbv(29.69%) zrsfhgzew(35.94%) plxctcly(29.69%) ecwqnxqp(32.81%) fxdyxd(21.88%) qetpub(29.69%) ppttjvdt(25.00%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%)]

利用以下公式可以計算亂度

S = - \sum_{i = 1}^{n} P (x_{i}) l o g_{b} P (x_{i})

以第一個字串txrinv計算亂度

	$P (x_{i})$	$l o g_{2} P (x_{i})$	$- P (x_{i}) l o g_{2} P (x_{i})$
t	0.167	-2.585	0.432
x	0.167	-2.585	0.432
r	0.167	-2.585	0.432
i	0.167	-2.585	0.432
n	0.167	-2.585	0.432
v	0.167	-2.585	0.432

將得到的

- P (x_{i}) l o g_{2} P (x_{i})

全部相加後得到 S 約為2.59017，按照 shannon_entropy.c 最後所進行的正規化得到以下結果

S = \frac{2.59017}{8} \times 100 % = 32.377 %

2025q1 Homework1 (lab0)

開發環境

實作 queue.c

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend

q_merge