WisKeyのLullaby

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

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

公告

“我该走哪条路?”
“这取决于你要去哪里。”
“我只想能到某个地方。”
“只要你走的够远,你始终能到达那个地方。”

Home: huangwei.pro
E-Mail: sir.huangwei [at] gmail.com
09.6 毕业于杭州电子科技大学
进入网易杭州研究院工作至今

常用链接

留言簿(1)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 45580
  • 排名 - 395

最新评论

阅读排行榜

评论排行榜

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 威士忌 阅读(758) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理