map implementation question

map implementation question

[Brian Hurt]

I was just looking at the map.ml implementation, and noticed that the 
logic for when to do a rotation was:

>       if hl > hr + 2 then begin


Isn't this supposed to be:

    if hl >= hr + 2 then begin

?  The latter will cause more rotations, but keep the tree more 
balanced.  The worst-case access of the >= version is log base 3/2, 
while the > is log base 4/3, which means that the >= will be about 41% 
(log(3/2)/log(4/3) ~ 1.41).  Both are correct in that they return the 
right answer and are still O(log(N)) performance, it's a question of 
performance of looking up an element in the tree vr.s the cost of 
inserting an element into the tree.

Was there a reason it was done this way, or is this a (minor) bug?

Brian

Re: [Caml-list] map implementation question

[Xavier Leroy]

Brian Hurt wrote:
> I was just looking at the map.ml implementation, and noticed that the
> logic for when to do a rotation was:
>       if hl > hr + 2 then begin
> Isn't this supposed to be:
>    if hl >= hr + 2 then begin

No, it was a conscious decision to use height-balanced binary trees
with an height imbalance of at most 2, rather than at most 1 as in
standard AVL trees.  As you note, log(N) access times are still
guaranteed, and it's a tradeoff between lookup time vs. rebalancing time.
Light experimentation suggested that imbalance <= 2 is globally more
efficient than imbalance <= 1.  Didn't try with larger imbalance bounds.

This said, red-black trees would probably work faster anyway, but I'll
let the algorithm experts on this list comment.

- Xavier Leroy

Re: [Caml-list] map implementation question

[j h woodyatt]

On Aug 17, 2006, at 4:37 AM, Xavier Leroy wrote:
>
> This said, red-black trees would probably work faster anyway, but I'll
> let the algorithm experts on this list comment.

My experience trying to tweak the red-black trees in the Cf library  
of OCaml NAE so they perform globally better than the height-balanced  
trees in the standard library has been mixed.  Some functions perform  
marginally better, but others are worse-- sometimes substantially  
worse, and I don't think there's any way around it.  (It doesn't help  
that a lot of my exercises reveal that my binary set operations need  
improvement, but there are other places where there's simply nothing  
to do.  I'll get around to fixing the binary set operators someday,  
before my next release.)

By the way, Xavier is very correct: that "imbalance <= 2" thing is  
utterly brilliant.  I'm pretty sure my red-black trees would smoke  
the standard library if it weren't for that.

The result is that I recommend using my red-black trees only when you  
are either 1) using the other facilities in the Cf library that are  
integrated well with them, e.g. Cf_seq and such, or 2) using them in  
a [currently hypothetical] case where you have compared the  
performance with the standard library and it makes a valuable  
difference to get 15% more CPU (or one less field per tree node) out  
of your tree algorithm.


—
j h woodyatt <jhw@conjury.org>
san francisco, ca

Re: [Caml-list] map implementation question

[Shawn]

Xavier Leroy wrote:

> This said, red-black trees would probably work faster anyway, but I'll
> let the algorithm experts on this list comment.
>   


I don't suppose anyone's compared the ocaml splay tree library that's 
floating around with Map and red-black trees?