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
Re: [Caml-list] 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 (13:30)
From: sasha mal <sasha.mal@e...>
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!

If could give a pointer to the discussion, that would be great!

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

> Not likely.

I wouldn't be so sure.

I'm thinking of an alternative approach which inserts keys one at a time. Basically, we go through both trees simultaneously, starting with smallest nodes of both trees. If two nodes with the same key are seen, the are inserted into a new tree that will hold the intersection; then the pair of nodes with next larger keys is taken. Otherwise, if, say, key1<key2, then we search for the smallest key k>=key2 inside the first tree. If k=key2, we add k into the new tree and proceed to the next pair. If k>key2, we proceed with the pair (k, key2) instead of (key1, key2). For key1>key2, prcoeed analogously, i.e. search for the smallest key k>=key2 in the second tree. If at some point of time no "larger" key is found in one of the two original trees, the new tree where we insert elements to contains exactly the intersection.

The search in the trees is done by using "pointers" which are lists of trees contained in one another. E.g. [a,b,c] means that c is the root, b is one of the children of c, a is one of the children of b.

The advantage compared to the current implementation is that portions of one tree which are irrelevant for the intersection might be skipped. In the current implementation, they are rebalanced.

The used time is at most O((t1+t2)log(t1 intersection t2)) if constructors need O(1) time. A better estimation is welcome.

Could anyone compare this approach to the current implementation?

Join Excite! - http://www.excite.com
The most personalized portal on the Web!