WisKeyのLullaby

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ù)組字典樹(shù) DATrie，現(xiàn)在讓我們來(lái)簡(jiǎn)單的測(cè)試下內(nèi)存占用情況。

測(cè)試用例，我選了The Holy Bible，數(shù)據(jù)文件大小為4.2MB。只記錄英文單詞，全部轉(zhuǎn)為小寫(xiě)。

Trie的實(shí)現(xiàn)我已經(jīng)做了一些優(yōu)化，初始每個(gè)節(jié)點(diǎn)的指針數(shù)組 size 為0，當(dāng)有節(jié)點(diǎn)插入時(shí)，再開(kāi) max(size, char) 大小的數(shù)組。trie-mem 顯示的是已經(jīng)除去節(jié)點(diǎn)自身的大小，即該數(shù)值體現(xiàn)的是申請(qǐng)的指針數(shù)組總大小。

trie-mem / ptr-size / nodes = 9.1，說(shuō)明平均每個(gè)節(jié)點(diǎn)（內(nèi)節(jié)點(diǎn)+葉節(jié)點(diǎn)）分配了9.1個(gè)指針。相對(duì)完全Trie樹(shù)而言，已經(jīng)節(jié)省了很多空間了。但這樣算浪費(fèi)的量明顯是不夠精確的，nodes 應(yīng)該換成內(nèi)節(jié)點(diǎn)數(shù)（這里就用 u-words 代替葉節(jié)點(diǎn)，雖然兩者是不等同的），因?yàn)槿~節(jié)點(diǎn)未分配指針數(shù)組，并應(yīng)該減去真正有用的轉(zhuǎn)移邊。這個(gè)浪費(fèi)的值應(yīng)該是 (trie-mem / ptr-size – nodes) / (nodes – u-words) = 12.8。

DATrie的浪費(fèi)值應(yīng)該是 (datrie-mem / (2 * int-size) – nodes) / (nodes – u-words) – 1 = 1.2，可見(jiàn) DATrie 的空間復(fù)雜度還是相當(dāng)不錯(cuò)的。當(dāng)然DATrie的實(shí)現(xiàn)我還沒(méi)有進(jìn)行深入的優(yōu)化，基本就是上一篇文章里的代碼做的測(cè)試。如果按那文章里提到的優(yōu)化方法繼續(xù)優(yōu)化，空間的浪費(fèi)值會(huì)更低。

但DATrie存在一個(gè)比較大的問(wèn)題，就是它的空間是預(yù)先申請(qǐng)好的，因?yàn)楦緹o(wú)從得出它實(shí)際的大小，如果空間不夠大了再重新分配的話，那勢(shì)必又得消耗時(shí)間，而且還是無(wú)法解決空間是否足夠的問(wèn)題。另外，附加的信息域最好保存為指針的形式，否則重排時(shí)復(fù)制的復(fù)雜度就可能會(huì)很高。

總結(jié)，DATrie還是比較適合在工程中應(yīng)用，尤其對(duì)于數(shù)據(jù)集比較固定的。