D04: prefix-search

tags: sysprog2018

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

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

預期目標

• 學習 ternary search tree 作為 auto-complete 和 prefix search 的實作機制
• 延續 phonebook 的基礎工作，引入 ternary search tree 讓電話簿程式得以更符合人性
• 配合 Week4 進度，思考針對現代處理器特性的高效能程式設計議題
• 設計效能評比 (benchmark) 的程式框架
• 學習 GNU make 的進階技巧
• 複習機率統計

Autocompletion in C

• Autocomplete using a ternary search tree
• Ternary Search Tree 視覺化
  • 用 ab, abs, absolute 等字串逐次輸入並觀察
• 實際整合案例: Phonebook: adds new contacts and effectively search for contacts via ternary search tree

ternary search tree

• 取得 prefix-search 程式碼，編譯並測試

$ git clone https://github.com/sysprog21/prefix-search
$ cd prefix-search
$ make
$ ./test_cpy

• 預期會得到以下執行畫面:

ternary_tree, loaded 259112 words in 0.151270 sec

Commands:
 a  add word to the tree
 f  find word in tree
 s  search words matching prefix
 d  delete word from the tree
 q  quit, freeing all data

choice: 

• 按下 f 隨後按下 Enter 鍵，會得到 find word in tree: 的提示畫面，輸入 Taiwan (記得按 Enter)，預期會得到以下訊息:

find word in tree: Taiwan
  found Taiwan in 0.000002 sec.

• 當再次回到選單時，按下 s 隨後按下 Enter 鍵，會得到 find words matching prefix (at least 1 char): 的提示訊息，輸入 Tain，預期會得到以下訊息:

  Tain - searched prefix in 0.000011 sec

suggest[0] : Tain,
suggest[1] : Tainan,
suggest[2] : Taino,
suggest[3] : Tainter
suggest[4] : Taintrux,

• 不難發現 prefix-search 的功能，可找出給定開頭字串對應資料庫裡頭的有效組合，你可以用 T 來當作輸入，可得到世界 9 萬多個城市裡頭，以 T 開頭的有效名稱
• 至於選單裡頭的 a 和 d 就由你去探索具體作用

GNU Make 的技巧

• 參見 Makefile header 檔的相依性檢查

透過統計模型來分析資料

• 參照交通大學開放課程: 統計學(一) / 統計學(二)
  • 95％信賴區間是從樣本數據計算出來的一個區間，在鐘形曲線的條件下，由樣本回推，「可能」會有 95 % 的機會把真正的母體參數包含在區間之中
  • 鐘形曲線可見資料的密集與散佈與否
  • 圖形上第一個數為平均，第二個數為標準差的平方，我們稱以下圖形為機率密度函數 Probability Density Function (PDF)
    
  • 雖然不一定每種統計數據都是常態分佈，但只要資料是常態分佈，機率密度函數就會成鐘形曲線，這是我們所希望的，因為排除掉忽大忽小的個案，才可以掌握資訊的正確性

把 prefix-search 程式碼和給定的資料分用從 CPY 和 REF，用統計的方式重畫，其中 X-axis 是 cycles 數，Y-axis 是到目前為止已累積多少筆相同 cycle 數的資料。

• CPY 分析分佈
  
• REF( Memory pool 版本 ) 分析分佈
  

• 轉換圖表 X-Y 的數據後我們可以很明顯的看出 REF 資料密集程度遠大於 CPY ，不只在 count 累積的數目，也在 cycles 的 range 有很大的差異
• 計算平均與標準差：
  標準差
  $\sigma =\sqrt{{\displaystyle \frac{1}{N}}\cdot \sum _{k=1}^N(X_i-\bar{x}{)}^2}$
  • CPY 平均： 5974.116 cycles
  • CPY 標準差: 5908.070
  • REF 平均: 65.885 cycles
  • REF 標準差: 9.854
• 帶入機率密度函數公式：
  
  $f(x)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-\frac{(x-\mu {)}^2}{2{\sigma }^2}}$
  • 把 x 帶入後，在常態分佈下資料展現如下圖。要特別注意是，因為我們判定資料型態像常態分佈才用這個公式算出理想的模型，CPY 表現太分散，其實並不像常態分佈所以才會在算 95% 信賴區間（平均加減 2 倍標準差）時出現負數，而 REF 符合常態分佈，在此假設他們是常態分佈下才能做以下的鐘形曲線圖
  • probability 總和為 1，因為資料量大，所以如果愈分散每個 cycles 分到的機率愈小

• REF_PDF ideal model (理想情況):
  

• REF_PDF real model (真實情況):
  

