Python、ProjectEuler、最適化によりコードが遅くなります

Question

Project Eulerの質問14には次のコードを使用しました。この質問を知らない人は、「ステップ」の数が最大で100万以下の数字を見つけなければなりません。そのCollat​​zシーケンスで。

largen = 0 

for i in range (1, 1000000): 
    n = 0 
    k = i 
    while k != 1: 

     if k % 2 == 0: 
      k = k/2 
      n = n+1 


     else: 
      k = 3*k+1 
      n = n+1 

    if n > largen: 
     largen = n 
     answer = i 


print "Value with highest number of terms in collatz sequence is %d which has %d terms in its collatz sequence." % (answer, largen) 

これは私に約1m20sで正しい答えを与えます。しかし、私はこれを次のようにスピードアップできると思った。最初に、プログラムは、各値iについてcollat​​zシーケンスのステップ数を覚えておくように指示しました。次に、数kのための配列を見つける過程の中で、私が前の数に乗っているならば、私はその配列を計算しました。今のところk。

たとえば、シーケンスのステップ数を13として計算しようとしているとします。最初の3ステップは13-40-20-10です。今私はすでに10のシーケンスのステップ数は6であると計算しました（10-5-16-8-4-2-1）。したがって、13のシーケンスのステップ数は、10から1になるために必要な6に加えられる10に達するために取られた3、すなわち合計9ステップである。

この目的を達成するために、私は次のようにコードを修正：私は試してみて、これを実行すると

nterms = [] # for each value i, contains number of terms in collatz sequence 
used = [] # list of used values of i (so can add nterms[i-1] to collatz sequence which redirects to i) 

largen = 0 

for i in range (1, 1000000): 

    n = 0 
    k = i 
    while k != 1: 

     if k in used: 
      n = n+nterms[k-1] 
      break 

     elif k % 2 == 0: 
      k = k/2 
      n = n+1 

     else: 
      k = 3*k+1 
      n = n+1 

    if n > largen: 
     largen = n 
     answer = i 

    used.append(i) 
    nterms.append(n) 

print "Value with highest number of terms in collatz sequence is %d which has %d terms in its collatz sequence." % (answer, largen) 

は、しかし、私はMemoryErrorが端末画面にoutprinted得ます。小さな値（つまり10000まで）を試すと、元のコードと同じ回答が得られますが、はるかにゆっくりします（つまり、1秒ではなく7秒かかる）。

どうしてですか？

Answer 1

最適化の考え方は問題ありませんが、間違ったデータ構造を選択しました。

nterms = [] 
used = [] 

これらの2つのリストは、すでに計算したCollat​​zシーケンスを保存するために使用されます。しかし、リスト内の要素を見つけるためには、時間の複雑さはO（n）で十分効率的ではありません。

---

代わりに、辞書を使用してください。数字はキーで、値はCollat​​zシーケンスの数です。たとえば、10のキーの値は6です。

Answer 2

リスト内の要素を検索する操作はO（n）操作であり、大きなリストではかなり遅くなる可能性があります。辞書は、他の一方で、一定の検索時間の複雑さ（O（1））保証：私のマシン上で

cache = {} 

for i in range (1, 1000000): 
    n = 0 
    k = i 
    while k != 1: 

     if k in cache: 
      n = n + cache[k] 
      break 

     if k % 2 == 0: 
      k = k/2 
      n = n+1 


     else: 
      k = 3*k+1 
      n = n+1 


    cache[i] = n 
    if n > largen: 
     largen = n 
     answer = i 


print "Value with highest number of terms in collatz sequence is %d which has %d terms in its collatz sequence." % (answer, largen) 

を、このアプローチは、のために〜26秒から約13倍のソリューションを、スピードアップこの答えに提示されているもののOPは〜2秒になります。要素がリストから求めることができるかどうかをチェックするO（N）時間複雑性を有するので、kがusedから求めることができるかどうかの確認

Answer 3

、計算が遅くなります。

2つのリストを使用する代わりに、最初に1000000の要素を持つものだけを使用できます。すべての要素は、-1に初期化されています。このアプローチは、私のマシン上で10〜15％高速であるディクショナリ・キャッシュに比べ

largen = 0 
answer = 0 
memo = [-1] * 1000000 
for i in xrange(1, 1000000): 
    n = 0 
    k = i 
    while k != 1: 
     # Since k can grow from original need to check it's within bounds 
     if k < 1000000 and memo[k] != -1: 
      n += memo[k] 
      break 
     if k % 2 == 0: 
      k /= 2 
     else: 
      k = 3 * k + 1 

     n += 1 

    memo[i] = n 
    if n > largen: 
     largen = n 
     answer = i 

を：あなたはこのCollat​​z番号を知っていれば、あなたが後でそれを使用できるように、そして、すべての繰り返しで、あなたはそれぞれのインデックスにそれを更新します。