English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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: 2008-04-01 (23:51)
From: Jon Harrop <jon@f...>
Subject: Re: [Caml-list] More efficient implementation of intersection of sets?
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.