Optimizing Python 3n + 1 Programming Challange
<p>I am trying to find a efficient solution for the 3n + 1 problem on <a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=3&amp;page=show_problem&amp;problem=36" rel="nofollow">uvaonlinejudge</a>. The code I have uses memoization using a dictionary. Can anyone suggest an improvement(s) that will help with the execution time of this code? At the moment I am getting a 'Time limit Exceeded' error when I submit the code. If anyone has a working solution to the problem please share it with me. PLEASE DON'T mark this post as DUPLICATE. I have already seen <a href="http://stackoverflow.com/questions/39401993/uva-online-judge-python-time-limit-exceeded">this</a> post and others on stackoverflow but they don't answer the question posted here. My code is as below:</p>

<pre><code>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 &lt;= b:
        m = recCycleLength(i, mydict)
        if m &gt; 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&gt;num2:
        num1, num2 = num2, num1
    m = maxCycle(num1, num2)
    print("{} {} {}".format(num1, num2, m))
</code></pre>

<p>The code seems to do the right thing to execute <code>maxCycle</code> optimally by caching all calculated results in <code>mydict</code>.</p>

<p>However, the input to the application consists of many pairs of values to be processed and <code>maxCycle</code> will reset <code>mydict = {}</code> and calculate everything from scratch.</p>

<p>I suggest remembering the results globally instead. A simple modification of the original code would be:</p>

<pre><code>cycLenDict = {}   # global dictionary

def recCycleLength(n):   # no cycLenDict argument
    if n==1:
        return 1
    if n not in cycLenDict:
        # ...

def maxCycle(a, b):
    # ...

    while i &lt;= b:
        m = recCycleLength(i)   # no myDict argument
</code></pre>

<p>To make everything a little bit nicer looking (without any difference performance-wise, compared to the solution above), make a decorator which remembers the results, so that the remainder of the code does not have to take care of that:</p>

<pre><code>def memoize(func):
    """decorate any function which takes positional arguments to cache its results"""

    func.results = {}  # results are stored globally as the funtion's attribute

    def memoized(*a):        # memoized version of func
        if a not in func.results:       # if not cached
            func.results[a] = func(*a)  # save to cache
        return func.results[a]          # return from cache
    return memoized


@memoize       # with this, recCycleLength is called only once for every n value
def recCycleLength(n):
    if n==1:
        return 1
    elif n%2==0:
        return recCycleLength(n//2) + 1
    else:
        return recCycleLength(3*n+1) + 1


def maxCycle(a, b):
    return max(recCycleLength(i) for i in range(a, b+1))
</code></pre>

python optimization