python - Project Euler p14 增强性能

Question

我已经使用以下代码完成了项目欧拉问题 14:

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] 

获得最长的 Collat​​z 大约需要 39 秒 从 1000000 到 2 的数字序列。我想知道我是否可以缓存任何值来加速我的代码，以及如何从我的代码中删除 if longestSequence[-1] == 2 而不会出现无限循环以及可以改进代码的任何其他方式。

为正整数集定义了以下迭代序列:

n → n/2(n 为偶数)n → 3n + 1(n 为奇数)

使用上述规则并从 13 开始，我们生成以下序列:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1可以看出，这个序列(从 13 开始到 1 结束)包含 10 个项。尽管尚未证明(Collat​​z Problem)，但认为所有起始数字都以 1 结尾。

哪个起始数(小于一百万)产生最长的链？

注意:一旦链开始，条款就可以超过一百万。

Answer 1

每次您在序列中生成一个项目时，您也会为那个项目生成项目。例如，对于 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 或以下数字的结果)，这仍然可以显着提高速度但使用更少的内存。

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