this is somewhat off topic, but i'll add "does anyone have a haskell implementation of..." to the beginning to make it more on topic :). anyway there are a lot of smart people here... 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. 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} and all i need to be able to do is respond with "3" very very quickly. using sorted arrays, this takes O(n+m) time (where n and m are the sizes of the arrays). i'm willing to pay some up front cost for creating a data structure that could do this more quickly (i.e., in logarithmic time). is such a thing possible? "does anyone have a haskell implementation of" such a thing? :P thanks! - hal -- Hal Daume III | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume
G'day all. Quoting Hal Daume III <hdaume@ISI.EDU>:
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 haven't had time to analyse the complexity, but you might want to try this representation, which uses a digital trie on the low-order bits of the number. If you're using Ints rather than Integers, this representation is quite speedy, and took fewer reductions in Hugs after pre-evaluating the trees than the equivalent list merge algorithm (which is not the same as an array merge, and is also not necessarily an indicator of anything) on your sample data. If you're using Integers, you're out of luck, because this code does arithmetic during the search, which allocates a lot of transient heap. Patricia tries may make the representation a bit more compact, but I doubt they would speed up the intersection operation. Using unboxed Ints might help, and so might converting countIntersection to accumulator form. Cheers, Andrew Bromage data DigitalTrie = Node DigitalTrie DigitalTrie | Leaf Int | Empty deriving (Show) dtInsert :: Int -> DigitalTrie -> DigitalTrie dtInsert x Empty = Leaf x dtInsert x t@(Leaf i) | x == i = t | x `mod` 2 == 0 = if i `mod` 2 == 0 then Node (dtInsert (x `div` 2) (Leaf (i `div` 2))) Empty else Node (Leaf (x `div` 2)) (Leaf (i `div` 2)) | otherwise = if i `mod` 2 == 0 then Node (Leaf (i `div` 2)) (Leaf (x `div` 2)) else Node Empty (dtInsert (x `div` 2) (Leaf (i `div` 2))) dtInsert x (Node t1 t2) | x `mod` 2 == 0 = Node (dtInsert (x `div` 2) t1) t2 | otherwise = Node t1 (dtInsert (x `div` 2) t2) flatten :: DigitalTrie -> [Int] flatten t = flatten' 0 1 t [] where flatten' p m Empty = id flatten' p m (Leaf i) = (:) (i*m+p) flatten' p m (Node t1 t2) = flatten' p (m*2) t1 . flatten' (p+m) (m*2) t2 countIntersection :: DigitalTrie -> DigitalTrie -> Int countIntersection Empty _ = 0 countIntersection (Leaf i) t = findIn i t countIntersection _ Empty = 0 countIntersection t (Leaf i) = findIn i t countIntersection (Node l1 l2) (Node r1 r2) = countIntersection l1 r1 + countIntersection l2 r2 findIn :: Int -> DigitalTrie -> Int findIn x Empty = 0 findIn x (Leaf i) = if x == i then 1 else 0 findIn x (Node t1 t2) | x `mod` 2 == 0 = findIn (x `div` 2) t1 | otherwise = findIn (x `div` 2) t2 t1 = foldr dtInsert Empty [0,1,10,346,398,1039,3289,3853,9811,89231,50913] t2 = foldr dtInsert Empty [0,3,98,183,398,1038,5319,7642,9811,13893,93123] test :: Int test = countIntersection t1 t2
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} | | and all i need to be able to do is respond with "3" very very | quickly. using sorted arrays, this takes O(n+m) time (where n and | m are the sizes of the arrays). | | i'm willing to pay some up front cost for creating a data structure | that could do this more quickly (i.e., in logarithmic time). | | is such a thing possible? "does anyone have a haskell | implementation of" such a thing? :P Hi. The total time (including the up front time for building the data structure) can't go below O(n+m), because if it did, you'd be neglecting to look at some of the elements at all. To move some of the effort up front, I suspect you're looking at a compression problem in disguise. For example, if your data weren't so sparse, you might try something like this: IntSet = [(Int, Int)] -- ordered list of non-overlapping ranges setToList s = concat [[a..b] | (a, b) <- s] intersectionSize :: IntSet -> IntSet -> Int intersectionSize s1@((a, b):s1') s2@((c, d):s2') = rangeSize (max a c, min b d) + case compare b d of LT -> intersectionSize s1' s2 EQ -> intersectionSize s1' s2' GT -> intersectionSize s1 s2' intersectionSize _ _ = 0 So... how *compressible* are your data? - Tom
On Wed, 12 Nov 2003, Tom Pledger 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} | | and all i need to be able to do is respond with "3" very very | quickly. using sorted arrays, this takes O(n+m) time (where n and | m are the sizes of the arrays).
The total time (including the up front time for building the data structure) can't go below O(n+m), because if it did, you'd be neglecting to look at some of the elements at all.
Isn't it O(min(m,n))? You don't have to look at all elements for the intersection. Eg: {0,1,10} {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) N
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
Dear Nicholas, Nicholas Nethercote (Wed, Nov 12, 2003 at 11:32:54AM +0000):
On Wed, 12 Nov 2003, Tom Pledger 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} | | and all i need to be able to do is respond with "3" very very | quickly. using sorted arrays, this takes O(n+m) time (where n and | m are the sizes of the arrays).
The total time (including the up front time for building the data structure) can't go below O(n+m), because if it did, you'd be neglecting to look at some of the elements at all.
Isn't it O(min(m,n))? You don't have to look at all elements for the intersection. Eg:
{0,1,10} {0,3,98,183,398,1038,5319,7642,9811,13893,93123}
O(f) describes the worst case of the algorithm. It is O((m,n)->m+n). The average cost may be lower, but it depends on the distribution of the data. Sincerly, -- Stefan Karrmann
Stefan wrote: [snip]
Isn't it O(min(m,n))? You don't have to look at all elements for the intersection. Eg:
{0,1,10} {0,3,98,183,398,1038,5319,7642,9811,13893,93123}
O(f) describes the worst case of the algorithm. It is O((m,n)->m+n). The average cost may be lower, but it depends on the distribution of the data.
Yes, and maybe these input lists make it a bit clearer: A = {0, 5, 10} B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Kind of hard to just "jump over" the B-exclusive elements... /David
On Wed, Nov 12, 2003 at 03:00:38PM +1300, Tom Pledger wrote:
The total time (including the up front time for building the data structure) can't go below O(n+m), because if it did, you'd be neglecting to look at some of the elements at all.
that would be true if there wern't a total ordering on integers, since there is you can cut out whole ranges of them without looking at the actual values. my intuition says something like binary trees annotated with the minimum and maximum value contained beneath each node so you may prune whole subtrees in constant time... John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john@foo.net ---------------------------------------------------------------------------
John Meacham wrote:
my intuition says something like binary trees annotated with the minimum and maximum value contained beneath each node so you may prune whole subtrees in constant time...
Yes. This may be one dimension too high, but check out "segment trees" from Computational Geometry. See Bentley, J.L., and D. Wood, An optimal algorithm for reporting intersections of rectangles, IEEE Trans. on Computers C-29 (1980), pp. 571-577. http://citeseer.nj.nec.com/context/2049538/0 best regards -- -- Johannes Waldmann, Tel/Fax: (0341) 3076 6479 / 6480 -- ------ http://www.imn.htwk-leipzig.de/~waldmann/ ---------
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.
participants (10)
-
ajb＠spamcop.net -
Daan Leijen -
David Bergman -
David Overton -
Hal Daume III -
Johannes Waldmann -
John Meacham -
Nicholas Nethercote -
Stefan Karrmann -
Tom Pledger