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

Answer 2

这不是最优雅的解决方案，但会帮助您了解其工作原理。

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 apt-get install python-memcache 运行此代码