2018q1 Homework3 (list)

contributed by < chasingfar >

自我檢查事項

生日悖論

如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式

$1-{\displaystyle \frac{1}{e^{\frac{n^2}{2N}}}}$

Birthday problem 對資訊安全的影響在哪些層面？

N 位長度的 hash table 可能發生碰撞測試次數不是

$2^N$次而是只有

$2^{\frac{N}{2}}$次

像是 Random Number Generator 這樣的產生器，是否能產生「夠亂」的亂數呢？

此網站並未提供亂數產生器算法，所以很難從數學角度解釋。
簡單的統計一下前1000個0~9的出現次數(seed=0)

可看出極不均勻，不知是不是樣本過少的關係，但它上限就是1000個。

在實務中需要真亂數時可以考慮random.org提供的服務，
若有可控的偽亂數需求可以考慮 c++11 提供的 <random> 函數庫，或者 intel 提供的 MKL 函數庫。

Linux 風格的 linked list

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

function call 需要對 stack push 及 pop 最少也需要 jmp 與 ret ，會對 stack 造成負擔以及產生多餘的指令。
用 macro 來實作的話就不會有多餘的指令及額外的 stack 消耗，但會有編譯後程式體積增加及難以維護的缺點

Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？

解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？

LIST_POISONING 這樣的設計有何意義？

linked list 採用環狀是基於哪些考量？

list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？

for_each 風格的開發方式對程式開發者的影響為何？

程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？

tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？

tests/ 目錄的 unit test 可如何持續精進和改善呢？

針對 linked list 的排序演算法

對 linked list 進行排序的應用場合為何？

考慮到 linked list 在某些場合幾乎都是幾乎排序完成，這樣貿然套用 quick sort 會有什麼問題？如何確保在平均和最差的時間複雜度呢？

能否找出 Linux 核心原始程式碼裡頭，對 linked list 排序的案例？

透過 skiplist 這樣的變形，能否加速排序？

研讀 How to find the kth largest element in an unsorted array of length n in O(n)?，比照上方連結，是否能設計出針對 linked list 有效找出第 k 大 (或小) 元素的演算法？

linux-list 裡頭 examples 裡頭有兩種排序實作 （insertion 和 quick sort)，請簡述其原理

實作 merge sort