---------- 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.