[Haskell-cafe] hstats median algorithm

[timothyhobbs at seznam.cz]

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 at 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 <felipe.lessa at gmail.com>
Datum: 3. 9. 2012
Předmět: Re: [Haskell-cafe] hstats median algorithm
"On Mon, Sep 3, 2012 at 11:18 AM, Felipe Almeida Lessa
<felipe.lessa at gmail.com> wrote:
> 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."
"
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120903/bc957820/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: medians.lhs
Type: text/x-literate-haskell
Size: 5546 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120903/bc957820/attachment.lhs>