[FZH] Fwd: [TL] Re: {技术}[shlug]设计比STL Map更高效的Map - Fedora 中文組郵件列表 - Fedora mailing-lists

14 Apr 2010


      ---------- 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.
-- 
Thanks & Regards

Linux Developer : Devil Wang