Re: [Haskell-cafe] hstats median algorithm

3 Sep 2012

      Some comments wrt. performance:

On Mon, Sep 3, 2012 at 9:57 AM,   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-Vecto...
...
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.

Re: [Haskell-cafe] hstats median algorithm

Felipe Almeida Lessa