執行人: LeoriumDev
jserv
LeoriumDev/lab0-c 應該要 rebase 到最新的 lab0-c,留意 git 的操作
好的 Leorium
使用 rebase,而非 git merge,注意二者的差別
已更正 Leorium
依據第一份作業指示,重新投入,並強化對於亂數、排序演算法和改進 (特別留意 cache 的影響)、常數時間判定的理論和實務、統計手法、網頁伺服器,以及程式碼品質的議題。
Fisher–Yates shuffle 是一種用來打亂有限序列的演算法。
其 (最初的) 演算法運作原理如下 (以打亂一串數字為例):
之後有為電腦改進的演算法為 Algorithm P (Shuffling)。
提供更多細節和參照第一手材料
在教材當中有描述另一種實作方式:
q_size
取得 queue 的大小 len
。random
,然後 old
將指向從前面數來第 random 個節點,new
會指向最後一個未被抽到的節點,將 old
和 new
指向的節點的值交換,再將 len - 1。shuffle
依據課程教材,C preprocessor 翻譯為「前置處理器」。
#
和 ##
二者皆「不是」運算子,翻閱 C 語言規格書。
留意細節!
在 C99 - 6.10.3.1 Argument substitution 有提到
#
及##
被稱為 “preprocessing token”
在 console.h 中定義的 ADD_COMMAND 巨集,利用 C 的前置處理器符號 (preprocessing token) #
和 ##
,提供了一個簡潔且一致的方式來新增命令。它讓每個命令都對應到自己的名稱字串及提供功能的函式指標。
例如,若要新增 shuffle 命令,只需使用:
這會展開為:
接下來要實作 do_shuffle
函式,其中將 Fisher–Yates shuffle 的實作寫成獨立的 q_shuffle
函式。
q_shuffle
函式實作:
shuffle
的亂度為確保 shuffle
的結果發生的機率相同,也就是其遵守 Uniform distribution,可以利用 Pearson's chi-squared test 來檢驗虛無假說 (Null hypothesis)。
參考教材說明:
如果要 shuffle 三個不同的數字,會出現六種可能的結果,彼此是互斥的,且發生機率加起來為 1。那假設 shuffle 是公平的(六種結果發生的機率相同),並遵守 Uniform distribution,那虛無假說為:
利用教材當中測試程式跑出的結果 (大約跑了半小時):
What is random?
How to measure the randomness?
這篇論文在介紹一項工具 dudect,這項工具能夠透過統計分析,評估一段程式碼的執行時間是否為 constant time ,這項工具的特點是,dudect 是透過 timing leakeage detection tests 對執行時間的統計分析,沒有底層硬體的限制,不限於特定 CPU。
參考 willwillhi1 同學的說明,實作可分為以下步驟:
Classes definition
: 給定兩種不同類別的輸入資料,重複對方法進行測量,最常見的就是 fix-vs-random testsCycle counters
: 現今的 CPU 提供的 cycle counters 可以很精準的獲得執行的時間。Environmental conditions
: 為了減少環境的差異,每次測量都會對應隨機的輸入類別。Cropping
: 剪裁掉一些超過 threshold 的測量結果Higher-order preprocessing
: Depending on the statistical test applied, it may be beneficial to apply some higherorder pre-processingt-test
: Welch’s t-test,測試兩個平均數是否相同Non-parametric tests
:(無母數統計分析): Kolmogorov-Smirnovselect()
select(2) — Linux manual page
select() allows a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2), or a sufficiently small write(2)) without blocking.
不要只是張貼素材,而該解讀和討論
根據 manpage,select()
能讓程式監控多個 file descriptor 的,會等待其中一個或多個 file descriptor 直到就緒 (ready),而判斷「就緒」的條件是能否執行相對應的 I/O 操作而不會發生 blocking 的情況。
sidenote:
select()
僅能監控 number 低於 FD_SETSIZE (1024) 的 file descriptor,可用poll()
或epoll()
取而代之。
而 file descriptor 是一個底層 (low level) 且原始 (primitive) 的一種用來與 file I/O 溝通的介面 (interface),本身是 integer。值得注意的是,如果要在 nonblocking 的情況下必須使用 file descriptor 而非 file stream。
select()
的定義:
fd_set
是一個 file descriptor 的集合的結構體。timeval
結構體,其成員用來描述 select()
函式等待 file descriptor 就緒時,最多阻塞(blocking)多久。如果 timeout 這個參數設為 NULL
,則代表 select()
會無限期地 (indefinitely) 等。blocking 結束的情況有:
紀錄你從其他學員成果獲得的啟發,應適度重現實驗並詳實標注