Re: [Caml-list] More efficient implementation of intersection of sets?

[Jon Harrop <jon@ffconsultancy.com>]

On Tuesday 01 April 2008 16:55:24 sasha mal wrote:
> Dear OCaml users!
>
> 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?

We discussed this before on this list and the result was inconclusive. Suffice 
to say, it is very fast!

> Is there a better one for the intersection for OCaml sets?

Not likely. OCaml's implementation is already vastly more efficient than any 
other language I have ever seen (e.g. C++). Your next best bet is probably to 
parallelize the algorithm to improve the performance but that is extremely 
difficult to do without a concurrent GC. Frederic Gava did some work on this 
in OCaml. I am working on the same problem in F#.

Failing that, you might want to apply some of the stock optimizations to the 
Set module, such as a Node1 type constructor for nodes with a value but no 
child nodes. That can improve performance by 30%.

Alternatively, you may prefer to ditch immutable structures and opt for a 
hashset, which can be many times faster but is much more difficult to use 
because it is mutable.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e