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

Question

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

• 问题(来自 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
  

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

谢谢!

Answer 1

这个

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

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

你可以说。

if str(k) in dictionary:

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

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