# 2018q1 Homework2 (prefix-search)
contributed by <`afcidk`>
[作業要求](https://hackmd.io/s/ByFWoR_tz#)
## 閱讀材料：
* [Makefile header 檔的相依性檢查](https://yodalee.blogspot.tw/2017/04/makefile-header.html)
* [C03: clz](https://hackmd.io/s/Hyl9-PrjW#)
## 系統環境
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 94
Model name: Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
Stepping: 3
CPU MHz: 2700.000
CPU max MHz: 3300.0000
CPU min MHz: 800.0000
BogoMIPS: 5424.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-3
```
## 理解 Ternary Search Tree
上課時老師有提供 [Ternary Search Tree 視覺化](https://www.cs.usfca.edu/~galles/visualization/TST.html)的網站，但是當時只是看動畫的運作有點不太清楚他到底根據什麼條件儲存資料的。
後來在 [Wikipedia](https://en.wikipedia.org/wiki/Ternary_search_tree) 看到下面這段話。很簡短的一句話直接讓我對 Ternary Search Tree 怎麼儲存有了一定的想法。
> All strings in the middle subtree of a node start with that prefix.
```
搭配這張圖
c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s as, at, cute, cup, he, i, us
```
Ternary search tree 只會有三個 child，分別把他們叫做 low child, middle child, high child
他們的特性
* low child: 儲存比 parent 小的字元
* middle child: 儲存字串的下一個字元
* high child: 儲存比 parent 大的字元
在第一次的作業 [phonebook](https://hackmd.io/s/HJpd6KXdG#%E5%98%97%E8%A9%A64-%E4%BD%BF%E7%94%A8-trie-%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B) 中，我已經有嘗試過使用 trie 來加速 `findName()` 的速度，但是缺點就是會很浪費空間。
Ternary search tree 利用 Binary tree 儲存連向其他資料的『邊』，和使用陣列預先配置一堆記憶體空間的方法相比，在記憶體空間上使用效率比較高。
參考資料：
* [Ternary search tree (Wikipedia)](https://en.wikipedia.org/wiki/Ternary_search_tree)
## 修改 Makefile
* 在需要重新編譯檔案時順便利用 astyle 檢查排版
```
%.o: %.c
@astyle --style=kr --indent=spaces=4 --indent-switches --suffix=none $*.c
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
```
* 增加 target `bench`
## 修改實做缺陷
* 名稱有誤，影響到搜尋結果
* 城市中間有空白會被分開
* 逗號會被加到城市名稱裡面
可以利用 fscanf 裡類似正規表達式的特殊寫法直接找出字串裡的程式名稱和國家名稱
把原本的`%s` 改成 `%256[^,], %256[^\n]\n`
其中`[^\n]`代表的是不包含 `\n` 字元，詳細說明可以參考 [fprintf 的 man page](https://linux.die.net/man/3/fscanf)
* `tst.c` 裡的 `tst_suggest()` 在搜尋 `A` 的時候會產生問題
紀錄 prefix search 的字元陣列大小超過限制，導致 Segmentation fault 。還沒有找到為什麼會 `tst_suggest` 裡的 `n` 會超過 1024，下面有紀錄暫時的解決方法。
## 修改 `test_ref.c`
### FIXME
在 `test_ref.c` 檔案裡面有三處 FIXME 提醒我們要更改程式碼。一開始看那段註解還是看不太懂要做什麼。
後來看到了 `raygoah` 同學的[共筆](https://hackmd.io/dwDOR7H2Q8qyxGxSOsc-vA?view#)，才突然發現到函式 `tst_ins_del()` 原先裡面的參數並不是我們希望放入的參數。
查閱 `tst.h` 裡面對於 `tst_ins_del` 的註解，從第一句話
`tst_ins_del() ins/del copy or reference of 's' from ternary search tree`
可以知道，這個函式可以選擇要 插入/刪除 tst 裡面的 copy 或是 reference
:::warning
我現在還是不太懂 copy 和 reference 在這裡到底是什麼意思
:::
:::info
看了 `tst.c` 裡面的程式碼，確定 copy 指的是整個字串，reference 會是字串的參照位址（可能在某處已經配置空間過了）
:::
> 看了 tst.h 裡面的註解後覺得英文好難，應該是因為每個人的表達方式都不太一樣。看到不習慣的表達方式除了不習慣還是不習慣，不過有註解總比沒註解還要好 QQ
回到 `test_ref.c`，FIXME 的註解要求我們插入每個字串的參照( reference )
看似把三處的 CPY 改成 REF 就可以了，但是這樣其實是不可行的。
為什麼呢？因為在**第一次的`tst_ins_del()`我們並沒有字串的參照位址**。
在`tst.c` 的實做裡面，可以發現我們使用的 reference 取自第二個參數 `char *const *s` ，但是第一次呼叫 `tst_ins_del()` 時，我們傳入的 s 是相同的位址（`char word[WRDMAX]`）
要解決這個問題，我們只要手動配置空間，並把字串放進去就可以了，函式 `strdup()` 可以幫我們做到這件事。
### 發現 prefix search 查詢 A 的時候會 segmentation fault
```
(gdb) r
Starting program: /home/afcidk/prefix-search/test_ref
ternary_tree, loaded 259112 words in 0.118815 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: s
find words matching prefix (at least 1 char): A
Program received signal SIGSEGV, Segmentation fault.
0x000055555555613d in tst_suggest (p=0x5555574afd70, c=65 'A', nchr=1, a=0x7fffffffbde0,
n=0x7fffffffbd94, max=1024) at tst.c:330
330 a[(*n)++] = (char *) p->eqkid;
(gdb) p (*n)
$1 = 1605
```
印出 n 的時候發現 n 的數字大於我們設定的上限（1024）
在 `tst_suggest` 裡面判斷式 `*n==max` 應該要改為 `*n>=max`，但是我還沒找到為什麼不能只判斷等於就好了。
:::warning
其實這樣改還是不符合我們預期的結果，可以發現 prefix search A 的時候建議的字串總共有 1025 個，但是預期的是只顯示 1024 個字串而已。
:::
### 增加效能評比功能
在載入資料後，利用 argc (argument count) 和 argv (argument vector) 來判斷是否進入效能評比的模式。
目標： 建立 tst tree 和 prefix search 所花費的時間
我留下 `cities.txt` 裡面的前 15000 筆資料用來測試 prefix search
看起來 ref 版本花費的時間比 cpy 版本還要多
## `tst_traverse_fn` 函式
函式裡面有一個 if/else 判斷式，判斷現在的 node 是不是空的（字串結尾的意思），又依序從 lokid, eqkid 到 hikid 各呼叫一次。因此判斷`tst_traverse_fn()` 應該是用來遍歷整棵 tst tree 的函式。
`fn()` 根據想要做的事情可以放不同的函式，類似的函式像是 [qsort](https://linux.die.net/man/3/qsort) 也可以自行定義排序的方式。
### 實際使用時機
* 可以用來觀察遍歷所有的資料需要多少時間
## 參考資料
* [`tina0405` 的共筆](https://hackmd.io/mI8HxMMJRqy_I2BmDzZWAQ#)
Sign in with Wallet
Connect another wallet