9
\$\begingroup\$

I am trying to find a efficient solution for the 3n + 1 problem on uvaonlinejudge. The code I have uses memoization using a dictionary. I am getting a 'Time limit Exceeded' error when I submit the code. Can anyone suggest an improvement(s) that will help with the execution time of this code.

I have already seen this post and implemented the proposed improvements. All other posts related to this are either for C++ or Java.

import sys

def recCycleLength(n,cycLenDict):
    if n==1:
        return 1
    if n not in cycLenDict:
        if n%2==0:
            cycLen = recCycleLength(n//2, cycLenDict)
            cycLenDict[n] = cycLen + 1
            return cycLen+1
        else:
            cycLen = recCycleLength(3*n+1, cycLenDict)
            cycLenDict[n] = cycLen + 1
            return cycLen+1
    else:
        return cycLenDict[n]


def maxCycle(a, b):
    i = a
    mydict = {} 
    maxLength = 1
    while i <= b:
        m = recCycleLength(i, mydict)
        if m > maxLength:
            maxLength = m
        i = i + 1
    return maxLength


for line in sys.stdin:
    curr_line=line.split()
    num1 = int(curr_line[0])
    num2 = int(curr_line[1])
    if num1>num2:
        num1, num2 = num2, num1
    m = maxCycle(num1, num2)
    print("{} {} {}".format(num1, num2, m))
\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review. Hope you get good answers. \$\endgroup\$ – Siobhan Oct 10 '16 at 20:09
  • 1
    \$\begingroup\$ You should probably read up on the PEP8 Style Rules for Python - there's some stuff that seem to be violating PEP8 (function names). Also this is for Python 3 yes? \$\endgroup\$ – Thomas Ward Oct 10 '16 at 22:46
  • \$\begingroup\$ what times do you achive for 1<x<10**6? \$\endgroup\$ – Simon Oct 11 '16 at 9:55
  • \$\begingroup\$ for 1<x<10**6 I am getting a time of 2.5-2.7 seconds. The brute force C implementation (using no memoization) takes around 0.5 seconds \$\endgroup\$ – Omar Khan Oct 12 '16 at 7:41
6
\$\begingroup\$

You should separate your responsibilities. Currently your function recCycleLength (which should be named rec_cycle_length to conform with Python's official style guide PEP8) does two things, calculating the return value and caching it in a passed dictionary. It would be better to outsource the latter to a decorator, like this one (which is the fastest memoization decorator for a single-valued function I know of):

def memodict(f):
    """ Memoization decorator for a function taking a single argument """
    class memodict(dict):
        def __missing__(self, key):
            ret = self[key] = f(key)
            return ret
    return memodict().__getitem__


@memodict
def rec_cycle_length(n): 
    if n == 1: 
        return 1
    elif n % 2 == 0: 
        return cyc_len = rec_cycle_length(n//2) + 1
    return rec_cycle_length(3*n+1) + 1

You can even use this decorator on maxCycle when changing it to accept only one argument, the tuple (a, b). You could also be using max with a generator expression here:

@memodict
def max_cycle(bounds):
    a, b = bounds
    return max(rec_cycle_length(n) for n in range(a, b + 1))

(Use xrange in case you are using python 2.x.)

Your code on module level should be guarded by a if __name__ == '__main__': guard. You could also use map and sorted to get rid of quite a few lines of code:

if __name__ == '__main__':
    for line in sys.stdin:
        bounds = tuple(sorted(map(int, line.split())))
        print(" ".join(bounds), max_cycle(bounds))

This allows you to do e.g. from filename import rec_cycle_length in another script to reuse a function defined here.

Note that even though str.format is awesome, it is not needed here.


Since you seem to be using python 3.x, you might want to use functools.lru_cache instead of this decorator, like so:

import functools

@functools.lru_cache(2**10)
def rec_cycle_length(n):
    ...

At least on my machine it is a lot faster for some use cases (because the cache will not grow without bounds, making it better when there are few repetitions, i.e. many cache misses.) It is, however, only included in python >= 3.3.

\$\endgroup\$
  • \$\begingroup\$ long time no see. Could the memorization be done with decorators in such a way that 5->16->8->4->2->1 not only save 5, but also path length for 16, 8, 4, 2? \$\endgroup\$ – Simon Oct 11 '16 at 8:58
  • \$\begingroup\$ yeah I went ahead and confirmed that realizing that the decorator toke the dict as super. Confirmed this magic. But dict don't have a __missing__() called by __getitem__(), how does that work? And the garbage collector don't collect because of the call to __getitem__() in the return statement? \$\endgroup\$ – Simon Oct 11 '16 at 9:26
  • \$\begingroup\$ I have already tried functools.lru_cache but had no luck. I beginning to think that the uvaonlinejudge system has not been adjusted for Python. \$\endgroup\$ – Omar Khan Oct 11 '16 at 9:47
  • \$\begingroup\$ Ah, I remember reading that section, d[key], apparently not realizing it's potential. \$\endgroup\$ – Simon Oct 11 '16 at 9:49
  • \$\begingroup\$ by 'no luck' I mean I am still getting the 'Time limit Exceeded' error. Yes I am beginning to suspect that they have not accounted for the slowness of python. A brute force (no memoization) implementation in C is accepted by the uvaonlinejudge system but my python implementation is not. I measured the execution time for both the C and Python solution and Python is around 4 times slower. \$\endgroup\$ – Omar Khan Oct 12 '16 at 7:38
4
\$\begingroup\$

Your performance problem is that you throw away the memoization cache after each test case.

Also, in Python, iteration should be more efficient than recursion.

\$\endgroup\$
  • \$\begingroup\$ yes you are right, it got accepted when I corrected this flaw(plus another, I was printing the output in the wrong sequence). I also implemented a iterative version with memoization, but surprisingly it takes more time than the recursive version. Thanks \$\endgroup\$ – Omar Khan Oct 12 '16 at 9:57
0
\$\begingroup\$

after changes suggested by 200_success, here is the code that got accepted:

import sys

def recCycleLength(n,cycLenDict):
    if n==1:
        return 1
    if n not in cycLenDict:
        if n%2==0:
            cycLen = recCycleLength(n//2, cycLenDict)
            cycLenDict[n] = cycLen + 1
            return cycLen+1
        else:
            cycLen = recCycleLength(3*n+1, cycLenDict)
            cycLenDict[n] = cycLen + 1
            return cycLen+1
    else:
        return cycLenDict[n]


def maxCycle(a, b, mydict):
    i = a
    maxLength = 1
    while i <= b:
        m = recCycleLength(i, mydict)
        if m > maxLength:
            maxLength = m
        i = i + 1
    return maxLength

memDict = {1:1}
for line in sys.stdin:
    curr_line=line.split()
    num1 = int(curr_line[0])
    num2 = int(curr_line[1])
    if num1>num2:
        num1, num2 = num2, num1
    m = maxCycle(num1, num2, memDict)
    print("{} {} {}".format(num1, num2, m))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.