]
someList =
concatMap
(\n-intersperse n [someListMin..someListMax])
[someListMax,someListMax-1..someListMin]
-- Původní zpráva --
Od: timothyho...@seznam.cz
Datum: 3. 9. 2012
Předmět: Re: [Haskell-cafe] hstats median algorithm
It really depends on how you are reading
Some comments wrt. performance:
On Mon, Sep 3, 2012 at 9:57 AM, timothyho...@seznam.cz wrote:
Right (medianBucket,stubLen) =
foldr
(\thisBucket@(thisBucketLen,_) eitheriOrMedianBucket -
case eitheriOrMedianBucket of
Left i -
if i + thisBucketLen (length `div` 2)
On Mon, Sep 3, 2012 at 11:18 AM, Felipe Almeida Lessa
felipe.le...@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`
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.le...@gmail.com
Datum: 3. 9. 2012
Předmět: Re: [Haskell-cafe] hstats median algorithm
On Mon, Sep 3, 2012
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 it ought to be! This algorithm
Is there any special structure in your data that could be exploited?
On Sat, Sep 1, 2012 at 6:17 PM, Gershom Bazerman gersh...@gmail.com 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
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
-cafe] hstats median algorithm
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
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
It really
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
On 2 September 2012 05:26, David Feuer david.fe...@gmail.com 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?
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
12 matches
Mail list logo
