# D05: list
###### tags: `sysprog2018`

:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2018 年系統軟體課程](https://www.facebook.com/groups/system.software2018/)
:mega: 返回「[作業系統設計與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表
:::

## 預期目標

* 嘗試研讀大型軟體專案
* 學習 Linux 核心原始程式碼的資料結構
* 資料封裝和 C 語言程式設計技巧
* 複習機率統計，及早脫離鄉民口中的「文組^TM^」
* 兼顧理論和實務

## 生日悖論

在街上你隨意找一人，兩人同一天生日的可能性有多大？

貌似很渺茫，直觀來說。考慮到閏年，一年共有 366 天，遇到同一天生日的機率為 `1/366`，或 `0.0027%`。但是如果把問題改為：在一個房間裡，至少有多少人，才能使其中兩個人的生日是同一天的可能性超過 50%？如果生日的分佈是隨機事件，在機率的推算，前述問題只要 23 個人在場，即可達到其中至少兩個人同一天生日，聽起來很怪吧？

這個有趣的數學現象被稱為生日悖論。這不是一個真正的邏輯悖論，因為它不是自相矛盾的，只是非常地不直觀。

先假設一年只有 365 天，每一天的生日機率相同。生日悖論會令人感到難以置信，因為人類傾向於從自己的角度看待問題。人們通常這樣想，如果一個房間裡加上自己共有 23 人，你會覺得在這 22 人裡頭跟你同一天生日的可能性太低了。365 天，現在卻只有 22 個人，你可能會想機率只有 `22/365`，所以很難在這 22 個人中遇上跟自己同一天生日。但這是錯的！ —— 只是站在你自己的角度來思考有誰與你生日是一樣的。

事實上，生日問題指的是在任何 23 個人中，兩人生日相同的機率是多少。而不是你進入了一個有著 22 個人的房間，房間裡有人會和你有相同生日的機率。我們需要挨個比較房間裡每個人之間的生日。

>$其實\ 22\ 個人中遇上和自己同一天生日的人的機率不是\ \dfrac{22}{365}\ 而是 \\
1 - 第一個人生日不同的機率\ \times\ 第二個人生日不同的機率\ \times\ ... \\
\begin{split}
&= 1 - \dfrac{364}{365} \times \dfrac{363}{365} \times \dfrac{362}{365} \times\ ... \\
&= 1 - \dfrac{P_{22}^{364}}{365^{22}}\\
&=50.73\%
\end{split}\\
已經有超過一半的可能了$
[name=ryanpatiency][color=green]

把第一個人與其他 22 個比較，把第二個人與 21 個人比較，第三個人與其它 20 個人比較......直到最後第二個人與最後一個人比較。將 23 個人之間的所有這些比較加起來，產生 22 + 21 + 20 ... + 1 = 23 × 22/2 = 253種不同的搭配，所以產生一對成功匹配的生日並非不可思議。

為了計算出生日相同的機率，我們可以先計算所有人生日都不同的機率。那麼，第一人生日是唯一的機率為 `365/365`，第二個人生日是唯一的機率則下降到 `364/365`，以此類推，第 23 個人生日是唯一的機率為 `343/365`。

然後，把所有 23 個獨立機率相乘，即可得到所有人生日都不相同的機率為：(365/365) × (364/365) × ... × (343/365) ，得出結果為 `0.491`。那麼，再用 1 減去 `0.497`，就可以得到 23 個人中有至少兩個人生日相同的機率為 `0.509`，即 `50.9%`，超過一半的可能性。

通過公式可以看到，隨著房間中人數的增加，至少有兩人生日相同的機率也增加。例如，一個教室有 30 名學生，那麼兩個同學生日相同的機率為 70%。如果把人數增加到 70 個人，那麼至少有兩人生日是同一天的機率為 99.9%。

延伸閱讀:
* [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem)
* [Extensions of the birthday surprise](https://www.sciencedirect.com/science/article/pii/S0021980067800759)

- [ ] 自我檢查事項
* 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
* [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響在哪些層面？
* 像是 [Random Number Generator](http://stattrek.com/statistics/random-number-generator.aspx) 這樣的產生器，是否能產生「夠亂」的亂數呢？

## Linux 風格的 linked list

閱讀 [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf) 共筆和觀看解說錄影。

$ git clone https://github.com/sysprog21/linux-list
$ cd linux-list
$ make

預期會得到以下輸出:

  CC   tests/containerof.o
  LD   tests/containerof
*** Validating tests/containerof ***
 [ Verified ]
...
  CC   tests/list_cut_position.o
  LD   tests/list_cut_position
*** Validating tests/list\_cut\_position ***
 [ Verified ]

其中 `include/list.h` 學習 Linux 核心原始程式碼的 linked list 資料結構實作程式碼。

- [ ] 自我檢查事項:

* 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
* GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* 解釋以下巨集的原理

#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 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
* 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
* `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* `tests/` 目錄的 unit test 可如何持續精進和改善呢？

## 針對 linked list 的排序演算法

研讀 [A Comparative Study Of Linked List Sorting Algorithms](https://www.researchgate.net/publication/2434273_A_Comparative_Study_Of_Linked_List_Sorting_Algorithms)

- [ ] 自我檢查事項

* 對 linked list 進行排序的應用場合為何？
* 考慮到 linked list 在某些場合幾乎都是幾乎排序完成，這樣貿然套用 quick sort 會有什麼問題？如何確保在平均和最差的時間複雜度呢？
* 能否找出 Linux 核心原始程式碼裡頭，對 linked list 排序的案例？
* 透過 [skiplist](https://en.wikipedia.org/wiki/Skip_list) 這樣的變形，能否加速排序？
* 研讀 [How to find the kth largest element in an unsorted array of length n in O(n)?](https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on)，比照上方連結，是否能設計出針對 linked list 有效找出第 k 大 (或小) 元素的演算法？
* [linux-list](https://github.com/sysprog21/linux-list) 裡頭 `examples` 裡頭有兩種排序實作 （insertion 和 quick sort)，請簡述其原理

## 作業要求

* 回答上述「生日悖論」、「Linux 風格的 linked list」，和「針對 linked list 的排序演算法」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
* 在 GitHub 上 fork [linux-list](https://github.com/sysprog21/linux-list)，參考 `examples/insert-sort.c` 和 `examples/quick-sort.c` 的實作方式，實作 merge sort，並且在 `tests/` 目錄提供新的 unit test
* 研讀「你所不知道的 C 語言」的 [函式呼叫篇](https://hackmd.io/s/SJ6hRj-zg) 和 [技巧篇](https://hackmd.io/s/HyIdoLnjl) 探討 [linux-list](https://github.com/sysprog21/linux-list) 的 `include/list.h` 的實作考量 (在上述檢查清單已提及部分)
* 承上，實作測試程式，批次建立包含若干大小的 linked list，隨機放入數值為介於 1 到 366 之間 (包含) 的節點 (代表 [day number](https://www.epochconverter.com/daynumbers)) ，至少應該涵蓋 10^1^, 10^2^, 10^3^, ... 10^6^ 等數量，透過前述的 insert, quick, merge sort 進行排序，分析執行時間並解讀其行為
* 需要有檢驗的程式碼
* 承上，設計 deduplication 程式，將上述輸入中的數值挑出重複的節點並與刪除，透過統計分析，解讀執行時間分佈，以及探討 [data deduplication](https://en.wikipedia.org/wiki/Data_deduplication) 的效益
* 比照生日悖論，提出統計模型和數學分析
* 參照 [Remove duplicates from a sorted linked list](https://www.geeksforgeeks.org/remove-duplicates-from-a-sorted-linked-list/)
* 延續 [A Comparative Study Of Linked List Sorting Algorithms](https://www.researchgate.net/publication/2434273_A_Comparative_Study_Of_Linked_List_Sorting_Algorithms) 的方式，量化分析上述步驟，並且提出效能改善機制
* 將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/S1iCyyziG)」

## 截止日期

* Apr 24, 2017 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review，評分越高