[challenge] Hamming numbers

[bearophile]

Philippe Sigaud:

>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.<

I have appreciated how the Haskell version allows me to generate a sequence lazily in a recursive way, with a compact syntax and efficiently. But I don't know Haskell, so it's easy for what I say about Haskell programs to be false :-)


> 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 the Python and D programs I have used woerking memory & commit on Windows, for the Haskell version I have used Ideone:
http://ideone.com/wH1YU

It computes the result (ghc-6.8.2) in 0.93s using only 8.7 MB of memory.


> 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 :-)

On my very slow PC using DMD the D version requires about 2.7s and about max 92 MB of memory.

The second Python version (the one by Hettinger) takes about 4.95s and less than 4.5 MB of memory.
(The third Python version, that uses the eager array and Psyco is faster.)

Are you able to write a short D version similar to the second Python version? (I have created one, but it's not as short as the second Python version, and it takes something like 4 seconds or more).

Bye,
bearophile