On Apr 8, 2006, at 1:58 PM, David F. Place wrote:
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))
There's a couple of other nice bit-twiddily things you can do: countBits :: Word -> Int 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)) lsb :: Word -> Int lsb x = countBits ((x-1) .&. (complement x)) -- stolen from http://aggregate.org/MAGIC/ msb :: Word -> Int msb x0 = let x1 = x0 .|. (x0 `shiftR` 1) x2 = x1 .|. (x1 `shiftR` 2) x3 = x2 .|. (x2 `shiftR` 4) x4 = x3 .|. (x3 `shiftR` 8) x5 = x4 .|. (x4 `shiftR` 16) in countBits x5 - 1 findMinIndex :: Word -> Int findMinIndex 0 = error "EnumSet.findMin: empty set has no minimal element" findMinIndex w = lsb w findMaxIndex :: Word -> Int findMaxIndex 0 = error "EnumSet.findMax: empty set has no maximal element" findMaxIndex w = msb w Which should make all access to the greatest or least element O(1). I guess, come to think of it, all operations on EnumSet are O(1) by virtue of the set size being upper-bounded. At any rate this turns recursion into unboxable straight-line code and I think it does less allocations. Rob Dockins Speak softly and drive a Sherman tank. Laugh hard; it's a long way to the bank. -- TMBG