---------- Forwarded message ---------- From: liuxinyu liuxinyu95@gmail.com Date: 2010/4/15 Subject: [TL] Re: {技术}[FZH][shlug]设计比STL Map更高效的Map To: TopLanguage pongba@googlegroups.com
Hi,
在支持pattern matching的FP写RBT非常简单。另外,只要使用递归,实现就会变得特别短小精悍 前者可以参考我的拙作: http://sites.google.com/site/algoxy/rbtree 插入部分来自1993年Chris Okasaki的论文,当年他用ML实现的,我的文章中给出了Haskell和scheme/Lisp的实现。 删除部分我使用了CLRS中的double black概念,略显冗长。
后者,红黑树的作者之一Robert Sedgewick给出过一个LLRB的实现,由于用了递归,代码也很简洁。但是没有方法一的代码短小。 原论文在这里: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf 他给出的代码是Java的也很容易理解。 另:我是通过Meta同学了解到LLRB的。
我的文章在墙外,需要的同学可以发email给我索取。
看来还是TopLanguage 的强人比较多。
-- 刘新宇 http://sites.google.com/site/algoxy/
On Apr 15, 11:32 am, 机械唯物主义 : linjunhalida linjunhal...@gmail.com wrote:
有谁写过红黑树的?花了多久?多少bug? 看算法导论里面,那操作复杂的。。
2010/4/15 jinhu wang wangjinhu...@gmail.com
对,还是具体问题具体对待。 因为平衡二叉树太通用了,经常在老c代码里看到要移入rbtree来做内存数据库。 在 2010年4月15日 上午11:24,机械唯物主义 : linjunhalida linjunhal...@gmail.com写道:
现在用到的这些算法都是最优的,如果还要更优,
就要根据实际的场景采用自己的数据结构, 让常见的操作提高性能,以不常用的操作性能作为代价。
2010/4/15 jinhu wang wangjinhu...@gmail.com
那样不就是hash_map了吗?
在 2010年4月15日 上午11:14,Devil Wang wxjea...@gmail.com写道:
2010/4/15 Ian Yang doit....@gmail.com
根据使用的场景会有更适合的。stl::map在插入查找交替进行的情况下性能是比较平均的,比较通用。基于有序的表的search不可能O(1),
既然search不能O(1),当然insert和delete也不能O(1)。不需要有序可以考虑hash,选一个好的hash函数可以达到O(1)
我也在想,hash是不是实现这个需求的唯一结构。
有没有种类似树的结构的,能实现这个需求的?
我之前在看swirl 的source code的时候,看到他们在底层实现了以个hash 的structer,但是也是基于__gnu_cxx::hash_map实现了一个类似功能的map.效率的提高也是惊人的。
2010/4/15 Devil Wang wxjea...@gmail.com
> HI all,
> 众所周知,STL里面的map 是由RBT来实现的。search ,insert跟delete的效率都应该是lg(n)的。
> 而且在做上面操作的时候,还需要维持树本身的平衡。
> 虽然RBT已经很高效了,探索下有没有什么更优的结构来替代 STL的这些功能。
> 需求是search , insert,delete 操作尽量更优( 能达到O(1)就最好了),但是也能实现STL map的那些功能。
> -- > Thanks & Regards
> Linux Developer : Devil Wang
-- Sincerely, Ian Yang
-- Thanks & Regards
Linux Developer : Devil Wang
-- To unsubscribe, reply using "remove me" as the subject.
chinese@lists.fedoraproject.org