2

次のコードを使用して、Project Euler＃14を解決しました。

import time
start_time = time.time()
def collatz_problem(n):
    count = 0
    while n!=1:
        if n%2==0:
            n = n/2
            count = count+1
        elif n%2!=0:
            n = 3*n+1
            count = count +1
    return count+1


def longest_chain():
    max_len,num = 1,1
    for i in xrange(13,1000000):
        chain_length = collatz_problem(i)
        if chain_length > max_len:
            max_len = chain_length
            num = i

    return num

print longest_chain()
print time.time() - start_time, "seconds"

上記のソリューション~35 secondsを実行するのに時間がかかりました。今、私はここから別の解決策を試しました。

解決：

import time
start_time = time.time()
cache = { 1: 1 }
def chain(cache, n):
     if not cache.get(n,0):
         if n % 2: cache[n] = 1 + chain(cache, 3*n + 1)
         else: cache[n] = 1 + chain(cache, n/2)
     return cache[n]
m,n = 0,0
for i in xrange(1, 1000000):
    c = chain(cache, i)
    if c > m: m,n = c,i

print n
print time.time() - start_time, "seconds"

さて、この解決策はたったの~3.5 secondsです。

最初の質問：

さて、私はPythonの初心者なので、これら2つのアプローチに大きな違いがある理由と、コードを変更してより効率的にする方法がわかりません。

2番目の質問：

プロジェクトオイラーの質問を解決する際に留意すべき時間的制約があり、私のコードは本当に非効率的です。

4

1 に答える 1

8

最初のバージョンでは、一部のチェーンは他のチェーンのサブチェーンであるため、いくつかのチェーンの長さを数回計算する場合があります。

2 番目のソリューションでは、キャッシングのために各チェーンの長さを 1 回だけ計算しています。この最適化手法はメモ化と呼ばれます。

メモ化のより劇的な例は、フィボナッチ数の計算です。簡単な再帰的な解決策は次のとおりです。

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

はとを評価するだけでなくも評価するfib(n)ため、指数関数的な時間がかかるため、まったく同じ計算を再度行うことになります。このアルゴリズムで以上を計算してみてください。fib(n-1)fib(n-2)fib(n-1)fib(n-2)fib(35)

fib(x)for eachの結果をキャッシュすることでx、同じ結果を再計算することを避け、パフォーマンスを線形時間に改善できます。

def fib2(n):
    if n < 2:
        return n
    elif n in cache:
        return cache[n]
    else:
        result = fib2(n-1) + fib2(n-2)
        cache[n] = result
        return result

関連している

于 2012-07-28T08:15:22.933 に答える