2017q3 Homework2(prefix-search)
========
contributed by <`loolofen`>
### Reviewed by `HexRabbit`
* **Trie 介紹** 「但是因為沒有共同前綴（ prefix ），所以耗費空間十分龐大」，敘述錯誤，Trie 跟 Ternary Search Tree 的其中一個相似點就是共同前綴，且空間龐大是因其產生的大量空指標造成。
* **Ternary search tree 介紹** 引用的TST圖表結構與作業中的實做不同，建議做出提示。
(思考先插入 cat 再 cats 的情況 string 的位置)
* **test_ref 修正**「發現應該是要 free 掉 data storage external，而不是 data storage internal」，「看起來是沒有 free 到正確的 pointer」，用詞過於模糊，
無法從字面上理解究竟修正了什麼以及有什麼差別。
* **memory pool改進** 需要更多數據，圖表，分析！
## trie 及 ternary serch tree 介紹
### trie
又稱為字典樹，是一種多分支的樹狀結構，像是英文單字就是有26個分支（a-z），阿拉伯數字就是10個分（0-9）。
e.g. 假設某字串只有五種字元(a,b,c,d,e)組合而成，那麼其trie結構如以下
~~不過此種方法雖然簡單好實現，但是因為沒有共同前綴（ prefix ），所以耗費空間十分龐大，如果電腦還要支援其它字元型態累積的耗費空間更是大中加大。~~
空間龐大是因其產生的大量空指標造成。
trie 其特性如以下 ：
1. 根節點不包含字元，除根節點以外，每個節點只包含一種字元。
2. 從根節點到某個節點，路徑上經過的字元連起來，就是該節點所對應的字串，
3. 每個節點的子節點所包含的字串都不相同。
### ternary serch tree
和 trie 結構類似，但其每個節點只有三個分支，所以在進行插入節點操作的時候，只需判斷插入字元與當前節點關係（大於、小於、等於），結合了 trie 及 binary serch tree 的優點。
依查尋到的資料整理出幾個分類原則
1. left pointer : 插入值比所經節點值小，則存取 left pointer。
2. equal pointer : 插入值和所經節點值相等，則以插入字串的下一個字元存取 equal pointer。
3. right pointer : 插入值比所經節點值大，則存取 right pointer。
4. 若存取時遇到空節點，則插入字元，並存取 equal pointer 。
e.g. 插入方法如以下，若有四個單字 CAT，BUG，CATS，UP 按照順序插入。
1. 字串 C A T ，根節點為空節點插入 C，並存取 equal pointer，之後一一插入字元
2. 字串 B U G ，和根節點 C 比較，由於較小所以存取 left pointer 之後一一插入字元
3. 字串 C A T S ，和根節點 C 比較，由於相等所以以插入字串的下一個字元存取 equal pointer
4. 字串 U P ， 和根節點比較，由於較大所以存取 right pointer 之後一一插入字元
### 參考資料
[演算法筆記](http://www.cnblogs.com/edwinchen/p/4580190.html)
[ternary serch tree](http://www.geeksforgeeks.org/ternary-search-tree/)
## 作業探討
### 開發環境
使用 lscpu 查看CPU、快取內容
```
Ubuntu 16.04.1 LTS
CPU:Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
```
### 修改 test_ref.c
以下參考'st9007a'同學共筆
打開 test_ref.c 把所有 FIXME 底下的 CPY 皆改成 REF 並編譯得到以下結果。
輸入 Tain 就全部都出現 Tain 根本看不出 array 包含的內容。
```=
find words matching prefix (at least 1 char): Tain
Tain - searched prefix in 0.000007 sec
suggest[0] : Tain
suggest[1] : Tain
suggest[2] : Tain
suggest[3] : Tain
suggest[4] : Tain
suggest[5] : Tain
suggest[6] : Tain
suggest[7] : Tain
suggest[8] : Tain
suggest[9] : Tain
suggest[10] : Tain
suggest[11] : Tain
```
觀察以下 code 發現， cpy = 0 時，*s 會存入 curr->eqkid 中，而在 test_ref.c 中 ， *s 對映到的是 word 。
因此 test_ref.c 中，所有 insert 操作的節點都存到以 word 為起點的連續記憶體位址的其中一個位址。
所以選用 strdup() ，其會先用 malloc() 配置與 word 相同的空間 ，存入到此位址，然後反回位址值。如此就可以讓他們的位址皆不同。
但每個都要配置額外的空間給他，此種方法十分沒有效率，也很容易增加 ~~cash~~ cache miss 的機會。
```=
void *tst_ins_del(tst_node **root, char *const *s, const int del, const int cpy)
{
...
for (;;) {
...
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;
}
}
pcurr = &(curr->eqkid);
}
}
```
參考 `ChiuYiTang`同學共筆，發現單純把 CPY 修改成 REF 在 q 會有錯誤
```
*** Error in `./test_ref': free(): invalid pointer: 0xbfc3e3dc ***
```
以上錯誤看起來是沒有 free 到正確的 pointer。
所以觀查 tst.c 中的 tst_free_all () 發現還有一個 tst_free () 發現應該是要 free 掉 data storage external，而不是 data storage internal。
修改成以下，即可正常運作。
```=
case 'q':
tst_free(root);
return 0;
break;
```
### memory pool
參考 `ChiuYiTang` 同學共筆，引入 memory pool 的概念，給定一個經過需求精算過的記憶體空間。
:::danger
1. 「經過需求精算」是怎麼一回事？請算給我們看
2. 重新把定義找出來
:notes: jserv
:::
優點如以下 ：
* 避免造成 memory fragmentation
* 避免了配置和釋放記憶體所花費的效能問題
* 記憶體間是緊密相鄰的，所以能提高系統cache命中率，進而提高軟體效能
不過缺點是在執行期間會一直佔用資源。
```Clike
/* the memory pool size */
#define MemoryPool 10000000
...
char *pptr = (char *) malloc(MemoryPool * sizeof(char));
char *pTop = pptr;
...
/* Use memory pool top pointer to insert reference to each string */
while ((rtn = fscanf(fp, "%s", pTop)) != EOF) {
char *p = pTop;
if (!tst_ins_del(&root, &p, INS, REF)) {
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
}
idx++;
pTop += (strlen(pTop) + 1);/* If memory exhausted, pTop++ for next memory */
}
t2 = tvgetf();
...
```
### 參考資料
[ChiuYiTang 同學共筆](https://hackmd.io/s/ByeocUhnZ#)
[st9007a 同學共筆](https://hackmd.io/s/SkeKQEq3Z#)
Sign in with Wallet
Connect another wallet