[Haskell-cafe] hstats median algorithm

[Felipe Almeida Lessa]

Some comments wrt. performance:

On Mon, Sep 3, 2012 at 9:57 AM,  <timothyhobbs at seznam.cz> wrote:
>>  Right (medianBucket,stubLen) =
>>   foldr
>>    (\thisBucket@(thisBucketLen,_) eitheriOrMedianBucket ->
>>     case eitheriOrMedianBucket of
>>      Left i ->
>>       if i + thisBucketLen > (length `div` 2)
>>        then Right (thisBucket, thisBucketLen-((length `div` 2) - i))
>>        else Left (i + thisBucketLen)
>>      _ -> eitheriOrMedianBucket)
>>    (Left 0)
>>    myBuckets

Use a let to store length `div` 2, GHC probably won't do this for you
automatically.  Ditto for i + thisBucketLen.

>>  buckets' <- mapM
>>               (\n->
>>                 newSTRef
>>                   (0,
>>                    if n >= guessedMiddleStart && n <= guessedMiddleEnd
>>                      then Just []
>>                      else Nothing))
>>               [0..numBuckets]

You should really use a mutable array here instead of a list of STRefs
(I recommend vector's STVector [1]).

[1] http://hackage.haskell.org/packages/archive/vector/0.9.1/doc/html/Data-Vector-Mutable.html

> 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...)

> Put the value into the appropriate bucket.
>
>>    modifySTRef
>>     (buckets' `genericIndex` bucket) --Obvious optimization, use an array
>> and not a list.
>>     (\(oldLen,oldListMaybe)->
>>       case oldListMaybe of
>>        Just oldList ->
>>         (oldLen+1,Just (number:oldList))
>>        Nothing -> (oldLen + 1, Nothing))

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)

HTH!

Cheers,

-- 
Felipe.