[FZH] Fwd: [TL] Re: {技术}[shlug]设计比STL Map更高效的Map

[Devil Wang]

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