## digitalmars.D - Hamming numbers comparison, take 2

- bearophile (27/27) Jun 09 2010 I have tried to implement the rosettacode Hamming Numbers Task:
- bearophile (65/65) Jun 10 2010 This D2 code adapted from the Java version finds the correct solutions, ...

I have tried to implement the rosettacode Hamming Numbers Task: http://rosettacode.org/wiki/Hamming_numbers I have tried to translate the Python version (but the best version is the Haskell one). I have tried to perform this translation time ago, and it was too much early for Phobos2. Now I have tried again, and I can see things are getting better, but Phobos2 seems not good enough yet. I am using this to find the multiples, this is easy: auto m2 = map!q{2 * a}(p2); // multiples of 2 auto m3 = map!q{3 * a}(p3); // multiples of 3 auto m5 = map!q{5 * a}(p5); // multiples of 5 But then nWayUnion can't be used, because it accepts an iterable of iterables: auto merged = nWayUnion([m2, m3, m5]); So I'd like nWayUnion to accept N different iterables all of of different type, with just the constraint that each one yields the same type. I presume it can work as chain() (I don't know why chain() and nWayUnion() have a so much different signature). To remove the duplicates I use this, that looks good enough: auto output = map!q{a.field[0]}(group(combined)); // eliminate duplicates The group() of Phobos2 isn't as powerful as the Python groupby(), because group() yields the pair of head item and its count, while Python groupby() yields the pair of the head item and a lazy iterable of the duplicated items. This design of the Python version is sometimes less handy because if you want to know how many similar items there are (and this is a common usage of groupby()) you have to count them for example with something like a walkLength, but it's more powerful because the items can define a generic equality, so they can be actually not the same item and you may need them all. Adding the starting item is easy: auto combined = chain([1], merged); // prepend a starting point But in practice this Task asks for the millionth item of this Hamming sequence, that is larger than a ulong, so I have to use something like this: auto combined = chain([BigInt(1)], merged); // prepend a starting point But then the BigInt lack a handy toString() (irony: I have seen that inside the unittests of BigInt there is one such function). I think Phobos2 lacks a tee() function: http://docs.python.org/library/itertools.html#itertools.tee And I have not seen the islice() (a lazy slice) but this is easy enough to implement. (I don't know if such ranges are already present in some dsource module about extra ranges). A bigger problem in the translation comes from the deferred_output and output, that I am not sure how to define/translate yet. I accept suggestions :-) I invite other people to try to use Phobos2, because in practice you can spot similar troubles only if you actually try to use it. Bye, bearophile

Jun 09 2010

This D2 code adapted from the Java version finds the correct solutions, but I don't think of it as the a good solution because it stores all items and uses lot of memory. The Python version I was trying to translate uses only few MB of RAM, while this version uses almost 100 MB of it. import std.stdio: writeln; import std.bigint: BigInt; import std.algorithm: min, map; import std.range: iota; import std.array: array; BigInt hamming(int limit) { BigInt two = 2; BigInt three = 3; BigInt five = 5; auto h = new BigInt[limit]; h[0] = 1; BigInt x2 = 2; BigInt x3 = 3; BigInt x5 = 5; int i, j, k; foreach (ref el; h[1 .. $]) { el = min(x2, x3, x5); if (x2 == el) x2 = two * h[++i]; if (x3 == el) x3 = three * h[++j]; if (x5 == el) x5 = five * h[++k]; } return h[$ - 1]; } const(char)[] bigIntRepr(BigInt i) { const(char)[] result; i.toString((const(char)[] s){ result = s; }, "d"); return result; } void main() { writeln(array(map!bigIntRepr(map!hamming(iota(1, 21))))); writeln(bigIntRepr(hamming(1691))); writeln(bigIntRepr(hamming(1_000_000))); } I think it's the first time I am able to write a working program that uses BigInt :-) In the first line of the main I have had to use two maps because I was not able to make it run with just one map. While writing this program I have found only two problems (beside the known map one), filed as 4300 and 4301. This code runs in D 2.62 seconds, its Java version in 1.95 seconds, and its Python+Psyco version in 1.03 seconds. (The Haskell version that uses a better algorithm can be a bit faster than the Python version). The Python translation: import psyco def hamming(limit): h = [1] * limit x2, x3, x5 = 2, 3, 5 i = j = k = 0 for n in xrange(1, limit): h[n] = min(x2, x3, x5) if x2 == h[n]: i += 1 x2 = 2 * h[i] if x3 == h[n]: j += 1 x3 = 3 * h[j] if x5 == h[n]: k += 1 x5 = 5 * h[k] return h[-1] psyco.bind(hamming) print [hamming(i) for i in xrange(1, 21)] print hamming(1691) print hamming(1000000) Bye, bearophile

Jun 10 2010