Re: Python 3.3 vs. MSDOS Basic

Discussion in 'Python' started by workshed, Feb 20, 2013.

  1. workshed

    workshed Guest

    On Tuesday, February 19, 2013 3:28:25 PM UTC-5, Serhiy Storchaka wrote:
    > 10-15% faster:
    >
    >
    > def f(M):
    > def g(n, cache = {1: 0}):
    > if n in cache:
    > return cache[n]
    > if n % 2:
    > m = 3 * n + 1
    > else:
    > m = n // 2
    > cache[n] = count = g(m) + 1
    > return count
    > num = max(range(2, M + 1), key=g)
    > return num, g(num)
    >
    > print(*f(1000000))


    I managed another 15-20% (on my machine) with a different caching scheme.

    def g(n):
    cache = [1,1] + [0]*(n - 2)
    longest = 0
    for x in range(1, n):
    num = 0
    y = x
    while True:
    if x < n and cache[x]:
    cache[y] = num + cache[x]
    break
    if x&1:
    x = (3*x + 1)//2 #Credit to Terry
    num += 2
    else:
    x = x//2
    num += 1
    ans = cache.index(max(cache))
    return ans, cache[ans] - 1

    Python 3.2.3 (default, Oct 19 2012, 19:53:57)
    [GCC 4.7.2] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    >>> import timeit
    >>> timeit.Timer('euler014.f(10**6)', 'import euler014').timeit(10)

    16.590431928634644
    >>> timeit.Timer('euler014.f(10**7)', 'import euler014').timeit(1)

    17.689634084701538
    >>> timeit.Timer('euler014.g(10**6)', 'import euler014').timeit(10)

    13.558412790298462
    >>> timeit.Timer('euler014.g(10**7)', 'import euler014').timeit(1)

    14.075398921966553

    In this code only entries less than n (1000000 in the project Euler problem)
    are cached, and only one is cached per run of the inner loop, which to
    me would seem to me much less efficient. I supposed the advantages are no
    overhead from dict lookups, function calls, or recursion, plus it uses Terry
    Reedy's nice observation that one can take two steps at a time for odd
    values. I would think my version uses less memory as well, since the cache
    dict/list would be maximally dense for indices less than n in either scheme.

    I'm still surprised that both algorithm's seem pretty much O(n) tho.
    Intuitively I'd have thought mine would start to lose out with larger
    numbers, given the much lower degree of caching.

    With PyPy the results are more striking:

    Python 2.7.2 (1.9+dfsg-1, Jun 19 2012, 23:23:45)
    [PyPy 1.9.0 with GCC 4.7.0] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    And now for something completely different: ``Is rigobot around when the
    universe ceases to exist?''
    >>>> import timeit
    >>>> timeit.Timer('euler014.f(10**6)', 'import euler014').timeit(10)

    26.138880014419556
    >>>> timeit.Timer('euler014.g(10**6)', 'import euler014').timeit(10)

    1.5725858211517334

    I guess PyPy can JIT the iterative loop more effectively than it can the
    recursion.

    This is my first post on this list btw, please let me know if I screwed
    anything up.

    workshed
    workshed, Feb 20, 2013
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Christopher Benson-Manica
    Replies:
    0
    Views:
    413
    Christopher Benson-Manica
    May 11, 2004
  2. bithead

    MSDOS call with C#.net ?

    bithead, Apr 6, 2005, in forum: C++
    Replies:
    4
    Views:
    917
    bithead
    Apr 8, 2005
  3. Manfred Schwab
    Replies:
    5
    Views:
    1,159
    Chris Liechti
    Nov 6, 2004
  4. Crypto Loko
    Replies:
    3
    Views:
    296
    Crypto Loko
    Oct 16, 2005
  5. John Immarino

    Python 3.3 vs. MSDOS Basic

    John Immarino, Feb 18, 2013, in forum: Python
    Replies:
    33
    Views:
    349
    Tim Daneliuk
    Feb 20, 2013
Loading...

Share This Page