Aha!!! Now it's working. Just had to compile with -O2 :D :D Now I'm over twice as fast for a list of 2 million! With better length based analysis of how many buckets should be used, this number can be improved. You can feel free to use my code however you like. I've attached the final version. That was fun :D Timothy ---------- Původní zpráva ---------- Od: timothyhobbs@seznam.cz Datum: 3. 9. 2012 Předmět: Re: [Haskell-cafe] hstats median algorithm " Thanks for the advice. After taking most of it it is faster. But it is still many times slower than it ought to be! This algorithm should be much faster than simply sorting the list, and yet it is more than twice as slow! One note, you said: """"
Increment length.
modifySTRef lengthRef (+1)
This will create a big thunk for the length, you should use
oldLength <- readSTRef lengthRef
writeSTRef lengthRef $! oldLength + 1
(I'm not sure if a strict modifySTRef exists somewhere...)""""
Actually, replacing modifySTRef with that code is just a hair slower... Not
sure why.
I'm attaching the super optimized version. Along with the profiler output.
I just can't understand what is slow here :(
Timothy
---------- Původní zpráva ----------
Od: Felipe Almeida Lessa
Ditto for oldLen here. Also, you can simplify this lambda a lot:
import Control.Applicative ((<$>))
\(oldLen, oldVal) -> let newLen = oldLen + 1 newVal = (number:) <$> oldVal in newLen `seq` newVal `seq` (newLen, newVal)
Or, using BangPatterns, \(oldLen, oldVal) -> let !newLen = oldLen + 1 !newVal = (number:) <$> oldVal in (newLen, newVal) Cheers, -- Felipe." "