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 (14:01)
From: sasha mal <sasha.mal@e...>
Subject: Re: [Caml-list] More efficient implementation of intersection of sets?

> 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 contain 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, proceed analogously, i.e.

> search for the smallest key k>=key1 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.

[Small corrections.]

By the way, the current implemented procedure always splits the second tree, regardless of the sizes of the trees. Imagine that we have two trees of very different sizes (e.g. with 5 and 10^5 elements). What tree should be split then?

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