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

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 回答
2

通过将缓存存储为字典，您并没有真正获得任何收益，因为为了计算f(n)您需要知道f(n-1)(and f(n-2))。换句话说，你的字典总是有来自 2-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 回答
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 回答