Python、ProjectEuler、优化使代码变慢

Question

我用下面的代码来解决欧拉计划问题 14。对于那些不知道这个问题的人，我必须找到它的 Collat​​z 序列中“步”数最多的低于一百万的数字。

largen = 0

for i in range (1, 1000000):
    n = 0
    k = i
    while k != 1:

        if k % 2 == 0:
            k = k/2
            n = n+1


        else:
            k = 3*k+1
            n = n+1

    if n > largen:
        largen = n
        answer = i


print "Value with highest number of terms in collatz sequence is %d which has %d terms in its collatz sequence." % (answer, largen)

这会在大约 1 分 20 秒内给出正确答案。但是我认为我可以通过以下方式加快速度。首先，我指示程序记住每个值 i 的 collat​​z 序列中的步骤数。然后，如果在查找数字 k 的序列的过程中，我找到了我计算序列的前一个数字 i，我只需将 i 的序列中的项数添加到我计算的数字到目前为止 k。

例如，假设我要计算 13 序列中的步数。前 3 个步是 13-40-20-10。现在我已经计算出 10 的序列中的步骤数是 6 (10-5-16-8-4-2-1)。因此，13 的序列中的步数是从 10 到 1 所需的 6 加上从 10 到 1 所需的 3，即总共 9 步。

为此，我将代码修改为:

nterms = [] # for each value i, contains number of terms in collatz sequence
used = [] # list of used values of i (so can add nterms[i-1] to collatz sequence which redirects to i)

largen = 0

for i in range (1, 1000000):

    n = 0
    k = i
    while k != 1:

        if k in used:
            n = n+nterms[k-1]
            break

        elif k % 2 == 0:
            k = k/2
            n = n+1

        else:
            k = 3*k+1
            n = n+1

    if n > largen:
        largen = n
        answer = i

    used.append(i)
    nterms.append(n)

print "Value with highest number of terms in collatz sequence is %d which has %d terms in its collatz sequence." % (answer, largen)

但是，当我尝试运行它时，我将 MemoryError 输出到终端屏幕。当我尝试使用较小的值(即最多 10000)时，我得到的答案与我的原始代码片段相同，但速度要慢得多(即需要 7 秒而不是 1 秒)。

为什么会这样？

Answer 1

优化的思路很好，但是你选错了数据结构。

nterms = []
used = []

这两个列表是用来存储你已经算出来的Collat​​z序列的吧？但是在列表中查找一个元素，时间复杂度为O(n)，效率不够。

---

相反，尝试使用字典，数字是键，Collat​​z 序列的编号作为值。例如，键 10 的值为 6。