set representation question

[David Overton]

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 at cs.mu.oz.au                Monash Uni (Clayton) +61 3 9905 9373
http://www.cs.mu.oz.au/~dmo    Mobile Phone         +61 4 0337 4393