顯然真實情況偏離理想狀況，但我們可將出現機率很小且不符合 95% 信賴區間的數值拿掉不考量。

CPY_PDF real model ：

* CPY 除了非常不符合常態分佈以外，還有一個更糟糕的情況，我們出現機率少的數值竟然佔大多數，可見資料是十分分散的，所以這邊我們不能取 95% 信賴間，因此得重新分析 CPY_PDF。

• Poisson distribution

• 參考 Statistics The Poisson Distribution , 統計應用小小傳 ，wiki

  • 上禮拜的課程中提到的卜瓦松分布，剛好有 CPY 的特性
    • The fundamental trait of the Poisson is its asymmetry，and this trait it preserves at any value of
      $\lambda$

• 有別於我們一般常態分佈的對稱性，不對稱性剛好是卜瓦松分布的特色
  

  • x 軸代的 k 是 index ， y 軸則是代入 k 後的機率

• Probability of events for a Poisson distribution：
  P ( k events in interval ) =

  $e^{-\lambda }\cdot {\displaystyle \frac{{\lambda }^k}{k!}}$
  • 他只需要一個參數 ： 單位時間平均事件發生次數 λ
  • 要判定一個統計是否可以做出 Poisson distribution 必須要有以下特點：
    (1) the event is something that can be counted in whole numbers
    (2) occurrences are independent
    (3) the average frequency of occurrence for the time period is known
    (4) it is possible to count how many events have occurred

• $\lambda$ 代
  $\frac{1}{\mu }$ : 這邊的意思拿 CPY 來說就是平均每 5974.116 個 cycle 可以完成一次搜尋

• 但是為了做圖方便所以將 5974.116 (cycles) 為一個單位時間，這樣

  $\lambda$ 代 1
  

• 放大版
  

• ｉｄｅａｌ　為階梯狀的原因是因為　5974.116（ｃｙｃｌｅｓ） 為一個單位，然後公式裏面又有　ｋ　階層，所以在小數的部份會被忽略，但　ｒｅａｌ　的部份又是　1個　ｃｙｃｌｅ　為單位，我認為這樣是不好的製圖方式，我應該要以　5974.116（ｃｙｃｌｅｓ）　為單位製圖才比較容易觀察差異

• 以　5974.116（ｃｙｃｌｅｓ） 為一個單位製圖
  

• 這樣看來就可以確定　ＣＰＹ　比起　Ｎｏｒｍａｌ distribution　確實比較像　Poisson distribution

• 代入　Poisson　的　95%　confidence interval

  • 參考 How to calculate a confidence level for a Poisson distribution?

• 兩者的 95% 信賴區間

  • CPY　= 5477.26　～　6947.76 (cycles)
  • ＲＥＦ（+ｍｅｍｏｒｙ　ｐｏｏｌ） ＝　46.177　～　85.593 (cycles)

作業要求

• 在 GitHub 上 fork prefix-search，並修改 Makefile 以允許 $ make bench 時，可對 ternary search tree 的實作做出效能評比，涵蓋建立 tst 和 prefix search 的時間，應比照 clz 透過統計模型，取出 95% 信賴區間
  • 測試程式碼應該接受 --bench 的執行參數，得以在沒有使用者輸入的前題下，對 tst 程式碼進行效能分析，應涵蓋 cpy 和 ref 兩種途徑 (詳情參閱 tst.h 的程式碼註解)
  • 解釋 tst 的優點和引入 tst 到電話簿或戶政管理系統的適用性
• 修改 test＿ref.c，參照裡頭標註 FIXME 的部分，替換成真正有效的 API 和對應的程式碼，這裡要求你學習分析現有的程式碼並得以擴充
• 分析 test_cpy 和 test_ref 兩種方式 (copy/reference) 的效能，並且針對現代處理器架構，提出效能改善機制
• 指出目前實作中，針對各國城市的 prefix search 有無缺陷呢？比方說無法區分城市和國家，並提出具體程式碼的修正
• 新增 phonebook.c，將之前 phonebook 的基礎工作引入，透過 ternary search tree 讓電話簿程式得以更符合人性，當使用者新增資料時，可以在居住地透過 prefix search 找出最接近的城市並避免輸入錯誤
  • 應該要能夠切換 command line interface (CLI) 和 benchmarking 模式
  • 允許程式碼產生的隨機輸入，讓 tst 自動找到匹配的國家和城市名稱
  • 以上述機率分佈函數來解釋，並且提出改善猜測精準度的方案
• 研究程式碼的 tst_traverse_fn 函式，並思考如何運用這個實作，注意到 callback function 的程式開發技巧/模式
• 將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「作業區」

截止日期

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