Skip to main content
 首页 » 编程设计

Python 意外性能 : Brute Force vs Dictionaries (Collatz Sequence)

2025年05月04日17lexus

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

  • 问题(来自 Project-Euler ):

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

    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 结尾。

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

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

  • 代码 [蛮力]:

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

    然后我说:“时间太多了!我们来实现字典吧!”

  • CODE [词典]:

    使用Dictionaries,每次链结束时,链的起始编号和链 block 编号都存储在一个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 
    

字典是否有可能影响这个程序的性能,让它真的很慢?它们不是用来提高性能和加快程序速度的吗? 或者...我的代码有问题吗?

谢谢!

请您参考如下方法:

这个

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

不好。这会将键集变成一个列表!并线性扫描(在 python3 中,它是一个生成器,但几乎一样糟糕)。

你可以说。

if str(k) in dictionary: 

这在 O(1) 而不是 O(n) 中做了正确的事情!

此外,在 python 中不需要将事物转换为字符串以将它们用作 dict 中的键。数字就很好,所以你真的可以说:k 你当前说的任何地方 str(k)。