2017q3 Homework1(prefix-search)
===
contributed by <`TsengWen`>
## 作業要求
* 在 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-)」
## 建立tst時間
### [Github](https://github.com/TsengWen/prefix-search)
### 想法
- cities insert的順序如果不相同,所建tst所需的時間不相同
#### 使用 shuf 打亂順序

$ shuf cities.txt -o cities1.txt

:::danger
使用外部工具時，檢驗過亂數分佈了嗎？是 PRNG，抑或能有更好的分佈呢？
:notes: 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過的時間都是有明顯降低
:::danger
1. 避免用「有時候」這種不精確的話，理工人這樣做事嗎？及早脫離文組^TM^
2. 你需要詳細描述測試方法 (以及對應的理論，機率統計學過)，並確保這樣的實驗得以「解讀」，需要量化

:notes: jserv
:::

- [github](https://github.com/TsengWen/prefix-search/tree/Sort)

## REF 修改

### 參考
- [st9007a同學](https://hackmd.io/s/SkeKQEq3Z)

### 過程
- 試著尋找改成REF之後所出現的問題原因，大概的想法是結束時給的空間為word的空間是不正確的。
:::danger
1. 上面這是合理的中文描述嗎？找出問題，卻講不清楚，根本不該是理工人的行為，重寫！
2. Git commit messages 寫不好，這是我們不能接受的事，重新閱讀指教材並且強化表達。修改記錄都無法寫好，實在無法想像日後如何做研究

:notes: jserv
:::

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