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, Joachim -- Joachim "nomeata" Breitner mail@joachim-breitner.de | nomeata@debian.org | GPG: 0x4743206C xmpp: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/