Thanks Bulat and Robert. I implemented Bulat's idea as the
following. It tests faster than Roberts. I use Robert's to compute
the table. The performance seems satisfactory now.
size :: Set a -> Int
size (Set w) = countBits w
where
countBits w
| w == 0 = 0
| otherwise = countBits (w `shiftR` 8) + bitsTable!(w .&.
0xFF)
bitsTable :: Array Word Int
bitsTable = array (0,255) $ [(i,bitcount i) | i <- [0..255]]
bitcount :: Word -> Int
bitcount 0 = 0
bitcount x = 1 + bitcount (x .&. (x-1))
On Apr 8, 2006, at 1:21 PM, Robert Dockins wrote:
On Apr 8, 2006, at 4:24 AM, Bulat Ziganshin wrote:
Hello Daniel,
Saturday, April 8, 2006, 4:21:14 AM, you wrote:
Unless I overlooked something, I use foldBits only via size
(though that's
used a lot).
size of set? there is much faster method - use a table
[0..255] -> number of bits in this number seen as set
Or:
bitcount :: Word -> Int
bitcount 0 = 0
bitcount x = 1 + bitcount (x .&. (x-1))
-- | /O(1)/. The number of elements in the set.
size :: Set a -> Int
size (Set w) = bitcount w
--------------------------------
David F. Place
mailto:[EMAIL PROTECTED]
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
