Project Euler #14 - Longest Collatz sequence

Longest Collatz sequence

13->40->20->10->5->16 ... 이렇게 해서 13:10을 찾았다면, 40:9, 20:8 도 메모리에 저장해 두고, 나중에 20이나 40이 나왔을 때 다시 계산하지 않도록 한다. 이런 식이라면, 이미 10:7이 메모리에 있었을테니, 13에 대해 10번 계산이 아니라 세 번 계산만에 13:10을 찾을 수 있다.

def collatz(n,cDic):
    m = n
    i = 0
    tl = [n]
    while True:
        if m in cDic:
            for s, t in enumerate(tl[::-1]):
                cDic[t] = s + 1 + cDic[m]
            return
        if m % 2 == 0: m = m / 2
        else: m = 3 * m + 1
        tl.append(m)
        i += 1

cDic = {1:1}
for i in range(2,1000000):
    collatz(i,cDic)

print max(cDic, key=cDic.get)

이렇게 하면 4.3초...
그런데, 13:10만 저장하고 40:9, 20:8 을 저장 안 하면 속도가 더 빨라진다. 아래 코드는 2.7초..
tl 이라는 리스트에 값을 하나씩 더하고 다시 꺼내는 데 드는 비용이 cache 비용보다 더 많이 드나보다.

def collatz(n,cDic):
    m = n
    i = 0
    while True:
        if m in cDic:
            cDic[n] = i + cDic[m]
            return
        if m % 2 == 0: m = m / 2
        else: m = 3 * m + 1
        i += 1

cDic = {1:1}
for i in range(2,1000000):
    collatz(i,cDic)

print max(cDic, key=cDic.get)