Hi Hal, On Tue, 11 Nov 2003 16:45:56 -0800 (PST), Hal Daume III <hdaume@ISI.EDU> wrote:
i'm looking for a representation for a set of natural numbers. right now, my representation is sorted array, which works well. *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.
I have a very speedy implementation of "Int" sets based on big-endian patricia trees in the DData library at: <http://www.cs.uu.nl/~daan/ddata.html> You can just pull out the "IntSet.hs" and start using it. One warning though, it is a general implementation and you might get better performance using a hand-tuned data structure that is adapted to your problem set (but than, you might not, since I paid lots of attention to the bit efficiency of the library ;-) All the best, Daan.