2017q3 Homework1(prefix-search)

contributed by <TsengWen>

作業要求

在 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 製圖，紀錄於「作業區」

建立tst時間

Github

想法

cities insert的順序如果不相同,所建tst所需的時間不相同

使用 shuf 打亂順序

$ shuf cities.txt -o cities1.txt

使用外部工具時，檢驗過亂數分佈了嗎？是 PRNG，抑或能有更好的分佈呢？
jserv

使用sort先排序過

$ sort -g cities.txt -o cities2.txt

比較三種所花的時間

ternary_tree, loaded 259112 words in 0.136866 sec
shuffle, loaded 259112 words in 0.118725 sec
sort, loaded 259112 words in 0.094033 sec

打亂過的還會比原本時間較長？？
不過預先sort過的時間都是有明顯降低

避免用「有時候」這種不精確的話，理工人這樣做事嗎？及早脫離文組^TM
你需要詳細描述測試方法 (以及對應的理論，機率統計學過)，並確保這樣的實驗得以「解讀」，需要量化

jserv

github

REF 修改

參考

st9007a同學

過程

試著尋找改成REF之後所出現的問題原因，大概的想法是結束時給的空間為word的空間是不正確的。

上面這是合理的中文描述嗎？找出問題，卻講不清楚，根本不該是理工人的行為，重寫！
Git commit messages 寫不好，這是我們不能接受的事，重新閱讀指教材並且強化表達。修改記錄都無法寫好，實在無法想像日後如何做研究

jserv

後來發現fscanf(),擷取到空格為止，許多城市名稱不夠完整，所以改成fget()一行一行取。