注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

可持久化数据结构第2集  

2011-07-10 22:24:32|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
曾经讨论过“可持久化数据结构”,见文章“挖掘Treap的潜力”(很久以前的了)
不过,当时没有解决的问题是复制粘贴操作,因为相同的节点会导致相同的权重,这样权重就不随机了。
我在浏览SGI STL的时候发现了一个好东西:rope
据说,它是“比string(细线)更强大的'重绳’ ”
rope支持什么呢?你可以写一个rope<char> a,然后,把a当作一个字符串,你可以:
1.在log时间、空间内取a的一个子串
2.在log时间、空间内将两个串链接起来
也就是说,这是一个支持查找、插入、删除、剪切、复制的一个超级强大的数据结构。
你甚至可以用一个rope来管理长达几百M的字符串却只占用十几个K的内存,所有的操作用时几乎和串的长度无关。

它是怎么实现的??
我查了一下stl中的文档,参考了一下wikipedia(rope,computer science),终于弄明白了它的原理。
它就是一个可持久化(只读)的平衡树!
这个树分为四种节点,其中通常情况下只使用两种节点:
叶节点(代表一小段字符串)
内节点(表示它左右两个子树的链接,内节点本身不存储数据)
对于任何操作,它从不修改已有的值,而是建立新的节点。
它的平衡策略很特殊,大体来说,如果一个节点所在子树的高度是h,它代表的串的长度达到了fib(h),就说它是平衡的。
一般情况,并不管节点是否平衡,使用最直接的操作方式。
当它在发现某一个树的高度超过给定值之后,在忍无可忍的情况下,进行一次”平衡“操作,
利用某个特殊的策略(有点像fibheap中的consolidate操作,不过它是以高度为关键字的),拼凑出尽量多的平衡节点出来。
具体的操作过程我看了之后感觉有点晕,并且严重怀疑它背后的数学证明。
但大量实践雄辩地证明了:这个策略工作地非常好。

嗯,我也想写个rope出来,当作“超级文本编辑器2”,数据范围改成操作不超过100000,维护的字符串总长度不超过512M,内存限制100M,变态吧!
这个,怎么实现呢?
那个传说中的rope的平衡树(可以叫它fib树吗?)?我打死都不想写它。
Treap?好像不行(权重无法随机);Splay?好像不行(势能分析失效)。

AVL?
什么?你说我疯了?不持久化的AVL你都不想写,更何况持久化版的?
哈哈,其实,AVL正是我选择的数据结构!

对一个内节点,规定它的两个孩子的高度差不能超过1.
struct node{
int s,h;//s是长度,h是高度
int d;//d是数据
node *l,*r;
}none,*None=&none;

我们使用函数式编程的风格,写从上至下操作的代码,而不是一般的从下至上的形式。
见证奇迹的时刻到了!

node * merge(node *a,node *b){
if (a==None)return b;
if (b==None)return a;
if (a->h-b->h>=-1 && a->h-b->h<=1){
return getnew(a,b);
}else if (a->h<b->h){ node *c=b->l;
if (c->h<=b->r->h || (a->h<c->r->h && c->l->h<c->r->h))
return getnew(merge(a,c),b->r);
return getnew(merge(a,c->l),getnew(c->r,b->r));
}else{node *c=a->r;
if (c->h<=a->l->h || (b->h<c->l->h && c->r->h<c->l->h))
return getnew(a->l,merge(c,b));
return getnew(getnew(a->l,c->l),merge(c->r,b));
}
}
node * left(node *p,int l){
if (l==0 || p==None)return None;
if (p->s==l)return p;
if (p->l->s>=l)return left(p->l,l);
return merge(p->l,left(p->r,l-p->l->s));
}
node * right(node *p,int l){
if (l==0 || p==None)return None;
if (p->s==l)return p;
if (p->r->s>=l)return right(p->r,l);
return merge(right(p->l,l-p->r->s),p->r);
}
怎么样,洋洋洒洒二十多行就写完了一个AVL,是不是可以和你的splay比短了?
现在已经实现了链接、取左、取右操作。有了这三个操作,其他操作都是顺理成章的了。
我测试了一下,在没有复制粘帖操作的情况下,它的运行速度和Treap差别不大。
但是不使用垃圾回收的版本的内存占用很恐怖(是带垃圾收集的Treap的几十倍)。
怎么解决内存占用的问题呢?
引用计数+垃圾收集!
因为一个节点可能出现在树中好多次,所以不能直接使用垃圾收集。而引用计数就可以方便地处理这种情况。
其实SGI STL中的rope也使用了引用计数。

带引用计数的版本,以及与它配套的题目,请看
http://builtinclz.abcz8.com/
  评论这张
 
阅读(6708)| 评论(14)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017