0

I have completed project Euler problem 14 with the following code:

def longest_Collatz_sequence():
    """
    returns longest Collatz
    sequence based on formula:
    n --> n/2 (n is even)
    n --> 3n + 1 (n is odd)
    """
    bestSequence = []
    lengthOfLongest = 0
    longestSequence = []
    for n in range(999999,1,-1):
        while n != 1:
            l = len(longestSequence)
            if n % 2 == 0:
                longestSequence.append(n)
                n /= 2
            elif n % 2 != 0:
                longestSequence.append(n)
                n = (n * 3) + 1
            if longestSequence[-1] == 2 and lengthOfLongest < l:  
                lengthOfLongest = l
                bestSequence = longestSequence[:]
                bestSequence.append(1)       
        longestSequence = []
    return bestSequence[0]

It takes around 39 seconds to get the longest Collatz sequence of numbers from 1000000 down to 2. I would like to know if I could be caching any values to speed up my code, also how to remove if longestSequence[-1] == 2 from my code without getting an infinite loop and any other ways the code can be improved.

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

4

1 回答 1

2

每次在序列中生成一个项目时，您也在为该项目生成项目。例如，对于 13，您会发现它产生 10 个项目。但是在这个过程中你也会发现 40 产生 9 个项目，20 产生 8 个项目，10 产生 7 个项目，等等。你可以在列表或字典中记住这些信息，这样在做 13 之后，你就不必再看 40 、20、10、5、16、4 或 2。

此外，当您生成以前从未见过的序列时，您可以查看此信息并将其用作快捷方式。对于 13，您在看到 13 之前已经看到了 10，因此您只需计算 40、20、10，然后您知道 10 产生 7 个项目，因此您只需将其添加到您已经看到的 3 中，而无需费心计算休息。

这将使用相当多的内存，但对于您必须考虑的项目数量来说它是完全可行的。您可以有某种截止（例如，仅存储数字 100,000 或以下的结果），它仍然可以实现很大的速度提高，但使用更少的内存。

一种简单的方法是重写你的函数以递归地而不是迭代地计算序列，然后应用一个 memoization 装饰器，例如this one。递归有一些开销，但记忆化的好处可能会超过这个。

于 2013-10-19T18:35:15.200 回答