contributed by <f74034067
>, <catpig1630
>
TODO:
嘗試導入 Bloom Filter,實作快速字串搜尋機制。如果字串根本不存在於資料庫中,我們根本不需走訪 ternary search tree
rex662624 的解說十分詳盡完整
trie 與 binary search tree 不同在於,不是把整個字串包在同一個node 中 ,而是根據 node 的位置決定代表的字串為何。也就是一個看結果( 最終 node ),一個看過程(經過的node)。因此利用 trie,可以快速的找出有相同 prefix 的字串。以下將舉例示範 trie 如何儲存 data。
一開始,trie tree 起始於一個空的root - ◎
若今插入一個字串 and
若此時插入一個字串 ant
如此再插入 bear ,bea 就會產生像這樣子的 tree
以上,我們注意到 Trie 中,若有儲存的字串有許多相同的 prefix ,那麼 trie 可以節省大量儲存空間,因為 Trie 中每個字串都是經由 character by character 方法進行儲存,所以具有相同 prefix 的部份都會有共同的 node 。
相對的,若是資料非常大量,而且幾乎沒有相同的 prefix 將會非常浪費儲存空間。因為 trie 在 memory 的 儲存方式其實是像下圖這樣,每個 node 建立時,都必須同時創造26個值為NULL的子節點。(下圖的 universal set ={a,b,c,d,e}5所以只創造了 5 個)
因此用此 Ternary search tree ,就能解決上面的問題。這種樹的每個節點最多只會有3個 children,分別代表小於,等於,大於。以下範例解釋 Ternary search tree 。
插入一個字串 and
接著插入單字ant
接著插入單字age
Ternary Search Tree 此網址提供了用動畫表示的方式,可以清楚看到如何加入與刪除 string 的流程。
從 Ternary Search Tree 中,我們可以發現幾種特性。
aa->ac->ae->af->ag->ah
的次序插入,而下圖是 af->ae->ac->aa->ag->ah
的順序。試想今天要尋找 ah ,則上圖要比較6次,下圖則是只要比較3次。而若是建立 trie ,只需要2次。$ make bench
進行效能評比參考 raygoah 的作法
Makefile
$ make bench
執行結果test_ref.c
標注 FIXME
的地方test_ref.c
,會發現搜尋結果有誤tst.c
中與 CPY 有關的程式碼CPY 的版本由於 strdup(*s) 會先用 malloc() 配置與參數 s 字串相同大小的空間,然後將 s 字串的內容複製到該空間,所以每次回傳的地址都不相同。
REF 的版本中,每次傳入 tst_ins_del() 的 *p 都相同,curr -> eqkid 當然也就都指向同一個位址。
參考 tina0405 的作法
建立一個叫 word_arr 二維陣列 ,每次讀入一個新的城市就依序存入 word_arr[ ][ WRDMAX ] 中,如此一來每次傳入 tst_ins_del() 的 *p 就不會一樣了。
若是在 main() 裡面建立一個 word_arr[ 259112 ][ WRDMAX ] 會造成程序 core dumped ,所以我選擇宣告成全域變數。
tst.c
中 tst_del_word() 的最後一個參數,將原本寫死的 1 改為 cpytest_ref.c
中 tst_free_all(root) 會 free 到 REF 版本中宣告的二維陣列的位址,若改成 tst_free(root) 就不會出錯了先來測試一下兩種版本的效能,以執行 s Tai
100次為例
參考 ChiuYiTang 的作法
參考 rex662624 將 insert 的時間抓出來比較
memory pool 的好處在於省去了頻繁的 malloc() 與 free(),可以看到在建立 ternary search tree 的效能上 REF 略優於 CPY。
可以利用 fscanf 裡類似正規表達式的特殊寫法直接找出字串裡的程式名稱和國家名稱
把原本的%s 改成 %256[^,], %256[^\n]\n
其中[^\n]代表的是不包含 \n 字元,詳細說明可以參考 fprintf 的 man page
TingL7的解說十分詳盡完整
tst_traverse_fn
function