[Haskell-cafe] Efficient functional idiom for histogram

[Paul Moore]

2009/8/5 Yitzchak Gale <gale at sefer.org>:
> Dmitry Olshansky wrote:
>> My measurements show that...
>> (-O2 gives approx 2 time impovements).
>> ...using RandomGen and State monad to generate a list gives at least 4 times
>> improvements (on 1 000 000 items).
>
> You earlier said:
>
>> this takes over twice as long as a naively implemented
> Python program

The latter was me :-)

> So now our "naive" Haskell - ordinary usage of Data.Map
> and System.Random, without resorting to things like
> unboxed arrays - is beating naive Python handily. Correct?

I haven't checked myself (and won't have time in the next couple of
weeks, as I'm on holiday - but I'll pick this up when I get back).,
but it sounds like it. I'd like to check Dmitry's suggestions, mainly
to see how they fit with my feel for "naive" (ie, at my beginner
level, do I understand why they are more efficient).

But I'd expect (compiled) Haskell to beat (interpreted) Python. That's
sort of the point, really... The big measures for me are (1) by how
much, and (2) how readable is the code.

> Or is this with an alternate RNG? Although I think even that
> would be fair, since Python uses Mersenne.

I got the impression Dmitry was using Haskell's standard RNG, not
Mersenne Twister. If so, then we'd get further improvements with MT,
but that's still a hit against Haskell, as I'd interpret it as meaning
that Haskell supplies as default a PRNG which costs noticeable
performance in order to provide guarantees that "ordinary" programs
don't need.

Paul.