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/
上一篇文章介紹了雙數組字典樹 DATrie，現在讓我們來簡單的測試下內存占用情況。
測試用例，我選了The Holy Bible，數據文件大小為4.2MB。只記錄英文單詞，全部轉為小寫。
Trie的實現我已經做了一些優化，初始每個節點的指針數組 size 為0，當有節點插入時，再開 max(size, char) 大小的數組。trie-mem 顯示的是已經除去節點自身的大小，即該數值體現的是申請的指針數組總大小。
trie-mem / ptr-size / nodes = 9.1，說明平均每個節點（內節點+葉節點）分配了9.1個指針。相對完全Trie樹而言，已經節省了很多空間了。但這樣算浪費的量明顯是不夠精確的，nodes 應該換成內節點數（這里就用 u-words 代替葉節點，雖然兩者是不等同的），因為葉節點未分配指針數組，并應該減去真正有用的轉移邊。這個浪費的值應該是 (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的實現我還沒有進行深入的優化，基本就是上一篇文章里的代碼做的測試。如果按那文章里提到的優化方法繼續優化，空間的浪費值會更低。
但DATrie存在一個比較大的問題，就是它的空間是預先申請好的，因為根本無從得出它實際的大小，如果空間不夠大了再重新分配的話，那勢必又得消耗時間，而且還是無法解決空間是否足夠的問題。另外，附加的信息域最好保存為指針的形式，否則重排時復制的復雜度就可能會很高。
總結，DATrie還是比較適合在工程中應用，尤其對于數據集比較固定的。
|