# C04: prefix-search
###### tags: `sysprog2017`

:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2017 年系統軟體課程](https://www.facebook.com/groups/system.software2017/)
:mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表
:::
## 預期目標

* 學習 [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree) 作為 [auto-complete](https://en.wikipedia.org/wiki/Autocomplete) 和 prefix search 的實作機制
* 延續 [phonebook](https://hackmd.io/s/HJJUmdXsZ) 的基礎工作，引入 [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree) 讓電話簿程式得以更符合人性
* 配合 Week3 進度，思考針對現代處理器特性的高效能程式設計議題
* 設計效能評比 (benchmark) 的程式框架
* 學習 GNU make 的進階技巧
* 學習物件導向程式開發思維

## [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree)

* 取得 [prefix-search](https://github.com/sysprog21/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` 就由你去探索具體作用

## 物件導向程式開發

* 研讀「所不知道的 C 語言」的 [物件導向程式設計篇](https://hackmd.io/s/HJLyQaQMl) 和 [技巧篇](https://hackmd.io/s/HyIdoLnjl) (都有錄影可對照)
* 物件導向是一種態度
* 善用 forward declaration 與 function pointer，用 C 語言實現 Encapsulation
* 案例探討: oltk
* Design Patterns: 抽象化各種常見的問題，並提供抽象化的解決方案

## GNU Make 的技巧

* 參見 [Makefile header 檔的相依性檢查](https://yodalee.blogspot.tw/2017/04/makefile-header.html)

## 作業要求

* 在 GitHub 上 fork [prefix-search](https://github.com/sysprog21/prefix-search)，並修改 `Makefile` 以允許 `$ make bench` 時，可對 ternary search tree 的實作做出效能評比，涵蓋建立 tst 和 prefix search 的時間，應比照 [clz](https://hackmd.io/s/Hyl9-PrjW) 透過統計模型，取出 95% 信賴區間
* 測試程式碼應該接受 `--bench` 的執行參數，得以在沒有使用者輸入的前題下，對 tst 程式碼進行效能分析，應涵蓋 `cpy` 和 `ref` 兩種途徑 (詳情參閱 `tst.h` 的程式碼註解)
* 解釋 tst 的優點和引入 tst 到電話簿或戶政管理系統的適用性
* 修改 [test＿ref.c](https://github.com/sysprog21/prefix-search/blob/master/test_ref.c)，參照裡頭標註 `TODO` 的部分，替換成真正有效的 API 和對應的程式碼，這裡要求你學習分析現有的程式碼並得以擴充
* 分析 `test_cpy` 和 `test_ref` 兩種方式 (copy/reference) 的效能，並且針對現代處理器架構，提出效能改善機制
* 指出目前實作中，針對各國城市的 prefix search 有無缺陷呢？比方說無法區分城市和國家，並提出具體程式碼的修正
* 引入 [phonebook](https://hackmd.io/s/HJJUmdXsZ) 的基礎工作，透過 [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree) 讓電話簿程式得以更符合人性，當使用者新增資料時，可以在居住地透過 prefix search 找出最接近的城市並避免輸入錯誤
* 詳細觀察 `tst.h` 和 `tst.c` 為何要 forward declaration 呢？分離介面和實作有何好處呢？這樣的思維又該如何運用於 [phonebook](https://hackmd.io/s/HJJUmdXsZ) 呢？提出想法並且實作
* 研究程式碼的 `tst_traverse_fn` 函式，並思考如何運用這個實作，注意到 [callback function](https://en.wikipedia.org/wiki/Callback_(computer_programming)) 的程式開發技巧/模式
* 將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/HkVvxOD2-)」

## 截止日期

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