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:d@vidplace.com