Python意外的表現：蠻力vs字典（Collat​​z序列）

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個術語。儘管尚未證明（Collat​​z問題），但認爲所有起始數字都以1結束。

  哪一個起始數字低於100萬，會產生最長的鏈？

  注：一旦鏈條開始，條款允許超過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 
  

  然後我說：「這是太多的時間讓我們實現字典！」

• CODE [字典]：

  使用詞典，每一個鏈末端，鏈的起始數和鏈段數被存儲在字典時間，所以當它發現比相同數目更有一次，它可以使用與存儲在字典中的這個數字相關的值。

  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！並掃描那lineraly（在python3，它是一個生成器，但幾乎一樣糟糕）。

你可以說。

if str(k) in dictionary: 

並且做正確的事情，在O（1）而不是O（n）！

此外，在python中將東西轉換爲字符串以在dict中使用它們作爲關鍵字是不必要的。數字很​​好，所以你可以說：k無論你目前在說什麼str(k)。