• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            WisKeyのLullaby

            huangwei.pro 『我失去了一只臂膀』「就睜開了一只眼睛」

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              12 Posts :: 0 Stories :: 23 Comments :: 0 Trackbacks

            公告

            “我該走哪條路?”
            “這取決于你要去哪里。”
            “我只想能到某個地方?!?br> “只要你走的夠遠,你始終能到達那個地方?!?br>

            Home: huangwei.pro
            E-Mail: sir.huangwei [at] gmail.com
            09.6 畢業于杭州電子科技大學
            進入網易杭州研究院工作至今

            常用鏈接

            留言簿(1)

            我參與的團隊

            搜索

            •  

            積分與排名

            • 積分 - 51692
            • 排名 - 446

            最新評論

            閱讀排行榜

            評論排行榜

            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。只記錄英文單詞,全部轉為小寫。

            words : 822,529
            u-words : 12,591
            nodes : 34,266
            trie-mem : 1,247,308
            datrie-mem : 483,376

            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還是比較適合在工程中應用,尤其對于數據集比較固定的。

            posted on 2010-07-23 08:52 威士忌 閱讀(1046) 評論(0)  編輯 收藏 引用
            欧美亚洲另类久久综合婷婷| 国内精品伊人久久久久| 久久国产三级无码一区二区| 国产成人久久精品二区三区| 久久无码国产| 人妻丰满AV无码久久不卡| 国产—久久香蕉国产线看观看| 日韩久久久久中文字幕人妻| 久久精品综合网| 国产精品99久久久久久www| 久久久久久午夜成人影院| 久久久久久久亚洲精品| 久久亚洲AV无码精品色午夜| 中文字幕精品久久| 久久久久成人精品无码中文字幕 | 久久精品国产亚洲AV高清热| 久久ww精品w免费人成| 欧美日韩精品久久久免费观看| 久久人人爽人人爽人人爽| 久久久久亚洲AV综合波多野结衣| 人妻无码αv中文字幕久久| 国产免费久久精品99re丫y| 久久人人爽人人爽人人片AV东京热| 久久精品中文字幕无码绿巨人| 色婷婷久久综合中文久久一本| 99久久精品这里只有精品| 91精品国产91久久| 久久精品国产99国产电影网| 青青草原精品99久久精品66| 久久国产精品77777| 无码任你躁久久久久久老妇App| 精品久久久久久无码不卡| 久久66热人妻偷产精品9| 精品久久人妻av中文字幕| 日本福利片国产午夜久久| 久久笫一福利免费导航| 少妇内射兰兰久久| 无夜精品久久久久久| 久久婷婷五月综合97色| 精品久久久噜噜噜久久久| 亚洲国产成人精品久久久国产成人一区二区三区综 |