D05: list

tags: sysprog2018

主講人: jserv / 課程討論區: 2018 年系統軟體課程

返回「作業系統設計與實作」課程進度表

預期目標

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

生日悖論

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

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

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

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

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

$$\begin{gathered} \mathrm{其}\mathrm{實}22\mathrm{個}\mathrm{人}\mathrm{中}\mathrm{遇}\mathrm{上}\mathrm{和}\mathrm{自}\mathrm{己}\mathrm{同}\mathrm{一}\mathrm{天}\mathrm{生}\mathrm{日}\mathrm{的}\mathrm{人}\mathrm{的}\mathrm{機}\mathrm{率}\mathrm{不}\mathrm{是}{\displaystyle \frac{22}{365}}\mathrm{而}\mathrm{是} \\ 1-\mathrm{第}\mathrm{一}\mathrm{個}\mathrm{人}\mathrm{生}\mathrm{日}\mathrm{不}\mathrm{同}\mathrm{的}\mathrm{機}\mathrm{率}\times \mathrm{第}\mathrm{二}\mathrm{個}\mathrm{人}\mathrm{生}\mathrm{日}\mathrm{不}\mathrm{同}\mathrm{的}\mathrm{機}\mathrm{率}\times ... \\ \begin{array}{rl}& =1-{\displaystyle \frac{364}{365}}\times {\displaystyle \frac{363}{365}}\times {\displaystyle \frac{362}{365}}\times ...\\ & =1-{\displaystyle \frac{P_{22}^{364}}{{365}^{22}}}\\ & =50.73\mathrm{\%}\end{array} \\ \mathrm{已}\mathrm{經}\mathrm{有}\mathrm{超}\mathrm{過}\mathrm{一}\mathrm{半}\mathrm{的}\mathrm{可}\mathrm{能}\mathrm{了} \end{gathered}$$
ryanpatiency

把第一個人與其他 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
• Extensions of the birthday surprise

• 自我檢查事項

• 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
• Birthday problem 對資訊安全的影響在哪些層面？
• 像是 Random Number Generator 這樣的產生器，是否能產生「夠亂」的亂數呢？

Linux 風格的 linked list

閱讀 你所不知道的C語言: linked list 和非連續記憶體操作 共筆和觀看解說錄影。

$ 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 有何作用？在程式碼中扮演什麼角色？
• 解釋以下巨集的原理

#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

• 自我檢查事項

• 對 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)，請簡述其原理

作業要求

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

截止日期

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