http://blog.huang-wei.com/2010/07/20/%e5%8f%8c%e6%95%b0%e7%bb%84%e5%ad%97%e5%85%b8%e6%a0%91%e7%9a%84%e5%86%85%e5%ad%98%e5%8d%a0%e7%94%a8%e6%b5%8b%e8%af%95/
上一篇文章介紹了雙數(shù)組字典樹 DATrie，現(xiàn)在讓我們來簡單的測試下內(nèi)存占用情況。
測試用例，我選了The Holy Bible，數(shù)據(jù)文件大小為4.2MB。只記錄英文單詞，全部轉(zhuǎn)為小寫。
Trie的實現(xiàn)我已經(jīng)做了一些優(yōu)化，初始每個節(jié)點的指針數(shù)組 size 為0，當有節(jié)點插入時，再開 max(size, char) 大小的數(shù)組。trie-mem 顯示的是已經(jīng)除去節(jié)點自身的大小，即該數(shù)值體現(xiàn)的是申請的指針數(shù)組總大小。
trie-mem / ptr-size / nodes = 9.1，說明平均每個節(jié)點（內(nèi)節(jié)點+葉節(jié)點）分配了9.1個指針。相對完全Trie樹而言，已經(jīng)節(jié)省了很多空間了。但這樣算浪費的量明顯是不夠精確的，nodes 應該換成內(nèi)節(jié)點數(shù)（這里就用 u-words 代替葉節(jié)點，雖然兩者是不等同的），因為葉節(jié)點未分配指針數(shù)組，并應該減去真正有用的轉(zhuǎn)移邊。這個浪費的值應該是 (trie-mem / ptr-size – nodes) / (nodes – u-words) = 12.8。
DATrie的浪費值應該是 (datrie-mem / (2 * int-size) – nodes) / (nodes – u-words) – 1 = 1.2，可見 DATrie 的空間復雜度還是相當不錯的。當然DATrie的實現(xiàn)我還沒有進行深入的優(yōu)化，基本就是上一篇文章里的代碼做的測試。如果按那文章里提到的優(yōu)化方法繼續(xù)優(yōu)化，空間的浪費值會更低。
但DATrie存在一個比較大的問題，就是它的空間是預先申請好的，因為根本無從得出它實際的大小，如果空間不夠大了再重新分配的話，那勢必又得消耗時間，而且還是無法解決空間是否足夠的問題。另外，附加的信息域最好保存為指針的形式，否則重排時復制的復雜度就可能會很高。
總結(jié)，DATrie還是比較適合在工程中應用，尤其對于數(shù)據(jù)集比較固定的。
|