oheyandy

collatz.py

import time
bound,mem = 1000000,{}

def collatz(n): 
    if n==1: return [1]
    else: return [n] + collatz(n/2 if (n%2==0) else 3*n+1) if (n>1) else [1] 

def collatzCount_recursive_memoized(n):
    if n not in mem: mem[n]= 1 + collatzCount_recursive_memoized(n/2 if (n%2==0) else 3*n+1) if (n>1) else 1
    return mem[n] 

def collatzCount_iterative(n):
    count = 1
    if n ==1:
        return count
    while n !=1:
        if n%2 == 0:
            count +=1
            n = n/2
        else:
            count +=1
            n = (n*3) + 1
    return count

iterative_mem = {}
iterative_mem[1] = 1
def collatzCount_iterative_memoized(n):
    count = 1
    initial_n = n
    while n not in iterative_mem:
        if n%2 == 0:
            count +=1
            n = n/2
        else:
            count +=1
            n = (n*3) + 1
    iterative_mem[initial_n] = count + iterative_mem[n]
    return iterative_mem[initial_n]

iterative_mem_pedantic = {}
iterative_mem_pedantic[1] = 1
def collatzCount_iterative_memoized_pedantic(n):
    count = 1
    initial_n = n
    while not iterative_mem_pedantic.get(n,False):
        if n%2 == 0:
            count +=1
            n = n/2
        else:
            count +=1
            n = (n*3) + 1
    iterative_mem_pedantic[initial_n] = count + iterative_mem_pedantic[n]
    return iterative_mem_pedantic[initial_n]

iterative_mem_pedantic_without_dot = {}
iterative_mem_pedantic_without_dot[1] = 1
get_direct = iterative_mem_pedantic_without_dot.get
def collatzCount_iterative_memoized_pedantic_without_dot(n):
    count = 1
    initial_n = n
    while not get_direct(n,False):
        if n%2 == 0:
            count +=1
            n = n/2
        else:
            count +=1
            n = (n*3) + 1
    iterative_mem_pedantic_without_dot[initial_n] = count + iterative_mem_pedantic_without_dot[n]
    return iterative_mem_pedantic_without_dot[initial_n]


def test(f,bound,number_of_runs):
    total_time = 0
    for i in range(number_of_runs):
        total_time += single_time(f,bound)
    print total_time/number_of_runs,"for",f.__name__

def single_time(f,bound):
    time1 = time.time()
    biggest_sequence =  len(collatz(max(((i,f(i)) for i in xrange(1,bound)),key=lambda x: x[1])[0]))
    print biggest_sequence
    return time.time()-time1

#test(collatzCount_recursive_memoized,10**4,10)
#test(collatzCount_iterative,10**4,10)
test(collatzCount_iterative_memoized,10**4,10)
test(collatzCount_iterative_memoized_pedantic,10**4,10)
test(collatzCount_iterative_memoized_pedantic_without_dot,10**4,10)

guess there's just too much overhead in a while loop versus recursive calls. Did not expect that.