Collatz猜想脚本- Python

Question

我正在研究Euler项目档案中最长的Collatz问题，我不明白为什么我的问题花了这么长的时间。我把它与其他成功的脚本进行了比较，这些脚本通常只需几秒钟。

代码如下所示，但是思想是，对于给定范围内的每一个数字，程序开始野蛮地强迫下降。如果它在下降的任何一个点找到一个它已经看到的数字并计算出一个下降值，它只会将当前下降的长度添加到先前确定的下降点。

我看到的其他代码也是这样做的，我不明白为什么我的代码没有给它额外的速度。我运行它的范围高达1,000，它工作得很好，并给出了完全正确的答案，但是大约10,000,000它慢下来了，我的目标是1,000,000

说句公道话，我对编程非常陌生(在Python上工作了一周)，但我非常熟悉数论。

编辑:稍微修改代码，感谢Glibdud！

collatz_dic = {1:3}
d=1

for x in range(1,10001):
    collatz_list = [x]
    while x != 1:
        if x % 2 == 0:
            x = x/2
            collatz_list.append(x)
            if x in collatz_dic.keys() == True:
                collatz_dic[d] = ((len(collatz_list)-1) + collatz_dic.get(x))
            else:
                collatz_dic[d] = (len(collatz_list)-1)
        else:
            x = (3*x)+1
            collatz_list.append(x)
            if x in collatz_dic.keys() == True:
                collatz_dic[d] = ((len(collatz_list)-1) + collatz_dic.get(x))
            else:
                collatz_dic[d] = (len(collatz_list)-1)
    d = d+1

print(max(collatz_dic, key=collatz_dic.get))

Answer 1

此代码中更重要的逻辑缺陷是以下语句：

if x in collatz_dic.keys() == True:
    collatz_dic[d] = ((len(collatz_list)-1) + collatz_dic.get(x))
else:
    collatz_dic[d] = (len(collatz_list)-1)

(这两种情况都可能崩溃为一。)应该有一个break后的第一个collatz_dic[d]分配，因为你现在知道答案，所以停止你的循环！else子句不属于这里，而是应该是while循环的一个else子句，因为此时我们还不知道答案，所以为什么继续将当前值保存到字典中。

次要的编码问题：if的两部分中的大部分可以折叠成通用代码；collatz_list不需要是一个列表，只是一个计数器；您不想这样做：

if x in collatz_dic.keys() == True:

而是：

if x in collatz_dic:

因为当您手头有一个特别快的数据结构时，不需要构建一个新的数据结构来进行搜索。将所有这些修复与一些样式更改结合在一起，我们得到：

collatz_dic = {1: 3}

for d in range(2, 1_000_001):
    x = d

    collatz_count = 0

    while x != 1:
        if x % 2 == 0:
            x = x / 2
        else:
            x = 3 * x + 1

        collatz_count += 1

        if x in collatz_dic:
            collatz_count += collatz_dic[x]
            break

    collatz_dic[d] = collatz_count

print(max(collatz_dic, key=collatz_dic.get))

在不到5秒的时间内解决了100万(837,799)个问题，时间限制在1分钟之内。