2024q1 Homework1 (lab0)

contributed by < godhand4826 >

專案網址

開發環境

使用 MacBook Air 2022 並使用 docker 作為開發環境，下面是我所使用的Dockerfile

FROM ubuntu:20.04

RUN apt-get update && DEBIAN_FRONTEND=noninteractive apt-get install -y build-essential git clang-format cppcheck aspell colordiff valgrind vim

RUN groupadd -g 10001 ubuntu && useradd -m -u 10000 -g ubuntu ubuntu
WORKDIR /home/ubuntu

RUN echo '\
set encoding=utf-8\n\
\n\
function! FormatOnSave()\n\
  let l:save_cursor = getpos(".")\n\
  execute "%!clang-format"\n\
  call setpos(".", save_cursor)\n\
endfunction\n\
\n\
autocmd BufWritePre *.h,*.hpp,*.c,*.cc,*.cpp call FormatOnSave()\n' > .vimrc

COPY . lab0-c
RUN chown -R ubuntu:ubuntu /home/ubuntu

WORKDIR /home/ubuntu/lab0-c

USER ubuntu:ubuntu

實作指定的佇列操作

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。

在實作基本的佇列操作時，使用了 list_entry 和 list.h 中提供的功能，使得 q_new, q_free, q_insert_head, q_insert_tail, q_remove_head, q_remove_tail, q_size 等操作變得簡單而有效。

目前只有你投入，用「我」自稱即可。

刪除中間節點: `q_delete_mid`

透過佇列的大小信息，能夠確定需要前進多少步，從而刪除指定位置的元素。

移除相鄰重複節點: `q_delete_dup`

從佇列的頭部開始，檢查相鄰兩個節點的值是否相同，若是，則整個刪除，然後繼續前進一步，重複執行直到結尾。

交換相鄰元素: `q_swap`

同樣從佇列的頭部開始，交換相鄰兩個節點的值（或指標），然後一次跳兩步，重複執行直到結尾。

反轉 Queue: `q_reverse`

透過交換每個節點（包括頭部）的 prev 和 next 指標，實現整個佇列的反轉。

每 k 個反轉: `q_reverseK`

從佇列的頭部開始，前進 K 步，利用 list_cut_position 將前 K 個元素剪下，如果拿滿 K 個就反轉剪下來的鏈結串列，最後再將反轉或未變動的部分加入結果的鏈結串列中，最後用結果的鏈結串列取代原本佇列中的鏈結串列。

排序: `q_sort`

在這裡，我採用 Merge Sort 算法進行佇列的排序。實現了 list_mergesort 和 list_merge 兩個功能，其中 list_mergesort 負責將鏈結串列分割成兩半並分別排序（遞迴呼叫自身），而 list_merge 則用於合併兩個已排序的鏈結串列。函式宣告如下

void list_merge(struct list_head *head_a, struct list_head *head_b, bool descend)
void list_mergesort(struct list_head *head, int size, bool descend)
void q_sort(struct list_head *head, bool descend)

升序排列: `q_ascend`

若下一個節點的值比當前小，則將自身刪除，一直處理到結尾，實現升序排列。

降序排列: `q_descend`

若前一個節點的值比當前大，則將自身刪除，一直處理到結尾，實現降序排列。

合併多個佇列: `q_merge`

由於在實作 q_sort 時已有 list_merge 可用，因此合併多個佇列變得簡單。只需將後續佇列的大小加到第一個佇列上，然後將所有佇列的鏈結串列依次合併到第一個佇列的鏈結串列中即可。

Github Action

在本地成功通過測試之後，推上 github 。但由於 github ci 使用的 runner 跑起來很慢，可以嘗試使用自己的電腦作為 runner。
Settings > Actions > Runners > New self-hosted runner，按照上面的指令操作就能快速的架設自己的 runner

Constant time

研讀指定的論文

指定論文 Dude, is my code constant time? 中 III.Result / A. Implementation / a)有提到 Pre-processing

a) Pre-processing: We pre-process measurements prior to statistical processing. We discard measurements that are larger than the p percentile, for various[2] values of p. The rationale here is to test a restricted distribution range, especially the lower cycle count tail. The upper tail may be more influenced by data-independent noise. This (heuristic) process gives good empirical results (makes detection faster); nevertheless we also process measurements without pre-processing.

而具體實作的方式在下方的備註也有附上連結

[2] The exact values for p follow an inverse exponential trend, see https://github.com/oreparaz/dudect/blob/master/src/fixture.c#L57 for the concrete specification.

雖然論文中連結已失效，但可以在最新版的 src/dudect.h 中找到相對應的實作。在 lab0-c 中的 dudect/fixture.c 加入相同邏輯的程式碼 (commit)，即可穩定的通過 O(1) 測試，且測試的執行時間也有明顯的下降。

2024q1 Homework1 (lab0)

專案網址

開發環境

實作指定的佇列操作

刪除中間節點: q_delete_mid

移除相鄰重複節點: q_delete_dup

交換相鄰元素: q_swap

反轉 Queue: q_reverse

每 k 個反轉: q_reverseK

排序: q_sort

升序排列: q_ascend

降序排列: q_descend

合併多個佇列: q_merge