Version française
Home     About     Download     Resources     Contact us    
Browse thread
More efficient implementation of intersection of sets?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Mike Furr <furr@c...>
Subject: Re: [Caml-list] More efficient implementation of intersection of sets?
sasha mal wrote:
> Currently,
> 
> Set.inter x y
> 
> splits y into two trees, one containing elements that are bigger and
> the other containing elements that are smaller than the top of x,
> then applies the procedure recursively. What is the exact runtime of
> the algorithm? Is there a better one for the intersection for OCaml
> sets?

The general algorithm is linear in the size of both sets in the worst 
case, however it can be quite a bit faster in many circumstances.  See 
the paper "Implementing Sets Efficiently in a Functional Language" by 
Stephen Adams[1] for a more detailed discussion.  I haven't looked at 
INRIA's exact implementation very closely, so they may do some extra 
tricks not discussed there, but it certainly appears to use this general 
technique.

-Mike

[1] - http://citeseer.ist.psu.edu/162336.html