ached the final
version.
That was fun :D
Timothy
-- Původní zpráva --
Od: timothyho...@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 i
lacing 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
Datum: 3. 9. 2
On Mon, Sep 3, 2012 at 11:18 AM, Felipe Almeida Lessa
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 `s
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)
>>the
*Main> someListMedian
Just 500
(37.77 secs, 15376209200 bytes)
>someListMin :: Integer
>someListMin = 0
>someListMax :: Integer
>someListMax = 1000
>someList :: [Integer]
>someList =
> concatMap
> (\n->intersperse n [someListMin..someListMax])
> [someListMax
Sorry, I am horribly mistaken. Hash table is O(n)+O(numbuckets)+O
(middlebucketsize log(middlebucketsize))... It's too late for this stuff...
Tim
-- Původní zpráva --
Od: timothyho...@seznam.cz
Datum: 3. 9. 2012
Předmět: Re: [Haskell-cafe] hstats median algorithm
"
start at the middle bucket and move outwards. That will be O(n) + O
(bucketsize log(bucketsize)) given that the middle bucket is non empty and
I'm not horribly mistaken.
Tim
-- Původní zpráva --
Od: David Feuer
Datum: 3. 9. 2012
Předmět: Re: [Haskell-cafe] hstats m
I was thinking it should offer a randomized version (taking a generator),
since randomized median algorithms provide the best expected performance.
It could also offer a deterministic version using some variant of
median-of-medians, intended for long lists. I guess it probably should
retain the nai
Is there any special structure in your data that could be exploited?
On Sat, Sep 1, 2012 at 6:17 PM, Gershom Bazerman wrote:
> In my experience, doing much better than the naive algorithm for median is
> surprisingly hard, and involves a choice from a range of trade-offs. Did you
> have a parti
In my experience, doing much better than the naive algorithm for median
is surprisingly hard, and involves a choice from a range of trade-offs.
Did you have a particular better algorithm in mind?
If you did, you could write it, and contact the package author with a patch.
You also may be able
On 2 September 2012 05:26, David Feuer wrote:
> The median function in the hstats package uses a naive O(n log n)
> algorithm. Is there another package providing an O(n) option? If not,
> what would it take to get the package upgraded?
http://hackage.haskell.org/packages/archive/statistics/latest
The median function in the hstats package uses a naive O(n log n)
algorithm. Is there another package providing an O(n) option? If not,
what would it take to get the package upgraded?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.hask
12 matches
Mail list logo
