[CentralOH] Generalized ham() to smooth()

[jep200404 at columbus.rr.com]

On Fri, 20 Oct 2017 22:24:22 -0400, jep200404 at columbus.rr.com wrote:

> Second version tries to avoid duplication,
> so is much faster and uses much much less memory.
> Seems to be fast enough for the 1000000th hamming number.
> It even seems to be correct.
> I wonder about using a decorator to avoid having the global dictionary.
> 
>     doj at sbc:~/20171026$ cat ham2.py 

The ham() generator function from ham2.py
has been generalized to smooth() in ham4.py below.
Also, the annoying global has been eliminated.
Surprisingly, the speed is very similar to previous versions.

The hamming() function is just a thin wrapper around smooth().

    doj at sbc:~/20171020$ cat ham4.py 
    #!/usr/bin/env python3

    import sys
    from itertools import islice


    def smooth(x, primes, already_done):
        if x in already_done:
            return
        already_done |= {x}
        yield x

        x_from_generators = {}
        generators = (
            smooth(prime * x, primes, already_done)
            for prime in primes
        )
        for g in generators:
            try:
                x_from_generators[g] = next(g)
            except StopIteration:
                pass

        while x_from_generators:
            x_min = min(x_from_generators.values())
            yield x_min
            for g, x in x_from_generators.items():
                if x != x_min:
                    continue

                try:
                    x_from_generators[g] = next(g)
                except StopIteration:
                    x_from_generators.pop(g)


    def hamming():
        yield from smooth(x=1, primes=(2, 3, 5), already_done=set())


    def nth_hamming_number(n):
        return list(islice(hamming(), n-1, n))[0]


    def main():
        for arg in sys.argv[1:]:
            n = int(arg)
            x = nth_hamming_number(n)
            print(n, x)

    if __name__ == '__main__':
        main()
    doj at sbc:~/20171020$ 

    doj at sbc:~/20171020$ time ./ham4.py 1
    1 1

    real    0m0.054s
    user    0m0.032s
    sys     0m0.020s
    doj at sbc:~/20171020$ time ./ham4.py 10
    10 12

    real    0m0.056s
    user    0m0.048s
    sys     0m0.008s
    doj at sbc:~/20171020$ time ./ham4.py 100
    100 1536

    real    0m0.058s
    user    0m0.048s
    sys     0m0.004s
    doj at sbc:~/20171020$ time ./ham4.py 1000
    1000 51200000

    real    0m0.112s
    user    0m0.088s
    sys     0m0.024s
    doj at sbc:~/20171020$ time ./ham4.py 10000
    10000 288325195312500000

    real    0m1.141s
    user    0m1.112s
    sys     0m0.020s
    doj at sbc:~/20171020$ time ./ham4.py 100000
    100000 290142196707511001929482240000000000000

    real    0m23.773s
    user    0m23.524s
    sys     0m0.200s
    doj at sbc:~/20171020$ time ./ham4.py 1000000
    1000000 519312780448388736089589843750000000000000000000000000000000000000000000000000000000

    real    8m27.888s
    user    8m23.132s
    sys     0m2.724s
    doj at sbc:~/20171020$