[CentralOH] 2017-10-20 燕月 Lunch Placemat Scribbles: tcl braces versus python; fibonacci versus hamming

[jep200404 at columbus.rr.com]

more code than usual

lunch:

    tcl braces
    versus python
    fibonacci and hamming numbers

tcl without braces is painfully slow

    doj at sbc:~/20171026$ cat FibForXNoBraces.tcl
    proc Fib {n} {

       if {$n == 0} {
          set Ret_Value 0
       } else {
          if {$n < 3} {
             set Ret_Value 1
          } else {
             set PrevVal 1
             set ThisVal 1
             for {set y 3} {$y <= $n} {incr y} {
                set Ret_Value [expr $PrevVal + $ThisVal]
                set PrevVal $ThisVal
                set ThisVal $Ret_Value
             }
          }
       }

       return $Ret_Value

    }

    puts "Please enter seed value:"

    gets stdin x

    set StartTime [clock microseconds]
    set Answer [Fib $x]
    set EndTime [clock microseconds]
    puts "Seed $x; Result $Answer"
    puts "Duration [expr $EndTime - $StartTime] microseconds"
    doj at sbc:~/20171026$ echo 11111 | tclsh FibForXNoBraces.tcl
    Please enter seed value:
    Seed 11111; Result 515...489
    Duration 129277783 microseconds
    doj at sbc:~/20171026$ 

tcl with braces is fast

    doj at sbc:~/20171026$ cat FibForXWithBraces.tcl
    proc Fib {n} {

       if {$n == 0} {
          set Ret_Value 0
       } else {
          if {$n < 3} {
             set Ret_Value 1
          } else {
             set PrevVal 1
             set ThisVal 1
             for {set y 3} {$y <= $n} {incr y} {
                set Ret_Value [expr {$PrevVal + $ThisVal}]
                set PrevVal $ThisVal
                set ThisVal $Ret_Value
             }
          }
       }

       return $Ret_Value
    }

    puts "Please enter seed value:"

    gets stdin x

    set StartTime [clock microseconds]
    set Answer [Fib $x]
    set EndTime [clock microseconds]
    puts "Seed $x; Result $Answer"
    puts "Duration [expr $EndTime - $StartTime] microseconds"
    doj at sbc:~/20171026$ diff FibForXNoBraces.tcl FibForXWithBraces.tcl
    12c12
    <             set Ret_Value [expr $PrevVal + $ThisVal]
    ---
    >             set Ret_Value [expr {$PrevVal + $ThisVal}]
    doj at sbc:~/20171026$ echo 11111 | tclsh FibForXWithBraces.tcl 
    Please enter seed value:
    Seed 11111; Result 515...489
    Duration 42093 microseconds
    doj at sbc:~/20171026$ 

regular Python is faster

    (jupy) doj at sbc:~/20171026$ cat fib.py 
    #!/usr/bin/env python3

    import sys
    from timeit import timeit

    source_code = '''
    def fib(n):
        if n == 0:
            return 0
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a
    '''

    exec(source_code)

    def main():
        for arg in sys.argv[1:]:
            n = int(arg)
            number = 1000
            elapsed_time = timeit('fib(%s)' % n, setup=source_code, number=number)
            print(
                f'{elapsed_time}s total / {number} loops -> '
                f'{elapsed_time / number}s per loop for fib({n}) -> {fib(n)}'
            )

    if __name__ == '__main__':
        main()
    (jupy) doj at sbc:~/20171026$ ./fib.py 0 1 2 3 4 5 6 7 11111
    0.00038148299790918827s total / 1000 loops -> 3.814829979091883e-07s per loop for fib(0) -> 0
    0.0018241599900647998s total / 1000 loops -> 1.8241599900647999e-06s per loop for fib(1) -> 1
    0.0020077070221304893s total / 1000 loops -> 2.0077070221304894e-06s per loop for fib(2) -> 1
    0.002059810038190335s total / 1000 loops -> 2.059810038190335e-06s per loop for fib(3) -> 2
    0.0022625650162808597s total / 1000 loops -> 2.26256501628086e-06s per loop for fib(4) -> 3
    0.0025070849806070328s total / 1000 loops -> 2.5070849806070328e-06s per loop for fib(5) -> 5
    0.0026626960025168955s total / 1000 loops -> 2.6626960025168955e-06s per loop for fib(6) -> 8
    0.002945350017398596s total / 1000 loops -> 2.945350017398596e-06s per loop for fib(7) -> 13
    8.536355245974846s total / 1000 loops -> 0.008536355245974845s per loop for fib(11111) -> 515...489
    (jupy) doj at sbc:~/20171026$ 

