lsb :: Word64 -> Int
lsb n = fromIntegral $ ix ! shiftR ((n .&. (-n)) * 0x07EDD5E59A4E28C2) 58
where
-- a 64 bit deBruijn multiplication table
ix :: UArray Word64 Word8
ix = listArray (0, 63)
[ 63, 0, 58, 1, 59, 47, 53, 2
, 60, 39, 48, 27, 54, 33, 42, 3
, 61, 51, 37, 40, 49, 18, 28, 20
, 55, 30, 34, 11, 43, 14, 22, 4
, 62, 57, 46, 52, 38, 26, 32, 41
, 50, 36, 17, 19, 29, 10, 13, 21
, 56, 45, 25, 31, 35, 16, 9, 12
, 44, 24, 15, 8, 23, 7, 6, 5
]
which could be sped up slightly by using a byteArray# directly for the backing store to find the least significant set bit in a Word64.
-Edward
Hi,
Am Samstag, den 17.09.2011, 23:37 +0200 schrieb Milan Straka:
> Great job!
thanks for the positive feedback.
> Could you please also generate comparison of and IntSet and DenseIntSet,
> when the set is sparse (eg [1, 65 .. N])? I would like to see the time
> complexities then. Also please include toList. If the results are fine,
> I currently see no reason why not to push the code in.
I have attached some benchmarking result. While results are good for
member, great for insert, intersection and union, toList is slower for
sparse maps. toList is basically a foldr, so I think the culprit is this
function:
foldrBits :: Int -> (Int -> a -> a) -> a -> Word -> a
foldrBits shift f x = go shift
where STRICT_1_OF_2(go)
go bi 0 = x
go bi n | n `testBit` 0 = f bi (go (succ bi) (n `shiftRL` 1))
| otherwise = go (succ bi) (n `shiftRL` 1)
I’ll try to optimize this function individually now, any suggestions are
welcome.
Greetings,