Try   HackMD

C04: prefix-search

tags: sysprog2017

主講人: jserv / 課程討論區: 2017 年系統軟體課程
:mega: 返回「進階電腦系統理論與實作」課程進度表

預期目標

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

ternary search tree

$ 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 語言」的 物件導向程式設計篇 和 技巧篇 (都有錄影可對照)
  • 物件導向是一種態度
  • 善用 forward declaration 與 function pointer，用 C 語言實現 Encapsulation
  • 案例探討: oltk
  • Design Patterns: 抽象化各種常見的問題，並提供抽象化的解決方案

GNU Make 的技巧

作業要求

  • 在 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，參照裡頭標註 TODO 的部分，替換成真正有效的 API 和對應的程式碼，這裡要求你學習分析現有的程式碼並得以擴充
  • 分析 test_cpy 和 test_ref 兩種方式 (copy/reference) 的效能，並且針對現代處理器架構，提出效能改善機制
  • 指出目前實作中，針對各國城市的 prefix search 有無缺陷呢？比方說無法區分城市和國家，並提出具體程式碼的修正
  • 引入 phonebook 的基礎工作，透過 ternary search tree 讓電話簿程式得以更符合人性，當使用者新增資料時，可以在居住地透過 prefix search 找出最接近的城市並避免輸入錯誤
  • 詳細觀察 tst.h 和 tst.c 為何要 forward declaration 呢？分離介面和實作有何好處呢？這樣的思維又該如何運用於 phonebook 呢？提出想法並且實作
  • 研究程式碼的 tst_traverse_fn 函式，並思考如何運用這個實作，注意到 callback function 的程式開發技巧/模式
  • 將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「作業區」

截止日期

  • Oct 16, 2017 (含) 之前
  • 越早在 GitHub 上有動態、越早接受 code review，評分越高
Last changed by 
 
Jim Huang
0
1983
Published on HackMD