解释如何在Python中使用内存缓存

Question

对于第 n 个斐波那契数，我有以下递归解决方案：

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

x=input('which fibonnaci do you want?')
print fib(x)

我需要更改此设置，以便它使用存储的内存缓存并从中获取内容以加快进程。我真的不知道该怎么做，谷歌也没有帮助。

Answer 1

用这个装饰你的函数：

http://docs.python.org/3/library/functools.html#functools.lru_cache

事实上，文档中的示例之一是斐波那契：

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

这使：

>>> [fib(n) for n in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

>>> fib.cache_info()
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)

更新

这只适用于Python3.2+

对于向后移植，请查看此页面：http://code.activestate.com/recipes/578078-py26-and-py30-backport-of-python-33s-lru-cache/