contributed by < maskashura
>
yusihlin
在討論 ternary search tree 前我們先討論一個支援自動查詢,但較佔空間的結構 "trie"
Trie 為一種樹狀資料結構, 其中每個 node 都包含一組指標陣列, 一個指向字元 character 中各個字母的指標。 我們可以從根節點開始,透過目標字中的字母對應的指標來追蹤一個單字詞。
:notes: jserv
Bruce Ke謝謝老師指教,今後的作業我會加強並改進!
這裡討論以 trie 型式儲存的字串 AB, ABBA, ABCD, 及 BCD. 字串的終止節點標記為黃色:
(圖片來源)
使用 Trie 實現自動完成 (auto-completion) 很容易。我們只需追踪指標來獲得一個表示使用者輸入的字串的節點。透過從該節點搜尋 trie ,我們可以列舉所有完成使用者輸入的字串。
但是,我們可以由上圖中看到一個 trie 的主要問題。上圖 trie 僅支援4個字母 {A,B,C,D}。如果我們需要支援到所有26個英文字母,意味著每個節點將存儲 26 個指標。而且,如果我們需要支持萬國碼(international characters),標點符號或區分小寫字母,則所需的記憶體空間將變得非常巨大。
character 在台灣和繁體中文的翻譯慣例為「字元」,共筆有一堆這樣的誤寫,請及早修正
:notes: jserv
Bruce Ke己修正共筆中不正確的誤寫
我們可以考慮在每個節點中使用不同的數據結構,例如 HASH mapping 。然而,管理成千上萬的 HASH maps 通常不是一個好主意,所以讓我們來看看一個更好的解決方案。
三元搜尋樹 (ternary search tree) 是一種 trie 的型式 (有時稱為 prefix tree), 有點類似 Binary search tree ,但 ternary search tree 是由三個子樹 (children) 所組成的, ternary search tree 每個節點由一個字元 character 構成,m一個 value ,及三個指向子樹的指標(分別為 equal kid, lower kid and higher kid), 下面引用作業中 TST node 結構做參考。
Bruce Ke己修正共筆中不正確的誤寫, 並修正內文與作業程式碼匹配
而和標準的 prefix tree 相比 ternary search tree 的空間效率更高, 以速度為代價 (雖然較其他 prefix tree 慢,但是由於其空間效率,三元搜尋樹適合應用在較大的資料集( data set )。
:notes: jserv
Bruce Ke修正 data set 的誤寫, 並修正為"三元搜尋樹適合應用在較大的資料集"
我們將以上述的字串 AB, ABBA, ABCD, 及 BCD 做三元搜尋樹的討論
(圖片來源)
"current" 的繁體中文翻譯為「目前」,而非「當前」,兩者的應用情境不同
:notes: jserv
例如,綠色箭頭顯示如何確認三元樹包含字串 ABBA:
(圖片來源)
而我們可以在下圖發現 ternary string 中不含字串 ABD:
(圖片來源)
可以使用三元搜尋樹來解決許多問題,其中大量的字串必須以任意順序儲存和檢索。一些最常見的應用的如下:
"store" 的繁體中文翻譯為「儲存」,而非「存儲」。你可以適度摘錄和引用簡體中文內容,但應該用繁體中文慣用語改寫。愛護自己的文化,你我有責。
:notes: jserv
謝謝老師提醒,己修正繁體中文慣用詞為"儲存"
Bruce Ke
Ternary Search Tree (TST)時間複雜度表示如下:
Algorithm | Average | Worst Case |
---|---|---|
Search | O(log n) | O(n) |
Insert | O(log n) | O(n) |
Delete | O(log n) | O(n) |
### Segmentation fault 錯誤修正
:notes: jserv
在原始程式執行時,會發現在做 search words matching prefix 輸入"A"發現會有出現 Segmentation fault ,使用 GDB 去追蹤,可發現錯誤出現在 a[(*n)++] = (char *) p->eqkid; (at tst.c:330)
但"Ab"可搜尋到190筆資料, 而輸入其他單字如B,C,D..皆能正常執行沒發生錯誤, 故我開始檢查 tst_suggest 中的程式碼
從tst_suggest的程式碼中, 我們會發現tst_suggest()會遞迴呼叫自己,而在 a[(*n)++] = (char *) p->eqkid; 這段程式 *n 會持續往上加並執行遞迴,而當 *n 值 >=1024(a[1024])時,程式就會發生 Segmentation fault
開始對 n 進行檢查, 避免n存取到錯誤區段
上述程式碼可改寫為:
:notes: jserv
修改後結果如下, A字元看起來可以正常執行搜尋:
不要說「看起來」,只要你能確保都可重現 (reproduce),就是「可以」。用語要精確
"jserv"
根據tst.h文件內的註解, 並依據 Fixme 的指示將 CPY 都改成 REF, 但在觀察 CPY 及 REF 二個變數後可以發現CPY一開始被定義為1,而DEL被定義為0
我試著將tst.h內的 CPY 都改成 REF, 重新make後執行可以發現程式在 search words matching prefix 出現錯誤(搜尋結果僅列出開頭第一個字母)
用gdb檢查單步執行 並顯示變數值 可以發現在sgl[i]並沒有放入完整字串
故我們開始回推程式尋找程式中和 CPY 及 REF 有關的地方, 最後在tst.c中的 tst_ins_del 發現有 CPY 關連的地方
1).
2).
程式碼應該用指定的 coding style 編排 (4 個空白,而非 tab),開發的紀律和對細節的重視,不能少!
"jserv"
謝謝老師提醒,查了網路一下,才知道原來不只為了防止不同編輯器作業下格式混亂,許多大公司也開始規定程式需以空白代替tab
Bruce Ke
可以發現 CPY 及 REF 的差異在於 , CPY 會分配一塊儲存空間 const char *eqdata = strdup(*s), 但此方式系統會不斷要求分配記憶體空間,而造成資料空間片段而不連續, 而不斷 malloc 和 free 記憶體區塊。會導致記憶體的碎片問題,碎片一多可使用的記憶體就變少最後產生 memory leak
to do: 能否用GDB去觀察記憶體空間
而 REF 並沒有分配空間,會將指標指向資料位置 curr->eqkid = (tst_node *) *s
我們試著在 REF 分配記憶體空間,同時避免如 CPY 不連續的記憶體配置方式, 我們一次分配較大的記憶體空間( memory pool )
Makefile
以允許 $ make bench
時,可對 ternary search tree 的實作做出效能評比,涵蓋建立 tst 和 prefix search 的時間,應比照 clz 透過統計模型,取出 95% 信賴區間
--bench
的執行參數,得以在沒有使用者輸入的前題下,對 tst 程式碼進行效能分析,應涵蓋 cpy
和 ref
兩種途徑 (詳情參閱 tst.h
的程式碼註解)TODO
的部分,替換成真正有效的 API 和對應的程式碼,這裡要求你學習分析現有的程式碼並得以擴充test_cpy
和 test_ref
兩種方式 (copy/reference) 的效能,並且針對現代處理器架構,提出效能改善機制tst.h
和 tst.c
為何要 forward declaration 呢?分離介面和實作有何好處呢?這樣的思維又該如何運用於 phonebook 呢?提出想法並且實作tst_traverse_fn
函式,並思考如何運用這個實作,注意到 callback function 的程式開發技巧/模式Reference: