解释如何在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

这还不是最完美的解决方案，但会帮助你学习如何工作的。

import memcache 

def fib(n): 
    v = mc.get(str(n)) 
    if not v is None: 
     print "Hit on cache: %s = %s" %(n, v) 
     return v 

    print "Miss on cache" 
    if n == 0: 
     return 0 
    elif n == 1: 
     return 1 
    else: 
     v = fib(n-1) + fib(n-2) 
     mc.set(str(n), v) 
     return v 

mc = memcache.Client(['127.0.0.1:11211'], debug=0) 
x=input('which fibonnaci do you want?') 
print fib(x) 

如果您在Ubuntu：sudo易于得到安装python-memcache中运行该代码

Answer 2

这种装饰你的函数：

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) 

UPDATE

这只有在Python3.2 +

作品对于一个补丁包，结账此页：http://code.activestate.com/recipes/578078-py26-and-py30-backport-of-python-33s-lru-cache/