# 2017q3 Homework2 (作業區)
## C04 : Prefix-search
##### tags :`williamchangTW`
---
### 開發環境
~~~
Architecture: i686
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 37
Model name: Intel(R) Core(TM) i5 CPU 650 @ 3.20GHz
製程： 5
CPU MHz： 1200.000
CPU max MHz: 3201.0000
CPU min MHz: 1200.0000
BogoMIPS: 6383.71
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 4096K
~~~
>請先列出開發環境
>[name=課程助教][color=red]
>>已補上謝謝[name=williamchangTW][color=blue]
---
### 一開始的準備
請根據以下內容準備。
### 新增資料
+ 第一行
+ 第二行
+ 第三行
+ 第四行
+ 第五行
##### processing problem
- 一開始遇到的問題：當我 `make` 時，在終端機出現以下問題：
~~~c=
test_cpy.c: In function 'main':
test_cpy.c:124:17:error: 'for' loop initial declaration are only allowed in C99 mode
for (int i = 0; i < sidx; i++)
test_cpy.c:124:17: note: use option -std=c99 or -std=gnu99 to compile your code
make: *** [test_cpy.o] Error 1
~~~
- 而我去找了資料後給了兩個方法，問題出現在 `test_cpy.c` & `test_ref.c`：
- `gcc -std=c99 test_cpy.c`
- `gedit test_cpy.c file` & add line below
~~~c=
int i;
for (i = 0; i < stdx; i++)
~~~
- 我選擇後者，先宣告`int i`在做`for loop`
### Ternary search tree (TST)
- 再來我先看了 [ternary search tree](https://en.wikipedia.org/wiki/Ternary_search_tree) ，針對其定義做一些重點標記：
- 最多三個子代
- 是 [tries](https://en.wikipedia.org/wiki/Trie)的一種
- lower than Prefix-search but more space-efficiency
- Insertion random order 常常造出 well-blanced tree
- 跟 BST 比， TST 以速度為代價，搜尋空間的效率更高，但不像 tries 一樣浪費空間又有其速度快為優點
- [Hash tables](https://en.wikipedia.org/wiki/Hash_table) 不允許多個 ternary-search-tree 因為 hash maps 經常性的使用較大的記憶體範圍 但不像 tries 一樣多，因為 hash maps 需要把整個資料都搜尋過一遍，不像 TST 一樣只需搜尋較少的字元，相對較慢
- 可用 [Associative map](https://en.wikipedia.org/wiki/Associative_array) 結構，有效率的解決增長的 [String search algorithm](https://en.wikipedia.org/wiki/String_searching_algorithm)
- 可以用在 spell checker & auto-completion
- 與程式碼對照，這裡插入一點解釋針對三個 child 出現的地方
~~~c=
//tst.c file
typedef struct tst_node {
char key;
unsigned refcnt;
struct tst_node *lokid;
struct tst_node *eqkid;
struct tst_node *hikid;
} tst_node;
~~~
- 我們預設字母 A~Z 的排序
- `lower child < search value` => *lokid
- `equal child = search value` => *erqkid
- `higher child > search value` => *hikid
---
- Time Complexity
| | Average-case running time | Worst-case running time |
|:------:|:-----------:|:--------:|
| Lookup | O(logn) | O(n)|
| Insertion | O(logn) |O(n)|
| Delete | O(logn) |O(n)|
> 改用 HackMD 的語法重制上圖
> [name="jserv"][color=red]
> > 已修正，謝謝
> > [name="williamchangTW"][color=blue]
- spell checker 因為 TST 為 tries 的一種，所以可以找尋相關字比如可以找出錯誤的地方然後取相關字。
---
- Auto-completion 這裡很明顯的可以看出他是如何在 TST 上運作的，子代都是其父代的相關聯字
---
- 找字系統如同 google search
---
最後做總結，參考了[link](http://www.drdobbs.com/database/ternary-search-trees/184410528?pgno=1)：
- 優點：
- 搜尋空間效率更高
- 有 binary search tree 空間利用上的優點以及 trie 搜尋速度上的優勢
- 效率高而且容易实现
- 效率比 hash 快，當資料相當大 collision increase
- 增加及減少資料容易，若 hash 改變大小則要重新操作
- 可以作為字典輸出，trie也能做，不过很费时
---
#### 針對 Tries 做解釋（跟題目相關連度高）
- 是一個**動態配置**或**關聯性配置**的資料結構，常用於 String
- 優點：
- 搜尋速度快
- 從父親開始，其子代下去都是以他為開頭的相關性子代，所以相連性強，e.g t(parent)->ta(child)
- 樹根是 empty string
- 是一個 prefix-search of space-optmized presentation
- 可以應用在 hash tables
- 在 worst case 中可達到 O(m)，其中 m 為字串最長長度，比 hash table time complexity batter ， 因為 hash table 有 collision problem ，因此 worst case bound in O(n)，顯得比較好一些
- 沒有 collision event
- bucket 的一個值能對應到多個值
- 不需提供 hash function or change，當有更多的值加入時
- 可提供按照字母順序的搜尋
- 缺點：
- 在一些事件上搜尋的時間較慢，當直接面對 hard disk 做存取時，還有 secondary memory 的 random access time 比較時間較長時
- 有時候空間需求會大於 hash table ，當 memory 要分配給每個字元一個記憶體空間而不是直接分配一塊記憶體給他時
- floating pointer 會造成長鍊的搜尋是無意義的儘管他可以支持 standard IEEE 單精度及倍精度浮點數
- 平均空間需求大
---
## FIXME
- 先看一開始給的資訊
~~~c=
enum { INS, DEL, WRDMAX = 256, STKMAX = 512, LMAX = 1024 };
#define REF INS
#define CPY DEL
~~~
enum 是列舉，用來宣告元素定義整數，根據規範若沒有賦予其值，就是 0->1->2...以此類推，所以目前 INS = 0 = REF ， DEL = 1 = CPY
- 把 REF 改成 1 觀察其輸出`#define REF DEL`，明顯出現錯誤
`choice : s`
~~~
suggest[1001] : Ta
suggest[1002] : Ta
suggest[1003] : Ta
suggest[1004] : Ta
suggest[1005] : Ta
suggest[1006] : Ta
suggest[1007] : Ta
suggest[1008] : Ta
suggest[1009] : Ta
suggest[1010] : Ta
suggest[1011] : Ta
suggest[1012] : Ta
suggest[1013] : Ta
suggest[1014] : Ta
suggest[1015] : Ta
suggest[1016] : Ta
suggest[1017] : Ta
suggest[1018] : Ta
suggest[1019] : Ta
suggest[1020] : Ta
suggest[1021] : Ta
suggest[1022] : Ta
suggest[1023] : Ta
~~~
>>只有輸出 `fscanf,%S,word` 所取得的長度，很明顯的沒有傳入整串字串給其輸出
- 原本輸出應為
~~~
suggest[947] : Taylorsville,
suggest[948] : Taylorville,
suggest[949] : Tayoltita,
suggest[950] : Taypano,
suggest[951] : Tayport,
suggest[952] : Taysan,
suggest[953] : Tayshet,
suggest[954] : Taytay,
suggest[955] : Taytayan,
suggest[956] : Taytsy,
suggest[957] : Tayturka,
suggest[958] : Tayu,
suggest[959] : Tayud,
suggest[960] : Tayug,
suggest[961] : Tayum,
suggest[962] : Tayuman,
suggest[963] : Taywanak
suggest[964] : Tayzhina,
suggest[965] : Taza,
suggest[966] : Tazacorte,
suggest[967] : Tazewell,
suggest[968] : Tazlău,
suggest[969] : Tazoult-Lambese,
suggest[970] : Tazovskiy,
~~~
- 從錯誤的地方開始著手，`choice : s` 的時候發生錯誤
```c=
for (int i = 0; i < sidx; i++)
printf("suggest[%d] : %s\n", i, sgl[i]);
```
可見它是輸出 sgl[i] 內的內容，而 i 是它找到的數字內有的，它是關聯性記憶體配置，所以在附近的都是關聯性教高的
- 查找 sgl[] 內的資料如何生成，不應該指現單一字頭，往上找 tst_ins_del 函式，在 tst.c 檔中發現一段程式碼中出現了 CPY
>>在上述中有提到 CPY 的值可能為 1 or 0，若我要跑 CPY 程式則設 1 ，反之則 0，這邊的 CPY 是由 test_ref.c 所提供，所以我把程式裡的 CPY changed to REF
~~~c=
if (*p++ == 0) {
if (cpy) { /* allocate storage for 's' */
const char *eqdata = strdup(*s);
if (!eqdata)
return NULL;
curr->eqkid = (tst_node *) eqdata;
return (void *) eqdata;
} else { /* save pointer to 's' (allocated elsewhere) */
curr->eqkid = (tst_node *) *s;
return (void *) *s;
}
}
~~~
>>上述程式中，若為 CPY = 1 則會給它一塊記憶體空間存取值，若不為 1 則會走另外一個判斷式，因此錯誤在這個地方
- 先找出 `FIXME` 標注的地方(共3處)
- 把 CPY 換成 REF 可以正常輸出
~~~c=
t1 = tvgetf();
while ((rtn - fscanf(fp, "%s", word)) != EOF) {
char *p - word;
/*FIXME: insert reference to each string*/
if (!tst_ins_del(&root, &p, INS, CPY)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
}
~~~
- 找到 tst.h 中有他宣告的格式，`int cpy`維持不變
~~~c=
void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy);
~~~
- 參考其註解，得知以下重點：
- 其中 's' 為從 scanf 中取得，存入word中之值
- 有兩個動作一個刪除一個增加
- 一開始存入所有點到 leaf
- 若 'del' 不為空值則刪除該值
- 'cpy' 若沒有配置記憶體給 's' 否則 save pointer to 's'，若已存在該字串，則增加 node->refcnt 然後回傳該值
- refcnt 在 tst.h 中有宣告該格式
~~~c=
unsigned tst_get_refcnt(const tst_node *node);
~~~
- 在 tst.c 有它做了什麼動作，可以拿來使用
~~~c=
unsigned tst_get_refcnt(const tst_node *node)
{
return node->refcnt;
}
~~~
---
## test_cpy & test_ref compare
- 在還沒做出任何改變時兩個檔案效能資訊，沒有太大的差異
`perf stat ./test_ref`
~~~
225.444266 task-clock (msec) # 0.024 CPUs utilized
25 context-switches # 0.111 K/sec
2 cpu-migrations # 0.009 K/sec
6,615 page-faults # 0.029 M/sec
773,503,788 cycles # 3.431 GHz (82.26%)
67,672,385 stalled-cycles-frontend # 8.75% frontend cycles idle (83.88%)
304,831,532 stalled-cycles-backend # 39.41% backend cycles idle (34.86%)
549,998,612 instructions # 0.71 insns per cycle
# 0.55 stalled cycles per insn (50.80%)
108,195,625 branches # 479.922 M/sec (66.50%)
3,064,576 branch-misses # 2.83% of all branches (82.95%)
9.289633678 seconds time elapsed
~~~
`perf stat ./test_cpy`
~~~
226.348106 task-clock (msec) # 0.034 CPUs utilized
22 context-switches # 0.097 K/sec
2 cpu-migrations # 0.009 K/sec
6,614 page-faults # 0.029 M/sec
745,684,917 cycles # 3.294 GHz (82.32%)
64,710,984 stalled-cycles-frontend # 8.68% frontend cycles idle (82.35%)
301,841,280 stalled-cycles-backend # 40.48% backend cycles idle (35.89%)
540,944,385 instructions # 0.73 insns per cycle
# 0.56 stalled cycles per insn (53.77%)
109,386,057 branches # 483.265 M/sec (68.70%)
2,994,135 branch-misses # 2.74% of all branches (84.59%)
6.668136718 seconds time elapsed
~~~
> 文字訊息請避免用圖片表示
> [name="jserv"][color=red]
>> 好的老師，已經全數換成字來顯示資訊
>> [name="williamchangTW"][color=blue]
---
## 程式與國家問題
- 觀察 cities.txt file，`Taipei , Tiawan`有一件事可以作為區隔城市與國家，當中用`"，"`區隔開來，想法是可以利用此分割點作為讀區到此點及返回找城市，或從此點開始對後面做搜尋找國家
---
## Prefix-search changes where is not suitable
- 使用過後大概題一下所有的功能簡介:
- a 隨意加入你想加入的資料
- f 一定要打完整的字且大小寫有分，因為在 [ASCII](https://zh.wikipedia.org/wiki/ASCII) 中，英文字母的大小寫呈現方式不一樣，所以必須區分大小寫，值得提醒的一點無法找城市，只能找國家
- s prefix-search 的找，無法區分城市跟國家，找出所有相符的資料出來
- d 隨意的刪除資料
- q 結束
---
## why used forward declaration
~~- [Forward Declaration](http://justbeahacker.blogspot.tw/2015/02/cc-forward-declaration.html) 根據其中提到的觀點，可以了解到為什麼要使用這個技巧，因為可以避免不必要的重新定義，當專案大到一定的程度時，會嚴重拖延編譯的時間，影響效能~~
:::danger
1. 這說法太片面，而且事實上編譯器技術進步很多，上述考量已經不是重點了
2. 用物件導向和軟體模組化的觀點來回覆
:notes: jserv
:::
- 在研讀[你所部知道的C語言：物件導向篇](https://hackmd.io/s/HJLyQaQMl#)得了以下幾點的重點及吸收：
- [Encapsulation](https://en.wikipedia.org/wiki/Encapsulation_(computer_programming))在此篇了解到，**物件導向**是一種包裝技術，將實體細節隱藏起來而不去讓使用者更動它
- **Alias**這個名詞曾經在白算盤書中看到，在那裡稱之為`"Aliasing problem"`簡易而論，也就是資訊不對稱，有可能同時存取同樣記憶體位置，當其中一方改變，而另一方拿取錯誤的資訊，造成不如預期的錯誤稱之
> 列出論文時，應該明確提及標題 (+超連結) [Glib-C: C as an alternative Object OrientedEnvironment](http://lore.ua.ac.be/Publications/pdf/Hendrickx2004.pdf)。論文閱讀和內文摘要是大學生很重要的訓練，可試著先把重點列出 (就像你已經做的事) 並透過實例解說和討論
> [name="jserv"][color=red]
> >已更正此部份所發生的不明確問題，並於其他地方發生過類似問題的地方做修正
> >[name="williamchangTW"][color=blue]
- 在詳讀 [Glib-C: C as an alternative Object OrientedEnvironment](http://lore.ua.ac.be/Publications/pdf/Hendrickx2004.pdf) 頁數介於 3~13 對於 OO 詳細解釋後歸內出以下幾點
- Objected-Oriented is sort of **trap.**
- Encapsulation ,objects, classes, inheritance and polymorph-ism may be regarded as the essential basic for OO.
- Encapsulation and data hiding is important for OO.
- An object is described by a class, where the class describes a type. So **an object is an instance of such a type.**
- Inheritance is concept in which **a type can be extended: a type can be specialized.**
- Polymorph-ism in the context of traditional OOPLs is the possibility of an object to take different forms at **runtime**
- Exception handling, garbage collecting, bulit-in operator overloading, runtime intrspection and reflection are kind of OO.
- **Garbage collection**系統在執行中把未用到的記憶體，開發者手動的管理它
- **ADT**是 OO 的子集合，稱之為 Object Base programming
---
## 作業要求
* 在 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，評分越高
Sign in with Wallet
Connect another wallet