# 2017q3 Homework2 (prefix-search)(uncomplete) contributed by < `kevin55216` > ### Reviewed by `kevin550029` * 可以更詳細的解釋個功能, 用自己的理解表達 * 開發日誌部分可以提供更多程式碼來做說明 * 嘗試說明結果部分, 並用圖表表達 ## 功能觀察 1. a add word to the tree 加入文字到建立的樹中（不會寫入cities.txt） 2. f find word in tree 從樹中尋找文字（需要完全吻合） 3. s search words matching prefix 從樹中尋找文字（只需要吻合前綴） 4. d delete word from the tree 將文字從建立的樹中刪除（不會寫入cities.txt）若無此文字，則插入進樹中 5. q quit, freeing all data 離開 ## 功能圖解 ternary search tree ``` c / | \ a u h | | | \ t t e u / / | / | s p e i s a ac c hi u s tu u e s p t e copy from wikipedia/Ternary_search_tree ``` delete word ``` delete "cup" c stack / | \ |__t__| a u h |__u__| | | | \ |__c__| t t e u / / | / | s p e i s --------------------------------------------------------------------- node p is victim node t is parrent parent lokid = NULL, free victim, victim = NULL, return NULL --------------------------------------------------------------------- c / | \ a u h | | | \ t t e u / | / | s e i s --------------------------------------------------------------------- delete "us" stack |__u__| |__h__| |__c__| --------------------------------------------------------------------- node s is victim, node u is parrent parent eqkid = NULL, free victim, victim=parent, parent = node h (pop stack) parent hikid (u) = victim lokid (i), free victim, victim = NULL --------------------------------------------------------------------- c / | \ a u h | | | \ t t e i / | s e ``` insert ``` insert "cup" c / | \ a u h | | | \ t t e u / / | / | s p e i s --------------------------------------------------------------------- p node->refcnt ++ so refcnt is a count that count how many "cup" word in tree. --------------------------------------------------------------------- insert "tea" t > c t > h t < u t > i --------------------------------------------------------------------- c / | \ a u h | | | \ t t e u / / | / | s p e i s \ t | e | a --------------------------------------------------------------------- t e a node = 1 ``` ## 開發日誌 1. 將 CPY 換成 REF ，發現差異在 tst.c 的 tst_ins_del()中 有 CPY 的情形，會做 const char *eqdata = strdup(*s) strdup() 會先幫 *eqdata 做 malloc ，後在複製字串進 *eqdata 中 2. malloc fword 一段很大的連續記憶體空間，使每一個 node p 皆在 fword 上 3. 問題點： free 的時候會 core dumped 4. 參考 [HMKRL](https://hackmd.io/s/BkdddNs3-) 將 tst_del_word 中 1 改成 cpy , 按 q 仍會 dump 掉, d 可以使用了。 5. q 會 dump 掉原因， tst_free_all() 中 free(p->eqkid) 會導致錯誤 6. 在 tst_free_all() 中 加入可以控制是否執行 free(p->eqkid) 解決問題 7. 加入 bench 功能，會將已經隨機取樣1000筆測試資料，進行 find 並將結果輸出成txt檔 ```clike= /*取得tst_search cycle*/ while ((rtn = fscanf(bfp, "%s", word)) != EOF) { char *testbench = word; rmcrlf(testbench); get_cycles(&timec_high1, &timec_low1); res = tst_search(root, testbench); get_cycles_end(&timec_high2, &timec_low2); result[j] = diff_in_cycles(timec_high1, timec_low1, timec_high2, timec_low2); if (res) fprintf(brfp, "%"PRIu64"\n", result[j]); else fprintf(brfp,"%s not found.\n", testbench); j++; } ``` ``` clike= /*計算平均、標準差*/ double resultmid = 0.0; for(int i = 0; i < 1000; i++) { resultmid += (double)result[i]; } resultmid /= 1000.0; double resultsd = 0.0; for(int i = 0; i < 1000; i++) { resultsd += (((double)result[i]-resultmid)*((double)result[i]-resultmid)); } resultsd /= (1000.0-1.0); resultsd = sqrt(resultsd); printf("mid: %.9f\n", resultmid); printf("SD : %.9f\n", resultsd); ``` 並print出平均與標準差。 >請列出程式碼 >[name=課程助教][color=red] ## 結果 ``` 單位為cycles, mid 為平均值, SD 為標準差 $ ./test_ref --bench benching... bench complete mid: 889.605000000 SD : 772.879254034 $ ./test_cpy --bench benching... bench complete mid: 1016.366000000 SD : 1758.118714267 ```