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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
