[Haskell-cafe] Efficient functional idiom for histogram

[Paul Moore]

2009/8/1 Ketil Malde <ketil at malde.org>:
> Paul Moore <p.f.moore at gmail.com> writes:
>
>> What am I doing wrong here? I'd have expected compiled Haskell to be
>> faster than interpreted Python, so obviously my approach is wrong.
>
> Two things from my experience: Python associative arrays are fast, and
> Haskell random numbers are slow.  So by building a map from random
> numbers, you are likely doing a fairly pessimal comparison.

Hmm, I think you're saying that for this problem, Haskell is likely to
be worse than Python. Interesting. I guess I'd assumed that something
CPU-intensive like this would benefit from a compiled language. Just
goes to show that intuition about performance is usually wrong
(something I really should know by now :-))

Is the issue with random numbers just the implementation, or is it
something inherent in the non-pure nature of a random number generator
that makes it hard for Haskell to implement efficiently? If the
latter, that probably makes Haskell a somewhat poor choice for
simulation-type programs.

> Did you profile to see where the time is spent?

Not until you suggested it :-) I was pleasantly surprised by how easy
it was to do. The results bear out what you were saying, the
bottleneck is entirely in the "dice" function.

>> I'm expecting the answer to be that I've got unnecessary laziness
>
> IME, laziness usually affects space, but not so much time
> performance.  Although 'insertWith (+)' looks like it would build
> unevaluated thunks for the sums.

That'll teach me to bandy about technical terms as if I understand them :-)

Thanks for the comments,
Paul.