Phonebook案例分析
===
# 架環境
先架構起可以運行作業所需要的環境
我在電腦中安裝的是ubuntu14.04的版本
---
# Gunplot印不出優化解決辦法
前幾次再使用語法$make plot時，都只會印出兩條orig的時間條，努力看懂main.c後，找到了問題所在，希望能幫到印不出來的同學
```c
#if defined(OPT)
output = fopen("opt.txt", "a");
#else
output = fopen("orig.txt", "a");
#endif
```
這段程式碼就是讓gunplot印出奇怪東西的原因，但老師原本打的#if defined(OPT)是甚麼意思呢？這邊的指示詞 #if 如果搭配 define 時，就可以再前置處理時檢查是否有此項識別項，這邊的識別項 (identifier) 指的就是 OPT，於是他會檢查 OPT 是否被定義，所以打開phonebook_opt.h，再裡頭加上一行：
```c
#define OPT 1
```
>Hua：這裡想請問老師，這類指示詞的前置處理指的是在程式執行前先判斷嗎？
>>Jim H：OPT 應該定義在 Makefile 中 CFLAGS，請注意看 "-DOPT=" 的設定
>>>HUA-YUAN：
>>>可以在Makefile的CFLAGS中 加上-DOPT="1" 去 define
>>>也可以在*.[ch]裡面寫上 #define OPT 1
>>>但是寫在*.[ch]的彈性沒有比在Makefile中來的好
>>>>Hua：恩恩，我在下面有修改過Makefile了，謝謝同學><
```c
phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h
$(CC) $(CFLAGS_common) $(CFLAGS_opt) \
-DIMPL="\"$@.h\"" -o $@ \
$(SRCS_common) $@.c
```
>Hua：這是Makefile在處理phonebook_opt時的語法，可是我找不到定義OPT
>>Jim H：你要自己定義
>>>Hua：了解！
```c
phonebook_opt: $(SRCS_common) phonebook_opt.c phonebook_opt.h
$(CC) $(CFLAGS_common) $(CFLAGS_opt) \
-DIMPL="\"$@.h\"" -o $@ \
-DOPT="1" \
$(SRCS_common) $@.c
```
直接在Makefile裡修改並定義OPT的值
這裡之後在去嘗試執行make plot就應該會有正確的結果囉 (前提是phonebook_opt.c或.h有做過優化！)
>Hua：如果不想經由 directive 去達成，也可以偷偷修改 main.c 裡的內容，直接透過判斷 IMPL 這個變數值也可以達到一樣的效果，不過要看懂 makefile 裡再幹嘛QQ
----
# 嘗試優化方法
參考過去的課程及開發紀錄，大致上有多種優化方法
1. 縮小資料的struct
2. 利用hash縮小資料量
3. 資料連續排序
4. 利用壓縮字串演算法處理
5. 自己想(努力ing)
# 效能分析
## 未優化版本
針對原本未優化的程式進行perf的分析，可以發現findname( )的使用比率15.77%佔了第3，確實是此程式的「熱點」，而相比之下append反倒只使用了0.84%，但append( )執行時間卻比findname( )多了將近6倍。
```
size of entry : 136 bytes
execution time of append() : 0.031616 sec
execution time of findName() : 0.005111 sec
```
## 優化版本 1 (縮小struct大小)
藉由縮小struct大小來增加裝載在cache裡的資料數，進而降低cache miss
```
size of entry : 32 bytes
execution time of append() : 0.024877 sec
execution time of findName() : 0.001999 sec
Performance counter stats for './phonebook_opt 2' (100 runs):
200,026 cache-misses # 54.181 % of all cache refs
465,553 cache-references
246,297,602 instructions # 2.07 insns per cycle
116,494,982 cycles
0.033493941 seconds time elapsed ( +- 0.49% )
```
對於這個方法，跟同組的成員有討論過是否有刪減功能的疑慮
```
entry *append(char lastName[], entry *e)
{
e->pNext = (entry *) malloc(sizeof(entry));
e = e->pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
return e;
}
```
原程式碼當中並沒有針對struct裡的*detail指標去配置記憶體，於是嘗試malloc記憶體給*detail
```
entry *append(char lastName[], entry *e)
{
e->pNext = (entry *) malloc(sizeof(entry));
e = e->pNext;
strcpy(e->lastName, lastName);
e->pNext = NULL;
e->detail = (entry1 *) malloc(sizeof(entry1));
return e;
}
```
其中的entry1是原struct的宣告型態，因為detail是指向原本的struct的，故記憶體也要配一樣大
可以想的到，勢必會讓運算及cache miss增加
```
size of entry : 32 bytes
execution time of append() : 0.040050 sec
execution time of findName() : 0.010390 sec
Performance counter stats for './phonebook_opt 2' (100 runs):
1,231,212 cache-misses # 90.445 % of all cache refs
1,374,492 cache-references
342,840,812 instructions # 1.16 insns per cycle
276,229,352 cycles
0.082166540 seconds time elapsed ( +- 1.02% )
```
對於這裡*detail的看法，我會將資料視為兩層的結構，再搜尋功能方面先不要配置記憶體給*detail (虛線表示)，等到搜尋結束後在針對得到的搜尋結果給予*detail指向的entry記憶體，就可以達到一樣查找到細節功能，而不增加findname( ) 的負擔
## 優化版本 2 (hashfunction)
過去沒有再實作中使用過 hashfunction，於是再使用前查找並了解 hashfunction，並簡單理解為"幫資料做編碼"，如何透過運算式讓資料依據 (key) 去轉為獨一無二的數值，讓查找的時間複雜度大幅的降低。但基本上完美的hashfunction是相當相當困難的 (不敢斷言不存在)，於是選擇一個讓資料均勻度高的hashfunction是不錯的出發點。
**道歉啟事**：回去重看我的hashfunction的實作後，發現有瑕疵跟錯誤，馬上奉上修正後的可怕結果，真是太對不起看過的同學了QQ
實作後的結果：
findname() 幾乎降到看不到，但 append() 本身的速度卻衝到天堂去了QQ
```
size of entry : 136 bytes
execution time of append() : 0.241334 sec
execution time of findName() : 0.000007 sec
Performance counter stats for './phonebook_opt_hash 2':
1,900,949 cache-misses # 28.082 % of all cache refs
6,769,278 cache-references
313,549,151 instructions # 0.36 insns per cycle
882,918,535 cycles
0.245116261 seconds time elapsed
```
一開始先採用簡單的 hashfunction，也就是利用 lastname 的值對某數進行 mod 後，這邊我並沒有額外建立hashtable，而是利用資料本身的 pointer 來相互連接，也就是資料結構本身就是 hashtable 來達成目的。
但是再研究過以前學長github裡的程式碼後，發現append( )再組成hash所需要的資料結構時，有邏輯上的錯誤，導致collision發生時，會直接覆蓋前一筆資料，而不是將資料接在資料串的最後端，所以才有append( )只增加些許的錯覺，這方面要跟老師請益(會找時間去問老師)
:::info
**推測**
- 再怎麼均勻的hashfunction都會讓append( )的時間暴增，因為要將資料放再linked-list的最末端時，會利用到迴圈的語法來進行幫助，所以時間的消耗會難以避免 。(ex：35萬筆資料均勻分散在5萬組之中，而每一組都會有7個entry，所以while迴圈會多執行(0+1+2+3+4+5+6)*50000=1050000的操作！！！勢必append( )的時間會增長許多，況且這是在perfect-hashfunction的大前提下，真實的時間只會更加的大
:::
剛剛翻找到神人對hashtable的做法，直接將資料接在linked list前端，就可以省去不必要的迴圈時間，實在太令人興奮了，回家後立馬實作分享跟補上[莊彥宣學長筆記](https://embedded2015.hackpad.com/Tonyyanxuans-hackpad-UE9J7cN1Li5)
>Jim H：人家有名字的！請做出最基本的尊重，把人名寫好
>>Hua：好的！馬上改
實作結果：
append( )跟之前的0.2~0.3秒鐘相比有了相當的縮短，果然append( )的時間最主要還是取決於資料結構的型態及如何配置記憶體給資料，而0.04秒要更加的接近原本的時間，就取決於hashfunction的優化，使得均勻度提高。
```
size of entry : 136 bytes
execution time of append() : 0.039045 sec
execution time of findName() : 0.000008 sec
Performance counter stats for './phonebook_opt_hash 2' (100 runs):
135,656 cache-misses # 26.088 % of all cache refs
522,893 cache-references
271,834,151 instructions # 1.71 insns per cycle
155,104,850 cycles
0.043292796 seconds time elapsed ( +- 0.59% )
```
為了不多增加一個main.c，而是像模組化的感覺安置進原程式，於是開始動手修改原本的 main.c 並增加了 phonebook_opt_hash.[ch] 來當作 hashfunction 優化的程式碼，更正後程式碼的部分已經在Github做更新了，要是邏輯有錯誤的地方，麻煩別吝嗇的告訴我> <
---
# 實作fuzzy search
## Levenshtein distance
首先從 Levenshtein distance 開始研究跟實作，[Charles的學習筆記](https://charles620016.hackpad.com/ep/pad/static/Japi4qFyAzt)以及 [NIKITA'S BLOG](http://ntz-develop.blogspot.tw/2011/03/fuzzy-string-search.html) 中有相當詳細的介紹以及原理，以下紀錄我學習的理解：
>Levenshtein distance將字串間的差異簡單的區分為三種模式：插入、刪>除、替換
>(以 jarsvs 轉為 jersv 做舉例)
>- jarsvs -> jarsv (刪除)
>- jarsv -> jersv ( "e"去替換"a" )
>- 因此這兩個字串間的 Levenshtein distance 就為 2
利用這張圖可以簡單理解其實作原理( ELEPHANT v.s. RELEVANT )，將母字串與子字串不斷的去進行 Levenshtein distance 的運算後，取其中最小值回傳，以 XX 與 XY 為範例。
:::info
Levenshtein distance (以下簡稱：LD)
LD ( XX , XY ) = min( LD( X , XY ) + 1 , LD( XY , X ) + 1 , LD ( X , X ) + Last )
Last當字串最後字元不相等時為 1
- Q：為何當比較 LD( X , XY ) 或 LD( XX , X) 時，需要 +1？
A：因為 X 與原字串 XX 、XY 相比多做了一個刪除的動作，所以 Levenshtein distance 必須+1 回傳
- Q：為何當比較 LD( X , X )時，是 + Last？
A：因為 LD ( X , X )與 LD( XX , XY ) 相比會差異在尾巴字串的異同，所以 Levenshtein distance 必須+Last 回傳
:::
## 實作一(Recursive)
Recursive再實作上的缺點就是效率極差，於是先建立一個 test.txt (只有15筆資料)來實作驗證
實作數據：
資料數：15、搜尋字串：zyexl
```
size of entry : 136 bytes
Levenshtein numver set:2
Distance=1,ayexl
Distance=0,zyexl
Distance=1,zyecl
Distance=1,zyexls
execution time of append() : 0.000005 sec
execution time of findName() : 5.243732 sec
```
可以發現少少15筆資料就讓 findName( ) 找了將近5秒，而且可以發現資料中有一個較長的字串，執行到那邊時會運算很久，這是因為 LD( ) 不斷的呼叫自己，總共呼叫了將近 3^16 次自己，導致5秒的時間幾乎都落在運算那個字串上。
```
size of entry : 136 bytes
Levenshtein numver set:2
Distance=1,ayexl
Distance=0,zyexl
Distance=1,zyecl
Distance=1,zyexls
execution time of append() : 0.000008 sec
execution time of findName() : 0.043940 sec
```
在這邊做個簡單設計就可以改善這個問題，再 findName( ) 之中，對字串長度做篩選就可以提高效率，欲搜尋字串的長度 ± Levenshtein numver 就可以稍微優化，但當字串本身太長時，還是沒辦法避免效率低落。
## 實作二 (Iterative)
(晚一點更新 Iterative 的實作跟原理)(研究ing)
----
# 參考資料
- 以上資料都與同學：黃鏡清(workfunction)、陳博聖(ponsheng)共同討論
- More about directive：
http://publications.gbdirect.co.uk/c_book/chapter7/directives.html
https://msdn.microsoft.com/zh-tw/library/ew2hz0yd.aspx
- Hash function：
http://www.powercam.cc/slide/22446
https://en.wikipedia.org/wiki/Hash_function
- GUTS Live：
https://www.youtube.com/c/GUTS4tech/live
- Fuzzy Search：
https://charles620016.hackpad.com/ep/pad/static/Japi4qFyAzt
http://ntz-develop.blogspot.tw/2011/03/fuzzy-string-search.html
https://en.wikipedia.org/wiki/Approximate_string_matching
https://en.wikipedia.org/wiki/Levenshtein_distance
----
Sign in with Wallet
Connect another wallet