[challenge] Hamming numbers

[Philippe Sigaud]

On Fri, Sep 3, 2010 at 21:43, bearophile <bearophileHUGS at lycos.com> wrote:

> Don:
> > That's not a very useful problem, because the timing depends entirely on
> > BigInt, which is completely unoptimised for small values.
>
> You are usually right, but this time what you say is useless. There are
> other means to judge how good a program is, beside running time:
> - Total line count of the program;
> - Max amount of memory used.
>
> The Haskell version of the program is quite fast, very short, and it's lazy
> so it uses very low memory.


It's crystal clear & short (but we should aim for J! :-), but being lazy I
don't see how it can use less memory than a strict version of the same algo.
Got to store all those thunks somewhere.


> The "Alternate version using "Cyclic Iterators"" Python version invented by
> the great Raymond Hettinger too is lazy and uses very low memory. On the
> other hand, that D version, that I have translated from the Java code, is
> eager so it uses a lot of memory, is slow (mostly because of the bigint
> implementation, I agree), and its source is many lines long. So D must do
> better along one or more than one of those axis.
>

What did you use to compare them? (out of curiosity, not attack).
I used GHCi, and got 8.8s for the millionth Hamming number, using ~450 Mo of
RAM, according to GHCi itself (:set +s, :set +t). But I'm no pro in
optimizing Haskell compilation.
For my own D version, that is quite near the Rosetta Code version, I get
3.7s, 100 Mo of RAM. (-O -release -inline)
Using the RC code (your own, translated from Java, right?), I get the same.
Same result, same time, same memory consumption. Yeah, my code is not wrong
:-)
So, at least naively like this for me, D is more than twice as fast as
Haskell and uses about 80% less memory.

Of course, GHC caches results, so the second time I ask for the millionth
Hamming number, I get it almost instantaneously. Nifty, that!


Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100904/70892607/attachment.html>