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-02 (15:34)
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 


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