Python 意想不到的表现：蛮力与字典（Collatz 序列）

Question

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

问题（来自 Project-Euler）：

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

n → n/2 (n is even)

n → 3n + 1 (n is odd)

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

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

可以看出这个序列（从13开始到1结束）包含10项。虽然还没有证明（Collatz Problem），但是认为所有的起始数字都以1结束。

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

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

代码[蛮力]：

我从一个蛮力程序开始，该程序采用从 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

然后我说："It's too much time! Let's implement dictionaries!"

CODE [词典]:

使用Dictionaries，每次链结束时，链的起始编号和链块编号都存储在一个Dictionary中，所以当它多次找到相同的数字时，它可以使用关联的值这个数字存储在字典中。

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 你目前说的任何地方 str(k).

Python 意想不到的表现：蛮力与字典（Collatz 序列）

Python unexpected performance: Brute Force vs Dictionaries (Collatz Sequence)

python

performance

dictionary

brute-force

Python 意想不到的表现：蛮力与字典（Collat​​z 序列）

Python unexpected performance: Brute Force vs Dictionaries (Collatz Sequence)

python

performance

dictionary

brute-force

Python 意想不到的表现：蛮力与字典（Collatz 序列）