Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

For Project Euler problem 14 I wrote code that runs for longer than a minute to give the answer. After I studied about memoization, I wrote this code which runs for nearly 10 seconds on Cpython and nearly 3 seconds on PyPy. Can anyone suggest some optimization tips?

import time
d={}
c=0
def main():
    global c
    t=time.time()
    for x in range(2,1000000):
        c=0
        do(x,x)
    k=max(d.values())
    for a,b in d.items():
        if b==k:
            print(a,b)
            break

    print(time.time()-t)

def do(num,rnum):
    global d
    global c
    c+=1
    try:
        c+=d[num]-1
        d[rnum]=c
        return
    except:
        if num==1:
            d[rnum]=c
            return
        if num%2==0:
            num=num/2
            do(num,rnum)
        else:
            num=3*num+1
            do(num,rnum)

if __name__ == '__main__':
    main()
share|improve this question

3 Answers 3

up vote 4 down vote accepted

I think you're over complicating your solution, my approach would be something along these lines:

def recursive_collatz(n):
        if n in collatz_map:
                return collatz_map[n]
        if n % 2 == 0:
                x = 1 + recursive_collatz(int(n/2))
        else:
                x = 1 + recursive_collatz(int(3*n+1))
        collatz_map[n] = x
        return x

Basically define a memoization map (collatz_map), initialized to {1:1}, and use it to save each calculated value, if it's been seen before, simply return.

Then you just have to iterate from 1 to 1000000 and store two values, the largest Collatz value you've seen so far, and the number that gave you that value.

Something like:

largest_so_far = 1
highest = 0
for i in range(1,1000000):
    temp = recursive_collatz(i)
    if temp > largest_so_far:
        highest = i
        largest_so_far = temp

Using this approach I got:

Problem 14's answer is: 837799. Took 1.70620799065 seconds to calculate.

share|improve this answer

A bit faster version:

d:\python27\python test.py
(837799, 525)
10.3589999676

d:\python27\python test1.py
Index 837799, max value = 525, time 1.078000

using psyco:
d:\python25\python test1.py
Index 837799, max value = 525, time 0.078000

-

import time

try:
   import psyco
   psyco.full()
except:
   pass

SIZE = 1000000
d = [0]*SIZE
d[1] = 1

def calc(n):
    if n < SIZE:
        if d[n]: return d[n]
        if n & 1:
            d[n] = 1 + calc(n + (n << 1) + 1)
            return d[n]
        d[n] = 1 + calc(n >> 1)
        return d[n]
    if n & 1:
        return 1 + calc(n + (n << 1) + 1)
    return 1 + calc(n >> 1)

def main():
   stime = time.time()
   mi = 1
   mv = 1
   for i in xrange(2,SIZE):
      v = calc(i)
      if v > mv:
          mv = v
          mi = i
   print('Index %d, max value = %d, time %f' % (mi, mv, time.time()-stime))


if __name__ == '__main__':
    main()

PS. I would suggest you to solve the similar SPOJ problem: http://www.spoj.pl/problems/PROBTNPO/

share|improve this answer

The following may take as much time as your code, but its length has been considerably shortened.

def main():
    pool, used = set(range(2, 1000000)), {1: 1}
    while pool:
        number = pool.pop()
        values = reversed(tuple(collatz_generator(number, used)))
        length = dict(map(reversed, enumerate(values, used[next(values)] + 1)))
        pool -= frozenset(length)
        used.update(length)
    table = dict(map(reversed, used.items()))
    print(table[max(table)])

def collatz_generator(number, used):
    while True:
        yield number
        if number in used:
            break
        number = 3 * number + 1 if number & 1 else number >> 1

if __name__ == '__main__':
    main()
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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