2018q1 Homework3 (list)

contributed by < BroLeaf>

tags BroLeaf

生日悖論

• 自我檢查事項

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

有 n 個人生日不重複的機率

$P^{\prime }(X)=\frac{365}{365}\times \frac{364}{365}\times \frac{363}{365}\times \frac{362}{365}\times \cdots \times \frac{366-n}{365}$

$=1\times (1-\frac{1}{365})\times (1-\frac{2}{365})\times (1-\frac{3}{365})\times \cdots \times (1-\frac{n-1}{365})$
引入Talor series

$e^x=1+x+\frac{x^2}{2!}+\cdots$

$\mathrm{當}X<<1\mathrm{時}，{\displaystyle e^x\approx 1+x}$
原式變為

$1\times e^{-\frac{1}{365}}\times e^{-\frac{2}{365}}\times e^{-\frac{3}{365}}\times \cdots \times e^{-\frac{n-1}{365}}$

$=e^{-\frac{n(n-1/2)}{365}}=e^{-\frac{n(n-1)}{730}}$
則有 n 個人生日會重複的機率為

$1-P^{\prime }(n)=1-e^{-\frac{n(n-1)}{730}}$

Linux 風格的 linked list

• 自我檢查事項:

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

  • 參考What is the difference between a macro and a function in C?

• Advantages

  • Time efficiency.
  • Not need to pass arguments like function.
  • It's preprocessed.
  • Easier to Read.

• Disadvantages

  • Very hard to debug in large code.
  • Take more memory in stack compare to function. Suppose in the program that there a Macro which used 50 times that means it will consume memory 50 times but in function if a function is called 50 times it will take single memory every time because every time it deallocate that memory

• C 語言對於 macro 的處理是在 preprocessed 這個解段，基本上可以當做是在 compile time 完成的，所以比起在 run time 才處理 function 的 push、pop 自然會更有時間上的效率，而這些勢必要多犧牲一些在 memory 的空間來達到這樣的效果