# list
contributed by <`rex662624`>, <`e94046165`>
[題目連結](https://hackmd.io/s/HkxZbJzif#)
## 生日悖論
### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
#### 1. A simple exponentiation
這種算法的核心思想為，先把事件縮小到兩個人生日不同的機率，而後算出房間內究竟可以組合出多少種兩個人的配對，房間內所有人生日皆不相同的機率就為觀察房間內所有兩兩一組的狀況，發現這兩個人生日皆不同的機率。
首先，任意兩個人生日不同的機率為$\dfrac{365}{365}*\dfrac{364}{365} =\dfrac{364}{365}$。而若一個房間內有 n 個人，這兩個人可以有的組合為 $C^{n}_2$組 。若是要估算全部的人生日皆不同的機率，我們可以將每兩個人生日不同的機率($\frac{364}{365}$)視為是獨立事件。而其中總共有$C^{n}_2$種事件。因此在一個有 n 人的房間內，沒有任何人生日相同的機率是$\dfrac{364}{365}*\dfrac{364}{365}*\dfrac{364}{365}......$。總共乘了$C^{n}_2$次，因為所有人生日皆不同的機率為兩兩生日皆不同的機率。
因此房間內生日皆不同的機率為$(\dfrac{364}{365})^{C^{n}_2}$，而房間內至少有兩個人生日相同的機率就為$1-(\dfrac{364}{365})^{C^{n}_2}$
由此，我們知道在房間內有22個人的狀況下，有生日相同的機率為$1-(\dfrac{364}{365})^{C^{22}_2}=0.4694$
而在房間內有23個人的狀況下，有生日相同的機率為$1-(\dfrac{364}{365})^{C^{23}_2}=0.5004$
#### 2.利用 Poisson distribution 計算
首先，Poisson distribution 適用的條件為下：
**(1) The event is something that can be counted in whole numbers**
**(2) Occurrences are independent, so that one occurrence neither diminishes nor increases the chance of another**
**(3) The average frequency of occurrence for the time period in question is know**
**(4) It is possible to count how many events have occurred**
首先，必須確定這個問題可以用 Poisson distribution 做解。
我們關注的是有兩人同一天生日這個 event，符合條件 **(1)**;且兩兩同一天生日的機率是獨立的，符合條件 **(2)**;單位時間內事件的平均發生機率 λ 可以由人數排列組合和一年有365天求得，符合條件 **(3)**;有多少個兩人同一天生日是可數的，符合條件 **(4)** 。
$而\ Poisson\ distribution\ 的公式為\ \ P(k\ \ events\ \ in\ \ interval )= e^{-\lambda} \dfrac{\lambda^k}{k!}$
我們要求的是至少有兩人同一天生日的機率，也就是 $P'=1-P(0)$ ，k=0 代表的是沒有人同一天生日(兩人同一天生日這個 event 發生的次數為0，$P(k=0)$)
而$\lambda$則是一年365天內兩人生日相同的機率，這裡透過 [Poisson approximation for the binomial](https://en.wikipedia.org/wiki/Poisson_distribution "Poisson distribution")知道$\ \ \lambda = np。其中\ n=C^{23}_2 ，是23人中取某2人生日相同，p=1/365，是兩個人生日在某一天的機率。$
$因此在房間有23人的狀況下\ \lambda =np=\dfrac{C^{23}_2}{365}=0.6932$ ， 22人則為$\lambda=\dfrac{C^{22}_2}{365}=0.6328$
23人狀況下:$1-P(0)=1-e^{-0.6932} \dfrac{-0.6932^0}{0!}≈1-0.499998≈0.500002$
22人狀況：$1-P(0)=1-e^{-0.6328} \dfrac{-0.6328^0}{0!}≈1-0.5311≈0.4689$
### [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響在哪些層面？
在密碼學上，有 birthday attack 這種議題。一般在傳遞訊息時，可能會經過一些加密的程序，而我們常用到 Hash function 這種加密方式。而 Hash function 的原理是，例如我們的密碼是 x ，則經過 hash(x) 轉換之後，會產生一個輸出 y ，這個 y 就是已經經過加密的訊息。一個 hash function 的好壞，就在於它是否能夠使輸出的 y 值盡量分散，減少輸出值的碰撞(collision)，這樣就能避免兩樣東西得到同樣的輸出。
如果把 hash function 的每個輸入值想成是房間內 n 個人中的一個，再把輸出值想成是每個人的生日，那麼 Birthday problem 就告訴我們，只需要很少的輸入值，就會有很大的可能性有至少兩個輸出值完全相同。
以下透過數學進一步證明這個特性：
假設有一個 hash function 產生的 output set 為$\{0,1\}^n$，也就是總共有 n bits binary。全部總共有$2^n$種組合。也就是可以想成是我們總共有$2^n$個抽屜可以放資料。而我們將發現，總共只需要輸入$2^{\frac{n}{2}}$種 input 。最後轉換出來很有可能找到相同的 output ，也就是發生 collision 。
**Proof**
$\ let\ r_1.....r_n\ \in \{1\ ...\ B\}$ Be independent、identically distributed integers.
($\{1\ ...\ B\}$是我們的 output 宇集)
則其中我們產生的 n 種 output 有重複的機率為：
$Pr[\exists\ i\neq j, r_i=r_j]=1-Pr[\forall i\neq j,r_i\neq r_j]\\
=1-(\dfrac{B}{B}\cdot\dfrac{B-1}{B}\cdot\dfrac{B-2}{B}...\cdot\dfrac{B-n+1}{B})\\
=1-\prod_{i=0}^{n-1}(1-\frac{i}{B})。\ 而我們知道e^{-x}\geq1-x，因為由泰勒展開式知道e^{-x}=1-x+\frac{x^2}{2}-...$
$所以原式=1-\prod_{i=0}^{n-1}(1-\frac{i}{B})\\
\geq1-\prod_{i=0}^{n-1}e^{-\frac{i}{B}}=1-e^{-\frac{1}{B}\sum_{i=1}^{n-1}\ \ \ i}\\
\geq e^{-\frac{n^2}{2B}}$
將 $n = 1.2\times B^\frac{1}{2}$代入上式可得 53...%。
這個數據顯示出，只要輸入$B^\frac{1}{2}$的資料量，產生的 output 就有一半機率發生 collision。
而在我的電腦上測試以下程式碼，也可以發現跑 4294967296 ($2^{32}$)次迴圈需要8秒，因此若是用太少 bits 的 hash key value ，會有極大的風險有collision。
```clike=
#include <stdio.h>
#include <time.h>
int main() {
long int i = 0;
time_t start, end;
time(&start);
while (i < 4294967296) {
i++;
}
time(&end);
printf("time: %lf\n", difftime(end, start));
return 0;
}
```
### 像是 [Random Number Generator](http://stattrek.com/statistics/random-number-generator.aspx) 這樣的產生器，是否能產生「夠亂」的亂數呢？
整理自`team6612`(共筆連結附於下方)
##### 1. 定義何謂"亂"(random)
我們認爲一個事件「亂」，表示我們無法預測該事件的結果，但統計學卻可以透過機率分佈的概念，即便無法準確的預測下一次的事件結果爲何，卻可以很「確定」的表示隨機事件的結果落在某個範圍內的機率是多少，或長期而言結果的統計量會趨近於某個確定的值。
而我們要說一個事件是無跡可循的，在統計上的觀點就是在事件上的每個位置發生機率都是均等的，這樣的性質叫做 uniform distributed 。但光是如此，還不足以稱之為是亂數。例如以下數列:
$f(i) = a + (i\ \%\ (b-a)), i=1, 2, 3, ...$
我們可以發現若是 a=1 , b=100 ，則這個數列會是2,3,4,...100,1,2......。雖然每個數字出現的機率都均等，但我們不會說這樣的數列是亂數，因為我們可以發現數字間的前後關係，也就是數字之間不是獨立的。
因此一般來說，真正的亂數必須具有兩種特性:
**隨機性**：平均分佈、獨立性（數字不能由其他數字推導而得）
**不可預測性**：下一個數字無法由前一個數字推導而得。
#### 2. Entropy
在密碼學的領域中，亂數是個很重要關鍵元素，我們要搞清楚一件一無所知的事情，就需要瞭解大量的資訊。相反，如果我們對某件事已經有了較多的瞭解，我們不需要太多的資訊就能把它搞清楚。所以，從這個角度來說，我們可以將不確定性(自由度)的多寡做為信息量的度量。因此若是我們要猜一組密碼，而這個密碼完全沒有什麼軌跡可循，也就是提供的訊息很少，則這組密碼就是很安全的。而這個量測事物無序性的一個重要的參數就是**熵**。
設一個隨機變量X，其可能的m種取值為x~1~,x~2~,⋯,x~m~，對於每一種取值的機率為：p~1~,p~2~,⋯,p~m~，那麼隨機變量X的不確定度，即熵，用H(X)表示：
$$
H(X)=- \sum^{m}_{i=1} P_i log_2 \frac{1}{P_i}=- \sum^{n}_{i=1} P_i log_2 P_i
$$
熵表示的是隨機變量X可能的變化，若隨機變量的變化越多，那麼其 H(X) 越大，若是測量亂數用的，也就表示亂數越亂。
因此我們能用熵來評估一個亂數產生器是否夠亂。這裡利用到了`team6612`寫的一個 javascript。若在 chrome 上操作，先對某個網頁按 `Ctrl+D`，然後跳出的訊息框按更多，把網址列改成以下程式碼，再回到[ Random Number Generator ](http://stattrek.com/statistics/random-number-generator.aspx)產生亂數後，按下剛剛加入的書籤，就會在 browser console 裡面顯示數據(按F12)。
```
javascript:(function(){var script=document.createElement('SCRIPT');script.src='https://rawgit.com/team6612/RandomnessTest/master/test-compress.js';document.body.appendChild(script);})()
```
而因為這個亂數產生器一次最多只能產生1000個亂數，因此我們的範圍一開始不應該設太大，以免失去評估的效果。因此這裡試試看產生1000個0~50的數字。
得到結果:
```
Calculated entropy = 5.626267458434571
Ideal entropy for N=51 is 5.672425341971495
Chi Square = 65.594
```
第一行是算出來的實際熵值，與第二行的理想熵值十分接近。而第三行的 Chi Square 則是卡方檢定中的$χ^2$ (Chi 念作"開")。這是用來檢測資料符不符合 Uniform distrubution 。
用[查表](https://homepage.divms.uiowa.edu/~mbognar/applets/chisq.html)方式可以得到 P 值，例如這裡的自由度(df)是 51(個數字)-1 =50，$χ^2$輸入65.594 ，得到0.06854。
經由卡方檢定計算出的 P 值若小於設定的信心水準 (一般設定門檻是0.05，代表95%信賴區間) 表示拒絕此虛無假說，則可宣稱此組資料不符合指定分佈，反之則宣稱無證據顯示此資料不符合該分佈。
因此這裡>0.05，無證據可以顯示此數據不符合 Uniform distrubution 。
#### 3.結論
我認為「夠亂」這個詞，端看於應用在甚麼場景，用來解決什麼問題，要求的亂數量的多寡也有關係。例如雖然這個亂數產生器用卡方檢定與熵來評估，符合亂數的標準，但是也不能保證不會被找到規則。作者也在網站自己說了，`it should not be used to generate numbers for cryptography(密碼學)`。
因此若要符合應用在密碼學上的亂數，必須要用[ CSPRNG ](https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator)這種更嚴格的亂數產生器。最大的差異在於， CSPRNG 多了「不能通過給定的隨機序列的一部分而以顯著大於${\frac {1}{2}}$的機率在多項式時間內演算出位元序列的任何其他部分」。意思就是若是知道了一部分的數列，不能有超過一半的機率可以推算出任何另外一部分的數列。
但電腦的演算法永遠只能產出非常接近亂數的數列。就算是收集周邊硬體訊息，例如環境噪音等加入演算法，只是利用這些資訊非常難以全盤掌握而且持續在更新，所以遠比純粹數學的方法安全。但仍然不能保證不被破解。若是要產生完全隨機的真亂數，就要引入量子電腦的量子特性。
## Linux 風格的 linked list
### **為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？**
在處理 functional call (subroutine) 時，總共需要做以下的動作:
* 將 function 參數及目前的 Program counter 存入 stack ，並調整 stack pointer，將 argument push 到 stack。
* 跳至該 function 執行
* pop stack 取得該 function 所需 argument。
* 執行 function 程式碼
* 存取執行結果
* 再次調整 stack pointer，return callee
由此可知 function call 需要做許多動作才會真正開始執行程式碼，執行完也要做一些工作，若是頻繁呼叫這個 function，則將會有大量的時間耗費。此外若是在處理 CPU cycle 等級的指令，例如我們要 delay 40 個 cpu cycle ，在精準計算上也會較為麻煩。
macro 的行為是在 preprocessing 的階段就會被編譯器轉換為對應的程式碼。如此可以避免上面的時間成本，但缺點是會造成空間的浪費，也就是程式碼所佔的記憶體會變大。而且 marco 不會做 type checking ，因此若程式碼一大， debug 會變困難。
因此在 linked list 這種程式碼規模較小，而且常常頻繁使用的情況，就較適合用 marco ，因為犧牲一點空間就可以省下很多的時間。
### **[Linux](https://github.com/torvalds/linux) 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量**
1. [linux/include/linux/fs.h](https://github.com/torvalds/linux/blob/master/include/linux/fs.h#L5) -- **作用:管理 file system**
根據檔案名稱，大致可以猜測到他是用來管理 file system 相關的 code 。
其中的 1002~1006行( linux kernel 隨時會更新，不一定準確) code 為
```clike=
struct file_lock {
struct file_lock *fl_next; /* singly linked list for this inode */
struct list_head fl_list; /* link into file_lock_context */
struct hlist_node fl_link; /* node in global lists */
struct list_head fl_block; /* circular list of blocked processes */
```
觀察註解寫道` struct file_lock represents a generic "file lock". It's used to represent POSIX byte range locks, BSD (flock) locks, and leases.`
這個結構應該是在管理 file 被某一個 process 寫入時，其他的 process 就不能寫入這個 file 的 file lock 角色。可以發現 這裡的第5行就用到 linked list ，把其他想用此 file 資源但被 block 的 process ，串成一個 linked list 。
2. [linux/fs/inode.c](https://github.com/torvalds/linux/blob/master/fs/inode.c) -- **作用:處理 inode 的各種操作**
首先要先釐清 inode 到底是甚麼東西。根據 OS 課程張大緯老師的講義 ch11 其中的P8 寫道:
==File Control Blocks (FCB) is a data structure contains information about a file. In UNIX, an FCB is called an inode.== 可以知道它是用來儲存每個檔案的一些資訊。磁碟中的可用空間分配以及檔案配置也都必須透過 inode 的存取來完成。
再看看其中一段關於產生新inode 的 code:
```clike=
struct inode *new_inode(struct super_block *sb)
{
struct inode *inode;
spin_lock_prefetch(&sb->s_inode_list_lock);
inode = new_inode_pseudo(sb);
if (inode)
inode_sb_list_add(inode);
return inode;
}
```
可以看到第7行首先呼叫函式產生新的 inode 結構，而後第9行把他加進list裡面。繼續往下看呼叫的`inode_sb_list_add(inode);`，可以發現的確呼叫了 list add 把他串進 linked list 中 ，而推測這個 list 是用於做索引，讓系統可以一次走訪所有 inode。
```clike=
void inode_sb_list_add(struct inode *inode)
{
spin_lock(&inode->i_sb->s_inode_list_lock);
list_add(&inode->i_sb_list, &inode->i_sb->s_inodes);
spin_unlock(&inode->i_sb->s_inode_list_lock);
}
```
3. [linux/kernel/sched/fair.c](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c)-- **作用:管理CPU排班**
我猜想 CPU 排班本來會用到 list ，因此去找cpu 排班的code，找到後發現是用 fair.c 作為檔名，因為 linux 系統預設排班法是用`Completely Fair Scheduler(CFS)`。
首先我們知道 CFS 排班法是選擇花費 CPU 時間最少的 process 起來執行，因此讓我們看看選擇 process 的 function ==pick_next_entity()==。
```clike=
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *left = __pick_first_entity(cfs_rq);
struct sched_entity *se;
/*
* If curr is set we have to see if its left of the leftmost entity
* still in the tree, provided there was anything in the tree at all.
*/
if (!left || (curr && entity_before(curr, left)))
left = curr;
se = left; /* ideally we run the leftmost entity */
.......(程式碼省略)
/*
* Someone really wants this to run. If it's not unfair, run it.
*/
if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
se = cfs_rq->next;
clear_buddies(cfs_rq, se);
return se;
}
```
因為linux是利用 rbtree 來維護 process ，所以一開始找 leftmost (不斷的往左走找)，最左邊的 process 就是有最小 runtime 的process ，這裡第20行的 next 我本來以為就是linked list 的應用，結果發現他這個`cfs_rq->next`指的只是下一個要跑的人(next 的意思是 next process to run)，並不是一個一個指下去的 list 關係。而這裡是用 rbtree 結構來維護 process，因此應該不算 linked list 。
參考[這裡](https://blog.csdn.net/conansonic/article/details/78203405)總算找到這份 fair.c 用 list_add(第11行) 應用 linked list 。這裡寫到， cfs_task 這個 list 是用來做 CPU Load balancing ，意思就是用來處理多核心狀況下，把負擔較大的CPU 分配工作給其他閒置的CPU 。
```clike=
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
update_load_add(&cfs_rq->load, se->load.weight);
if (!parent_entity(se))
update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
#ifdef CONFIG_SMP
if (entity_is_task(se)) {
struct rq *rq = rq_of(cfs_rq);
account_numa_enqueue(rq, task_of(se));
list_add(&se->group_node, &rq->cfs_tasks);
}
#endif
cfs_rq->nr_running++;
}
```
4. [linux/mm/page_alloc.c](https://github.com/torvalds/linux/blob/master/mm/page_alloc.c)-- **用來 allocate pages**
在程式碼開頭就寫了`Manages the free list, the system allocates free pages here.`。因此可以知道它是用來管理 free page list 的 allocate。以下是程式碼(第2482行開始)
```clike=
/*
* Obtain a specified number of elements from the buddy allocator, all under
* a single hold of the lock, for efficiency. Add them to the supplied list.
* Returns the number of new pages which were placed at *list.
*/
static int rmqueue_bulk(struct zone *zone, unsigned int order,
unsigned long count, struct list_head *list,
int migratetype)
{
int i, alloced = 0;
spin_lock(&zone->lock);
for (i = 0; i < count; ++i) {
struct page *page = __rmqueue(zone, order, migratetype);
if (unlikely(page == NULL))
break;
if (unlikely(check_pcp_refill(page)))
continue;
/*
* Split buddy pages returned by expand() are received here in
* physical page order. The page is added to the tail of
* caller's list. From the callers perspective, the linked list
* is ordered by page number under some conditions. This is
* useful for IO devices that can forward direction from the
* head, thus also in the physical page order. This is useful
* for IO devices that can merge IO requests if the physical
* pages are ordered properly.
*/
list_add_tail(&page->lru, list);
alloced++;
if (is_migrate_cma(get_pcppage_migratetype(page)))
__mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
-(1 << order));
}
/*
* i pages were removed from the buddy list even if some leak due
* to check_pcp_refill failing so adjust NR_FREE_PAGES based
* on i. Do not confuse with 'alloced' which is the number of
* pages added to the pcp list.
*/
__mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
spin_unlock(&zone->lock);
return alloced;
}
```
當 caller 請求一個 page 時，這裡將把 pages 分配出去，並串到 caller 的 page list 最後面(第31行`list_add_tail(&page->lru, list);`)。最後也回傳新 pages 在 linked list 上被分配的編號。
這裡值得注意的地方是，Linux Kernel 是以 Page 為記憶體管理的單位，也稱為 Buddy System 。這種方式的好處是會減少 external fragmentation，因為永遠是找最適合大小的 page分配出去，但是仍有 internal fragmentation。因為在 IA32 (x86) 的 page 大小是 4KB ，若是只想用3KB，仍會有 1KB 的浪費。
因此也有 Slab Allocator 可以先向 Buddy system 要一個 page ，然後再由 slab 切得更小以配置小量記憶體。
### **GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？**
GNU extension 指的是那些沒有規範在 ISO standard C 裡面的 feature，但是在 GNU C compiler 卻有被補充的那些 feature 都叫做 GNU extension。
[typeof 的官方文件](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 說到，`There are two ways of writing the argument to typeof: with an expression or with a type.`，以下將解釋兩種用法。
1.argument with an expression
若宣告一 function \: `int foo()` ,則 `typeof(foo(5))` 會回傳 int 。
若宣告一 double variable \: `double n`,則 `typeof(n)` 會回傳 double。
2.argument with a type
若今天宣告 `typeof(int *) ptr1, ptr2` ,則等同於 `int *a, *b;` 。
以下程式是測試 typeof 的好處之一，我覺得和例如 C# 或 C++ 等高階語言的 Generic 功能雷同，不須宣告多個 function ，就可以完成不同 type 參數傳入的操作。
```clike=
#include "stdio.h"
#define swap(a, b) \
do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
int main(int agrc, char **argv)
{
//--------test myself------------------
char a = 'a';
char b = 'b';
printf("ori: a = %c, b = %c\n",a ,b);
swap(a, b);
printf("new: a = %c, b = %c\n",a ,b);
int c = 1;
int d = 2;
printf("\nori: c = %d, d = %d\n",c ,d);
swap(c, d);
printf("new: c = %d, d = %d\n",c ,d);
}
```
output:
```
$gcc -o typeof typeof.c
$./typeof
ori: a = a, b = b
new: a = b, b = a
ori: c = 1, d = 2
new: c = 2, d = 1
```
### **解釋以下巨集的原理**
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
以下是測試程式與輸出結果
```clike=
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define offsetof(type, member) ((size_t)&((type *)0)->member)
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
printf("__pmember address:%p\n", __pmember); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
typedef struct student_info
{
int id;
char name[32];
int age;
} student_info;
int main()
{
size_t off_set = 0;
off_set = offsetof(student_info, id);
printf("id offset: %u\n",off_set);
off_set = offsetof(student_info, name);
printf("name offset: %u\n",off_set);
off_set = offsetof(student_info, age);
printf("age offset: %u\n\n",off_set);
student_info *stu = (student_info *)malloc(sizeof(student_info));
printf("stu->age address:%p\n", &(stu->age));
student_info *ptr = container_of(&(stu->age), student_info, age);
printf("\n");
printf("stu address:%p\n", stu);
printf("ptr address:%p\n", ptr);
return 0;
}
```
```
id offset: 0
name offset: 4
age offset: 36
stu->age address:0x251e444
__pmember address:0x251e444
stu address:0x251e420
ptr address:0x251e420
```
可以看到 offsetof 的作用為算出每個 member 的偏移量，舉例而言：
`id` 為 `student_info` structure 的第一個 member 因此 offset = 0
`name` 是第二個 member ，前一個 member `id` 的 size 為 4 bytes(int)，所以他的offset = 4
`age` 前面所有 member 佔了 4+32 = 36 bytes，偏移量 offset = 36
而 offsetof 的詳細運作原理如下：
```
#define offsetof(type, member) ((size_t)&((type *)0)->member)
```
`(type *)0` 強制將 `0` 轉換成輸入的 `type` 的指標 `(type *)`的型式，而 `0` 會被當成這個 type 起始的位置。((type *)0)->member) 就能得到 `member` 的地址，但這是在type 起始地址為 `0` 的情況下的地址，也就是這個 member 的 offset。
至此，我們能透過 offsetof 得到每個 member 的偏移量了，那這個偏移量在 container_of 裡怎麼被應用呢？
```clike=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
//printf("__pmember address:%p\n", __pmember); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
由上面的測試可以看出來，containerof 透過輸入 ptr(struct 中某成員的地址)、struct、member 就可以得到該成員所在 struct 的起始位置。概念上很簡單，已知成員的記憶體位置、已知成員的偏移量，相減就能得到起始位置。
那實作上這個 container_of 裏面怎麼運作呢?
為了使這個 macro 能接受不同 type 的輸入，因此使用的上面討論過的 typeof 函數
`const __typeof__(((type *) 0)->member) *__pmember = ptr`
定義一個 member 型別的指標 __pmember，並將輸入的位置 ptr 餵給他。
`(type *) ((char *) __pmember - offsetof(type, member));`
再把他的位置值減掉 offset 就是起始地址了。
本來這個部份的解說到這裡就結束了，但是我發現還是有很多搞不懂的小細節：
1. (type *)0 為何可以強制轉型成 type 指標的型式，並被當作 type 的起始位置呢？
印像中 (char *)、(int *)0 好像是用來代表 null pointer 啊
Ans:
```clike=
int main(){
int* ptr = 0;
if(ptr == NULL) printf("ptr is a null pointer\n");
else printf("%p", ptr);
printf("%p\n", ptr);
printf("%p\n", ptr+1);
return 0;
}
```
這是自訂的測試程式，當定義一個 int* ptr = 0 效果應該跟 (int *)一樣，那麼上列的程式會 printf 出什麼東西呢？測試結果如下：
```
ptr is a null pointer
(nil)
0x4
```
結果相當有趣，當 ptr 指向 0x0 的時候，會被當作 NULL pointer 來看待，而 ptr+1 則指向一個記憶體位置 0x4，為什麼不是 0x1 呢？理由是 ptr 是一個 int* 型指標函數，而 int 佔了4 bytes。
__結論：我們可以定義任意型別的指標到任意記憶體位置，不論該位址是否存放有該行別的變數。__
進一步測是 type 為 struct 的情況：
```clike
typedef struct student_info
{
int id;
char name[32];
int age;
} student_info;
int main(){
student_info* ptr = 0;
printf("Size of struct : %d\n", sizeof(student_info));
if(ptr == NULL) printf("ptr is a null pointer\n");
else printf("%p", ptr);
printf("%p\n", ptr);
printf("the address of member id: %p\n", &ptr->id);
printf("the address of member name: %p\n", &ptr->name);
printf("the address of member age: %p\n", &ptr->age);
ptr++;
if(ptr == NULL) printf("ptr is a null pointer\n");
else printf("%p\n", ptr);
return 0;
}
```
測試結果：
```
Size of struct : 40
ptr is a null pointer
(nil)
the address of member id: (nil)
the address of member name: 0x4
the address of member age: 0x24
0x28
```
由輸出結果可以看出，就算我們定義一個 struct* 型別之 ptr 指向一個不存在 struct 型別變數之位置 0x0，我們依舊可以 ptr->member 一樣會找到各個 member 應該要在哪個位址。
這個輸出結果同樣可以幫助我們更加理解 offsetof 中的 ((type \*)0)->member 是如何運作的：
定義一個 type* 的指標指向 0x0 位址上的 type 型別變數(實際上 0x0 並沒有存放 type 型別的變數)，而當輸入的 type 為一個 struct 時，struct 中所有 member 的位置也都依照起始位置 0x0 被定義，也就是我們想找的 offset，所以 &((type *)0)->member 就可以得到各 member 的 offset 值。用 size_t 而不用 int 可以避免在不同環境下 int 位數不同的問題。
2. `(type *) ((char *) __pmember - offsetof(type, member));`為何要用 (char *) 宣告 `__pmember - offsetof(type, member)`
Ans: `__pmember - offsetof(type, member)` 的結果應該是一串數字構成的記憶體位址，因此直覺的想用 int 或 unsigned int 來宣告，但是這樣可能遇到在不同環境下表示位元不夠的問題。用(char *)就能避免掉長度的問題，但是如果將這個 (char *) 拿掉呢？
`(type *) ( __pmember - offsetof(type, member));`
~~實際測試結果是與先前的輸出相同~~，概念上，這個 macro 回傳一個指向一記憶體位置的 type * pointer 沒有問題，但目前仍不清楚這個 (char *) 的用意。
:::warning
回想 C99/C11 提到 dereference 時會遇到的 alignment 議題，倘若將 `(char *)` 換成 `(void *)` 會發生什麼事呢？繼續翻規格書！
:notes: jserv
:::
測試：
`(type *) (__pmember - offsetof(type, member));` v.s
`(type *) ((void *)__pmember - offsetof(type, member));` v.s
`(type *) ((char *)__pmember - offsetof(type, member));`
### **除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？**
[ list.h ](https://github.com/torvalds/linux/blob/master/include/linux/list.h)光是 list_add，就有 list_add_valid、hlist_add_behind、hlist_add_before、list_tail等等。而觀察程式碼一開始的註解寫到
```clike=
/*
* Simple doubly linked list implementation.
*
* Some of the internal functions ("__xxx") are useful when
* manipulating whole lists rather than single entries, as
* sometimes we already know the next/prev entries and we can
* generate better code by using them directly rather than
* using the generic single-entry routines.
*/
```
可以知道呼叫後面有 \_\_XXX 的函式，比起 general 的 add ，這種特定操作的add 能帶來效能上的助益，因為當我們已經知道 next 或 prev 的 entry，我們或許可以善加利用這些資訊，而非只是用 general 的 add。
例如：
```clike=
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
```
```clike=
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
```
這個 __list_add 可以讓我們在任何已知 prev 、 next 的情況下將新節點 new 加到 list 中特定的位置，而更有趣的是也可以當我們只是要將 new 加到 head 之後，對應的 list_add 也是 call 這個 function
```clike=
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
```
因為置入 head 之後，所以 prev 當然是 head，而 next 則是原來的第一個節點，也就是 head->next。
```clike=
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
```
在這個加入 entry 在 head 後一個的 function 旁有一段註解，最後一句提到 "This is good for implementing stacks"因為這符合 stack LIFO 的特性，猜測在 list.h 中應該也可以找到一個刪除 head 後的第一個 entry 的 list_del function 兩者合起來就可以實作 stack 的 pop/push 動作。
雖只看了幾個 functions 但是可以深刻的感受到，如果依照特定的需求，找到適合的 function，實作起來應該可以事半功倍，整份 list.h 應也是因應不同的場景需求，每個 linked list 的動作(add、del...)都維護了數種不同的實作方式。
### **`LIST_POISONING` 這樣的設計有何意義？**
[List poisoning](https://en.wikipedia.org/wiki/List_poisoning) 在 wikipedia 上面的定義是用於電子郵件攻擊，被攻擊者用一些 invalid mail address 攻擊。而參考[ linux-like-list ](https://github.com/ecsv/linux-like-list/blob/master/list.h) ，裡面寫到了
```clike=
/**
* hlist_del() - Remove a hlist node from the hlist
* @node: pointer to the node
*
* The node is only removed from the hlist. Neither the memory of the removed
* node nor the memory of the entry containing the node is free'd. The node
* has to be handled like an uninitialized node. Accessing the next or pprev
* pointer of the node is not safe.
*
* Unlinked, initialized nodes are also uninitialized after hlist_del.
*
* LIST_POISONING can be enabled during build-time to provoke an invalid memory
* access when the memory behind the next/prev pointer is used after an
* hlist_del. This only works on systems which prohibit access to the predefined
* memory addresses.
*/
```
可以看到 12\~15行說使用了`hlist_del`後，可能會發生LIST_POISONING，回頭看5~8行也有寫原因是因為用了這個函數後， node 只是從 list 裡面移除，list 所佔的 memory 或是裡面的資料都沒有被 free，因此若是此時又去訪問他的 next 或是 prev ，則這是不合法的，因為他被從 list 移除，操作他的行為應該要與操作一塊空白記憶體相同。
此外可以發現 [ linux/list.h ](https://github.com/torvalds/linux/blob/master/include/linux/list.h)之中，list_del 將要刪除的 entry 的 next 和 prev 都指向 LIST_POISON 。
### **linked list 採用環狀是基於哪些考量？**
1. 不需要 maintain 兩個 pointer front 和 rear ，只需要一個 last，我們就知道他的下一個 node 是 front。
2. 設計演算法較一般的 linked list 容易，彈性也較大，因為沒有第一個或是最後一個的問題，例如如果要改 last 到另一個 node ，一般的 list 需要把新 last 搬到後面，last->next=NULL 等動作，而 circular list 只要 改 last指標就好，結構完全不需變動。
### **`list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？**
首先比較程式碼
```clike=
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
```
```clike=
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
```
原本的版本處理 list_del 時會出問題。首先，我在`LIST_POISONING`那道題目最後講到，list\_del 將要刪除的 entry 的 next 和 prev 都指向 LIST\_POISON。因此如果是用 list_each 來 delete ，delete 完目標之後，下次回來for會做的是 pos =pos->next，但此時的 pos 已經是 LIST\_POISON ，因此就會錯誤。
但是在 list_each_safe 的版本中，用一個 temp 指標n，在回到 for 的一開始就做 pos = n ，因此若是刪除 pos 這個 node ，下次回來會先執行 pos = n，而此時的n 是上一個循環存的pos->next，也就是刪除的人原本的 next ，因此就能成功的指向正常 list。
### **for_each 風格的開發方式對程式開發者的影響為何？**
[for each](https://msdn.microsoft.com/zh-tw/library/e5sk9w9k.aspx)，`for_each(InputIterator _First, InputIterator _Last, Function _Func);`，可以讓使用者針對範圍( first 到 last )去做特定的 function ，比起原來用 for 迴圈，再 call function，程式碼簡潔得多。
### **程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？**
參考[ doxygen ](http://nano-chicken.blogspot.tw/2009/07/doxygen.html)。 Doxygen 是一個 document generator ，可以將程式中的註解轉換成為說明文件。如果我們寫註解的時候，可以依據某種格式，就可以不用另外寫說明文件，可以透過這個 generator 直接產生說明文件，若今天程式碼做修改，我們也不用再去維護文件，而是只要用 Doxygen 產生新版的文件就好。
而根據[ doxygen 說明文件](https://www.stack.nl/~dimitri/doxygen/manual/commands.html#cmda)裡面第一句話就寫到了`All commands in the documentation start with a backslash (\) or an at-sign (@).`用`@`作為註解開頭，是 Doxygen command 規定的特定語法。我也思考 linux kernel 為什麼不用`\`作為開頭而是用`@`作為開頭，因為文件裡面寫兩者其實都可以。推測是因為 C 語言裡面的`\`是作為 escape character 。例如我們打`printf(%s,"\"")`，印出來的是`"`，因此本身C程式碼可能就會出現很多`\`，如果我們要搜尋整份程式碼寫的 doxygen 註解，用`@`才不會搜尋到我們不想要的資訊。
### **`tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？**
`tests/`裡面分為許多檔案，而每個檔案的用處就是針對某個 list.h 的某個功能做測試。這樣的測試就軟體工程來說可以方便 debug 。先確定每個小模組是正確無誤的，然後再兜起來如果發生錯誤，我們就可以排除是某個小模組出錯的可能，而是可能在兜起來的邏輯上有錯誤。
以 list_add.c 來做說明
```c=
#include <assert.h>
#include "list.h"
#include "common.h"
int main(void)
{
struct list_head testlist;
struct listitem item1;
struct listitem item2;
struct listitem item3;
struct listitem item4;
struct listitem *item = NULL;
size_t i;
item1.i = 1;
item2.i = 2;
item3.i = 3;
item4.i = 4;
INIT_LIST_HEAD(&testlist);
assert(list_empty(&testlist));
list_add(&item1.list, &testlist);
list_add(&item3.list, &item1.list);
list_add(&item2.list, &item1.list);
list_add(&item4.list, &item3.list);
i = 1;
list_for_each_entry (item, &testlist, list) {
assert(item->i == i);
i++;
}
assert(i == 5);
return 0;
}
```
- 可以看到這段程式碼，主要宣告變數、初始化，並且重點是 24～27 用了四次 ```list_add``` ，然後再去用 ```assert()``` 檢查，所作的跟變化跟預期有沒有相同，因此這個 unit test 檔就是用來測試 ```list_add``` 是否有誤，其他在 tests/ 下的檔案皆是這個概念。
- 單元測試在軟體工程來說是非常重要的一環，有了單元測試在做 refactor 時，會相對比較容易而且比較不會出錯，如果對更進階的想法來說，編寫程式同時編寫測試案例，甚至有時會先撰寫測試案例，這就比較偏向 TDD (Test-Driven-Develop)，就是因為你會先知道要測試什麼，而實做出來的功能才不會開發過度，甚至知道有什麼功能應該要捨棄。
### **`tests/` 目錄的 unit test 可如何持續精進和改善呢？**
- 避免在一個 unit test 中，同時用到多個在專案中自行定義的 function，否則測試結果顯示為錯誤的話，無法判定是否為想要測試的那個 function 造成的問題，應該要讓操縱變因保持為一個，或是在確認其他 function 能正常運作後才使用該 function
- 可以增加變異性，並測試一些 boundary condition 。或是故意測試一些會出錯的值，看程式碼是否能夠抓到並印出 warning。
## 針對 linked list 的排序演算法
### **對 linked list 進行排序的應用場合為何？**
1. 若使用者想知道 process消耗的 CPU 資源，可能就須經過 sort 把消耗資源比率由大排到小。
2. 管理 Memory 時，可能需要知道分散的 memory space 由小排到大的關係，才能用作例如 Best-Fit 或是 Worse-fit 等分配。
3. phonebook(電話簿程式) ，如果本來數據是打亂的，要把它變回原本按照英文字母排序的形式儲存在 list ，也要使用 sort。
### **考慮到 linked list 在某些場合幾乎都是幾乎排序完成，這樣貿然套用 quick sort 會有什麼問題？如何確保在平均和最差的時間複雜度呢？**
首先看到[ linux kernel 的 list sort ](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)是用 Merge sort，而不是用 quicksort 。比較一下兩者的 Complexity 差異:[來源](https://softwareengineering.stackexchange.com/questions/146173/merge-sort-versus-quick-sort-performance)
||mergesort|quicksort|
| ---| --- | --- |
|best case|$O(n log n)$|$O(n log n)$|
|average case|$O(n log n)$|$O(n log n)$|
|worst case|$O(n log n)$|$O(n^2)$|
乍看之下發現主要是考慮到 Worse case ， quicksort 的效能將會大幅下降，因此在不清楚資料分布的狀況下選用 Mergesort 是較好的選擇。但是我們不能就此下定論，因為要看處理的情境與場合才能確定要使用甚麼演算法。
以下將更深入的比較兩者的差異。其實 quick sort 更適合用來處理 array 的排序，而 Merge sort 則適合用來處理 linked list 的排序。
==為何 quicksort 更適合處理 array 排序==
**1. quicksort 是 in-place 排序** :
這代表他不需要額外的 space 暫存資料。但 Mergesort 需要 O(N) space來暫存每輪 Merge 後的資料。N 是 array 的大小，若是今天處理很大的 array ，space cost 也會很昂貴，此外一直 allocate,free 也會造成執行時間上的浪費。
**2.Quick Sort 是 cache friendly sorting**:
Quick sort 的特性是會走訪 array 去與 pivot key做比較，因此他有利於 cache 的 spatial locality。而 merge sort 則因為他不是 in place ，不能保證新宣告的暫存 array 與原來的 array 是放在記憶體連續的地方。
由以上的觀點，並考慮到兩者的 average case 都是 O(NlogN) ，而且也有 Randomized Quick sort 這種演算法大幅降低 Quick sort 的 worst case 發生機率，因此用 quicksort 處理 array sort 是較佳的選擇
==為何 Mergesort 更適合處理 linked list 排序==
**1.linked list 不需要額外空間** :
Merge sort 在處理 linked list 排序時，只需要宣告一個 head 作為暫存的 head 。因此我們可以在 O(1) 額外 space 達成。
**2.linked list 不能 random access**:
在 quicksort ，我們要將比Pivot大的數值換到右邊，或比Pivot小的數值換到左邊時，需要 swap array[i] 和 array[j]，但是在 linked list，並不能這樣直接 access 到某個 node ，只能從頭開始走訪。我們也不能保證 linked list 的記憶體是連續的，因此無法去用 memory address 的加減法做到(但 array 就可以用記憶體位置加減法算到自己要的位置)。而 Merge sort 對這種 random access 的需求就較小，所以並沒有此問題。
此外，考慮到 linked list 在某些場合幾乎都是幾乎排序完成的，
這樣容易遇到 quick sort 中的 worst case，理由如下:
quick sort 之所以能達到 $O(n log n)$ 等級是因為利用 partition->sort，將一個排序(主問題)不斷分成左右兩個的排序(子問題)，來使時間縮短。當處理一串已排序完成的資料、或插入的資料為最大(最小)值時，Pivot 就會被排到最後一個(第一個)，左右兩邊的資料個數分別為 0 與 (n-1)，也就等於沒有 partition，時間複雜度為 $O(n^2)$。
綜合以上我們可以知道，處理 linked list 排序用 Merge sort較為適合。
### **能否找出 Linux 核心原始程式碼裡頭，對 linked list 排序的案例？**
利用[這個工具](https://livegrep.com/search/linux)可以從 linux 程式碼找關鍵字，另外想起上作業系統時，老師第一堂課有介紹[ linux lsr ](https://elixir.bootlin.com/linux/v4.8.17/ident) 應該也是用來尋找關鍵字的網站。首先 linux 的 sort function 是命名為 **list_sort**。因此我鍵入關鍵字看能夠找到甚麼案例。
發現檔名比較親切的只有 [linux/fs/ext4/fsmap.c](https://github.com/torvalds/linux/blob/master/fs/ext4/fsmap.c)，裡面的 line 451 有用到 list_sort。乍看之下是用來顯示 file system 的 information (參考[這裡](https://patchwork.kernel.org/patch/9654745/)和[這裡](https://sort.veritas.com/public/documents/vis/7.2/aix/manualpages/html/man/file_system/html/man1/fsmap.1.html))。而裡面的 function `ext4_getfsmap_find_fixed_metadata` 裡面用到 sort，這個 function 的目的是獲取 filesystem 的 metadata。先收集完全部之後存在 meta_list ，然後會用 list_sort 做一次排序。
### **透過 [skiplist](https://en.wikipedia.org/wiki/Skip_list) 這樣的變形，能否加速排序？**
* skip list 是一種針對 sorted linked list 的資料結構，透過不同 level 做出不同的 linked list 達到加速搜尋的效果
e.g. 搜尋 `7`
1. 從 level 4 比對， 1 <= 7 ， null 跳 level 3
2. level 3 比對 4 <= 7 , 6 <= 7, null 跳 level 2
3. level 2 比對 9 >= 7 跳 level 1
4. level 1 比對 7 == 7
比對 5 次，比直接查詢 （7 次） 還要快
* skiplist 對於 查詢，刪除，和插入元素的時間複雜度 為 O(logn)，這對於經常要進行查詢的排序演算法，如：insertion sort，selection sort 會有複雜度上（理論上）的優勢，但是也會因為需要維護更多空間（更多上層的 sub-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 大 (或小) 元素的演算法？**
參考演算法講義`09_Medians and Order Statistics` P19 ，(或是上方連結有寫到)但這種演算法是尋找第 i 小的元素，因此稍加修改可以做出尋找第 i 大的元素
找出第 i 大的元素 pseudocode 為 \:
```
Select(i)
{
/*找 median-of-medians*/
將n個元素分成 ⌈n/5⌉ 個由5個元素構成的小群
找出每群的中位數
利用 Select 函數找出這 ⌈n/5⌉ 個中位數的中位數 x
/*找出第 i大的元素*/
利用 x 作為 Partition 使用的 Pivot ， Partition 後 x=A[k]
如 i=k 則 return x
如 i>k 則對大於 x 的那些元素做 Select(i)
如 i<k 則對小於 x 的那些元素做 Select(i-(n-k)) //因為全部index > k 的人都比他大，共 n-k 個。
}
```
### **[linux-list](https://github.com/sysprog21/linux-list) 裡頭 `examples` 裡頭有兩種排序實作 （insertion 和 quick sort)，請簡述其原理**
程式碼:
```clike=
static void list_insert_sorted(struct listitem *entry, struct list_head *head)
{
struct listitem *item = NULL;
if (list_empty(head)) {
list_add(&entry->list, head);
return;
}
list_for_each_entry (item, head, list) {
if (cmpint(&entry->i, &item->i) < 0) {
list_add_tail(&entry->list, &item->list);
return;
}
}
list_add_tail(&entry->list, head);
}
static void list_insertsort(struct list_head *head)
{
struct list_head list_unsorted;
struct listitem *item = NULL, *is = NULL;
INIT_LIST_HEAD(&list_unsorted);
list_splice_init(head, &list_unsorted);
list_for_each_entry_safe (item, is, &list_unsorted, list) {
list_del(&item->list);
list_insert_sorted(item, head);
}
}
```
首先看上方的 insertion sort ， list_insertsort()在 30 行，會把 item 傳進 list_insert_sorted() 內，而意義就是 insertion sort 的把目前要 insert 的 key 與目前已經排好的 list 做比較。因此在第10~14行，就是走訪目前 list ，直到找到比 key 還大的人就停下來插入 list。
```clike=
static void list_qsort(struct list_head *head)
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move(&item->list, &list_greater);
}
list_qsort(&list_less);
list_qsort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
以上是 quicksort 程式碼，可以注意到13~14行是在做選出 pivot key。然後16~21行，是對 list 中的每個數字，若是比 pivot 大就加入大的 list ，反之則加入小的 list。而23~24行對大小 list 做 recursive call 。最後終止條件在第7~8行。
## 參考連結
* Birthday 問題:
[Wikipedia - Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem)
[rex662624 的共筆](https://hackmd.io/ydo2r5veS66u5eG6p36EEw?view)
[piggyking1421 的共筆](https://hackmd.io/s/SkzlHZy3G#)
[birthday attack](https://www.getit01.com/p2017120653854/)
[LinYunWen 的共筆](https://hackmd.io/s/S1aszm0sM#)
[Generic Birthday Attack開放式課程](https://www.coursera.org/learn/crypto/lecture/pyR4I/generic-birthday-attack)
[team6612 的共筆](https://hackmd.io/s/r1A3kFPjz#)
[熵](https://blog.csdn.net/google19890102/article/details/51025764)
[Chi-square Test](http://belleaya.pixnet.net/blog/post/30844198-%5B%E6%95%99%E5%AD%B8%5D-%5B%E7%B5%B1%E8%A8%88%5D-%E5%8D%A1%E6%96%B9%E6%AA%A2%E5%AE%9A-%E5%B0%8F%E7%AD%86%E8%A8%98-%28%E6%9C%AA%E5%AE%8C%29)
* Linux 風格的 linked list
[linux/mm/page_alloc.c 的 rmqueue_bulk](https://blog.csdn.net/lights_joy/article/details/2732491)
[afcidk 的共筆](https://hackmd.io/s/Hk75lsjjM#Linux-%E9%A2%A8%E6%A0%BC%E7%9A%84-linked-list)
* 針對 linked list 的排序演算法
[Why Quick Sort preferred for Arrays](https://www.geeksforgeeks.org/why-quick-sort-preferred-for-arrays-and-merge-sort-for-linked-lists/)
Sign in with Wallet
Connect another wallet