Re: [Camllist] More efficient implementation of intersection of sets?
 sasha mal
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20080402 (14:01) 
From:  sasha mal <sasha.mal@e...> 
Subject:  Re: [Camllist] 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!