Python意想不到的性能：蛮力vs字典（Collatz Sequence）

Question

有没有可能字典在这个问题上比蛮力慢？

>

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

<代码>n→ n/2（n为偶数）

<代码>n→ 3n 1（n为奇数）

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

13→40→20→10→5→16→8→4→2→1

可以看出，该序列（从13开始，到1结束）包含10个术语。虽然这还没有被证明（科拉兹问题），但人们认为所有的起始数字都以1结束。

100万以下的哪个起始数字产生的链条最长？

注：一旦链开始，条款允许超过一百万。

代码[暴力]：

我从一个蛮力程序开始，该程序从1到1000000取每个数字，并打印找到的最长链。

大约需要30秒才能完成。

# number from 1 to 1000000
num = 0

# longest chain here
maxLength = 0

# number that produce the longest chain
result = 0

while num < 1000000:
    num += 1
    k = num

    # count the current chain pieces
    i = 0

    while k > 1:
        i += 1
        if k%2 == 0:
            k /= 2
        else:
            k = k*3 + 1

    if maxLength < i:
        maxLength = i
        result = num

print result

然后我说：“时间太多了！让我们实现字典吧！”

代码[词典]：

对于字典，每次链结束时，链的起始编号和链件编号都存储在字典中，因此当它多次找到相同的编号时，可以使用字典中存储的与此编号关联的值。

5分钟后，我停止了它。

# number from 1 to 1000000
num = 0

# longest chain here
maxLength = 0

# number that produce the longest chain
result = 0

dictionary = {}

while num < 1000000:
    num += 1
    k = num
    i = 0
    while k > 1:
        # if it processed the number before, it use the shortcut
        if str(k) in dictionary.keys():
            i += dictionary[str(k)]
            break

        i += 1
        if k%2 == 0:
            k /= 2
        else:
            k = k*3 + 1

    # add new shortcut
    if not (str(num) in dictionary.keys()):
        dictionary[str(num)] = i

    if maxLength < i:
        maxLength = i
        result = num

print result

字典是否可能会影响此程序的性能，使其变得非常缓慢？它们不是用来提高性能和加速程序吗？或我的代码有问题吗？

谢谢

Answer 1

这个

if str(k) in dictionary.keys():
#                      ^^^^^

很糟糕。这将一组键转换为list！并在线扫描（在python3中，它是一个生成器，但几乎同样糟糕）。

你可以说。

if str(k) in dictionary:

这是正确的，在O（1）而不是O（n）中！

此外，在python中，将事物转换为字符串并将其用作dict中的键是不必要的。数字很好，所以您可以在当前所说的任何地方都说：k。