On Wed, Nov 12, 2003 at 11:32:54AM +0000, Nicholas Nethercote wrote:
Hal Daume III writes: : | *all* i care about is being able to quickly calculate the size of | the intersection of two sets. these sets are, in general, very | sparse, which means that the intersections tend to be small. | | for example, i might have two sets reprsented by the arrays: | | {0,1,10,346,398,1039,3289,3853,9811,89231,50913} | {0,3,98,183,398,1038,5319,7642,9811,13893,93123}
I can vaguely imagine some clever bitset implementation that lets you do intersection with bitwise-and. Mercury has a bitmap library, which might be able to do something like this, but I'm not sure; it might be more suited to smaller and denser sets than you seem to have. But it might be worth a look (see www.cs.mu.oz.au/research/mercury/information/doc-release/library_8.html#SEC8)
There is also `sparse_bitset', which may be more appropriate for the type of data you've got. See <http://www.cs.mu.oz.au/research/mercury/information/doc-release/library_50.html#SEC50> David -- David Overton Uni of Melbourne +61 3 8344 1354 dmo@cs.mu.oz.au Monash Uni (Clayton) +61 3 9905 9373 http://www.cs.mu.oz.au/~dmo Mobile Phone +61 4 0337 4393