744 views
# 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) 程式碼,編譯並測試 ```shell $ 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,評分越高