pypy is faster yet.
This is the first time that I have used pypy.

    (jupy) doj at sbc:~/20171026$ cat fibpypy.py
    #!/usr/bin/env pypy

    import sys
    from timeit import timeit

    source_code = '''
    def fib(n):
        if n == 0:
            return 0
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a
    '''

    exec(source_code)

    def main():
        for arg in sys.argv[1:]:
            n = int(arg)
            number = 1000
            elapsed_time = timeit('fib(%s)' % n, setup=source_code, number=number)
            print(
                '{0}s total / {1} loops -> '
                '{2}s per loop for fib({3}) -> {4}'.format(
                    elapsed_time,
                    number,
                    elapsed_time / number,
                    n,
                    fib(n),
                )
            )

    if __name__ == '__main__':
        main()
    (jupy) doj at sbc:~/20171026$ diff fib.py fibpypy.py 
    1c1
    < #!/usr/bin/env python3
    ---
    > #!/usr/bin/env pypy
    24,25c24,31
    <             f'{elapsed_time}s total / {number} loops -> '
    <             f'{elapsed_time / number}s per loop for fib({n}) -> {fib(n)}'
    ---
    >             '{0}s total / {1} loops -> '
    >             '{2}s per loop for fib({3}) -> {4}'.format(
    >                 elapsed_time,
    >                 number,
    >                 elapsed_time / number,
    >                 n,
    >                 fib(n),
    >             )
    (jupy) doj at sbc:~/20171026$ ./fibpypy.py 0 1 2 3 4 5 6 7 11111
    0.00112700462341s total / 1000 loops -> 1.12700462341e-06s per loop for fib(0) -> 0
    0.00417494773865s total / 1000 loops -> 4.17494773865e-06s per loop for fib(1) -> 1
    0.00802302360535s total / 1000 loops -> 8.02302360535e-06s per loop for fib(2) -> 1
    0.00941896438599s total / 1000 loops -> 9.41896438599e-06s per loop for fib(3) -> 2
    0.0132009983063s total / 1000 loops -> 1.32009983063e-05s per loop for fib(4) -> 3
    0.011430978775s total / 1000 loops -> 1.1430978775e-05s per loop for fib(5) -> 5
    0.0093469619751s total / 1000 loops -> 9.3469619751e-06s per loop for fib(6) -> 8
    0.00933718681335s total / 1000 loops -> 9.33718681335e-06s per loop for fib(7) -> 13
    3.84163093567s total / 1000 loops -> 0.00384163093567s per loop for fib(11111) -> 515...489
    (jupy) doj at sbc:~/20171026$ 

It had been a long time since I had looked at tcl.
I think a big virtue of tcl is its smallness.

###############################################################################

making hamming numbers

wp:Smooth number
wp:Hamming numbers
wp:Richard Hamming

wp: prefix means Wikipedia
To get good answers, consider following the advice in the links below.
http://catb.org/~esr/faqs/smart-questions.html
http://web.archive.org/web/20090627155454/www.greenend.org.uk/rjk/2000/06/14/quoting.html

My first version is correct, but gobbles memory like crazy,
much much worse than a naive recursive fibonacci function.
It starts swapping soon, at which point all hope is lost.

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

    import sys
    from itertools import islice

    def ham(x=1):
        yield x
        g2 = ham(2 * x)
        g3 = ham(3 * x)
        g5 = ham(5 * x)
        x2 = next(g2)
        x3 = next(g3)
        x5 = next(g5)
        while True:
            x = min(x2, x3, x5)
            yield x
            if x2 == x:
                x2 = next(g2)
            if x3 == x:
                x3 = next(g3)
            if x5 == x:
                x5 = next(g5)

    def nth_hamming_number(n):
        return list(islice(ham(), 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:~/20171026$ 

    doj at sbc:~/20171026$ time ./ham1.py 1
    1 1

    real    0m0.057s
    user    0m0.044s
    sys     0m0.012s
    doj at sbc:~/20171026$ time ./ham1.py 10
    10 12

    real    0m0.058s
    user    0m0.048s
    sys     0m0.012s
    doj at sbc:~/20171026$ time ./ham1.py 100
    100 1536

    real    0m0.087s
    user    0m0.072s
    sys     0m0.012s
    doj at sbc:~/20171026$ time ./ham1.py 200
    200 16200

    real    0m0.429s
    user    0m0.384s
    sys     0m0.044s
    doj at sbc:~/20171026$ time ./ham1.py 300
    300 82944

    real    0m2.950s
    user    0m2.696s
    sys     0m0.244s
    doj at sbc:~/20171026$ time ./ham1.py 400
    400 311040

    real    0m12.706s
    user    0m11.792s
    sys     0m0.884s
    doj at sbc:~/20171026$ time ./ham1.py 500
    500 937500

    real    0m41.093s
    user    0m38.336s
    sys     0m2.672s
    doj at sbc:~/20171026$ time ./ham1.py 600
    
    this was killed after a long time of swapping

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 
    #!/usr/bin/env python3

    import sys
    from itertools import islice

    already_done = set()

    def ham(x=1):
        global already_done

        if x in already_done:
            return
        already_done |= {x}
        yield x

        x_from_generators = {}
        generators = (ham(prime * x) for prime in (2, 3, 5))
        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 nth_hamming_number(n):
        return list(islice(ham(), 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:~/20171026$ 

    doj at sbc:~/20171026$ time ./ham2.py 1
    1 1

    real    0m0.055s
    user    0m0.036s
    sys     0m0.020s
    doj at sbc:~/20171026$ time ./ham2.py 10
    10 12

    real    0m0.057s
    user    0m0.048s
    sys     0m0.004s
    doj at sbc:~/20171026$ time ./ham2.py 100
    100 1536

    real    0m0.061s
    user    0m0.048s
    sys     0m0.012s
    doj at sbc:~/20171026$ time ./ham2.py 1000
    1000 51200000

    real    0m0.111s
    user    0m0.080s
    sys     0m0.028s
    doj at sbc:~/20171026$ time ./ham2.py 10000
    10000 288325195312500000

    real    0m1.115s
    user    0m1.080s
    sys     0m0.032s
    doj at sbc:~/20171026$ time ./ham2.py 100000
    100000 290142196707511001929482240000000000000

    real    0m23.579s
    user    0m23.332s
    sys     0m0.200s
    doj at sbc:~/20171026$ time ./ham2.py 1000000
    1000000 519312780448388736089589843750000000000000000000000000000000000000000000000000000000

    real    8m31.437s
    user    8m27.944s
    sys     0m2.252s
    doj at sbc:~/20171026$