2

キャッシュ（辞書）を使用してフィボナッチ数を計算するためのこのコードがあります。

cache = {} 
def dynamic_fib(n):
    print n
    if n == 0 or n == 1:
        return 1
    if not (n in cache):
        print "caching %d" % n
        cache[n] = dynamic_fib(n-1) + dynamic_fib(n-2)

    return cache[n]

if __name__ == "__main__":
    start = time.time()
    print "DYNAMIC: ", dynamic_fib(2000)
    print (time.time() - start)

小さい数字では問題なく動作しますが、入力が 1000 を超えると停止するようです。

2000を入力した結果です。

....
caching 1008
1007
caching 1007
1006
caching 1006
1005
caching 1005

1000を入力した結果です。

....
8
caching 8
7
caching 7
6
caching 6
5
caching 5

ディクショナリに 995 保存した後、ハングするようです。これで何が間違っている可能性がありますか？Python で何が問題なのかを確認するには、どのデバッグ手法を使用できますか?

私は Mac OS X 10.7.5 で python を実行しています。私は 4G バイトの RAM を持っているので、メモリ使用量の KB (または MB) はあまり重要ではないと思います。

4

4 に答える 4

2

キャッシュをディクショナリとして保存しても、実際には何も得られません。計算するには、 (および)f(n)を知る必要があるためです。つまり、辞書には常に 2-n のキーがあります。代わりにリストを使用することもできます (追加の 2 つの要素のみです)。これは、適切にキャッシュされ、再帰制限に達しないバージョンです (これまで):f(n-1)f(n-2)

import time
cache = [1,1]

def dynamic_fib(n):
    #print n
    if n >= len(cache):
        for i in range(len(cache),n):
            dynamic_fib(i)

        cache.append(dynamic_fib(n-1) + dynamic_fib(n-2))
        print "caching %d" % n

    return cache[n]

if __name__ == "__main__":
    start = time.time()
    a = dynamic_fib(4000)
    print "Dynamic",a
    print (time.time() - start)

dict でも同じことができることに注意してください。ただし、リストの方が高速になることはほぼ確実です。

楽しみのために、ここにたくさんのオプション (およびタイミング!) があります。

def fib_iter(n):
    a, b = 1, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

memo_iter = [1,1]
def fib_iter_memo(n):
    if n == 0:
        return 1
    else:
        try:
            return memo_iter[n+1]
        except IndexError:
            a,b = memo_iter[-2:]
            for i in xrange(len(memo_iter),n+2):
                a, b = b, a + b
                memo_iter.append(a)
            return memo_iter[-1]

dyn_cache = [1,1]
def dynamic_fib(n):
    if n >= len(dyn_cache):
        for i in xrange(len(dyn_cache),n):
            dynamic_fib(i)

        dyn_cache.append(dynamic_fib(n-1) + dynamic_fib(n-2))

    return dyn_cache[n]

dyn_cache2 = [1,1]
def dynamic_fib2(n):
    if n >= len(dyn_cache2):
        for i in xrange(len(dyn_cache2),n):
            dynamic_fib2(i)

        dyn_cache2.append(dyn_cache2[-1] + dyn_cache2[-2])

    return dyn_cache2[n]

cache_fibo = [1,1]
def dyn_fib_simple(n):
   while len(cache_fibo) <= n:
        cache_fibo.append(cache_fibo[-1]+cache_fibo[-2])
   return cache_fibo[n]

import timeit
for func in ('dyn_fib_simple','dynamic_fib2','dynamic_fib','fib_iter_memo','fib_iter'):
    print timeit.timeit('%s(100)'%func,setup='from __main__ import %s'%func),func


print fib_iter(100)
print fib_iter_memo(100)
print fib_iter_memo(100)
print dynamic_fib(100)
print dynamic_fib2(100)
print dyn_fib_simple(100)

そして結果：

0.269892930984 dyn_fib_simple
0.256865024567 dynamic_fib2
0.241492033005 dynamic_fib
0.222282171249 fib_iter_memo
7.23831701279 fib_iter
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
于 2013-01-03T18:16:05.820 に答える
2

Python のデフォルトの再帰制限は 1000 に設定されています。プログラムでそれを増やす必要があります。

import sys

sys.setrecursionlimit(5000)

から: http://docs.python.org/2/library/sys.html#sys.setrecursionlimit

sys.setrecursionlimit(制限)

Set the maximum depth of the Python interpreter stack to limit. 
This limit prevents infinite recursion from causing an overflow of the C 
stack and crashing Python.
The highest possible limit is platform-dependent. A user may need to set the
limit higher when she  has a program that requires deep recursion and a 
platform that supports a higher limit. This should bedone with care, because
a too-high limit can lead to a crash.
于 2013-01-03T17:59:12.180 に答える
1

再帰のないバージョン:

def fibo(n):
   cache=[1,1]
   while len(cache) < n:
       cache.append(cache[-1]+cache[-2])
   return cache
于 2013-01-03T18:30:45.723 に答える
0

おそらく、スタックの深さの制限が原因で、RuntimeError が発生します。呼び出すことで、スタックの再帰制限を増やすことができます

sys.setrecursionlimit(<number>)

sysモジュールの。

于 2013-01-03T18:01:47.920 に答える