使用Python标准库functools中的lru_cache实现缓存

原创

杜逸先

发布于 2018-05-31 15:17:59

2.4K1

发布于 2018-05-31 15:17:59

很多人在学习递归的时候都写过斐波那契数列的递归函数，最直接的版本是这样的。

def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

很简单，也很容易理解，但是不难发现这个函数在计算斐波那契数列的时候事实上进行了很多重复计算，例如：

fib(4) = fib(3) + fib(2) = fib(2) + fib(1) + fib(1) + fib(0) = fin(1) + fib(0) + fib(1) + fib(1) + fib(0) = 5

计算fib(4)要计算一次fib(3), 两次fib(2), 两次fib(1),两次fib(0)。而n更大的话重复计算的次数更多。

因而我个人一般是通过生成器来产生斐波那契数列的。

def fib():
    prev, current = 1, 1
    while True:
        yield prev
        prev, current  = current, prev + current

可以直接通过for循环使用生成器：

for num in fib():
    pass

或者一次获得很多个斐波那契数列的项：

fibs = dict(zip(range(20), fib()))

但一个可以直接通过fib(n)使用的函数毕竟还是很方便，为了减少重复计算，我们可以使用全局变量做缓存：

fib_cache = [1, 1]
def fib(n):
    if n > len(fib_cache) - 1:
        fib_cache.append(fib(n - 1) + fib(n - 2))
    return fib_cache[n]

或者使用一个类：

class Fib:
    cache = [1, 1]
    def __call__(self, n):
        if n > len(self.cache) - 1:
            self.cache.append(self(n - 1) + self(n - 2))
        return self.cache[n]
# fib = Fib()
# fib(10) == 89

这些方式毕竟还是有点繁琐，这时候就到本文的主角登场了，functools.lru_cache，看一下它的文档。

Signature: lru_cache(maxsize=128, typed=False)
Docstring:
Least-recently-used cache decorator.

If *maxsize* is set to None, the LRU features are disabled and the cache
can grow without bound.

If *typed* is True, arguments of different types will be cached separately.
For example, f(3.0) and f(3) will be treated as distinct calls with
distinct results.

Arguments to the cached function must be hashable.

View the cache statistics named tuple (hits, misses, maxsize, currsize)
with f.cache_info().  Clear the cache and statistics with f.cache_clear().
Access the underlying function with f.__wrapped__.

See:  http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used
File:      ~/.local/share/virtualenvs/notebook-yiSh32rr/lib/python3.6/functools.py
Type:      function

可以看出lru_cache使用了LRU算法，在maxsize大小的空间内缓存函数的结果，值得一提的事函数的参数是要可以哈希的，接下来我们利用lru_cache改进我们的递归算法，非常的简单。

from functools import lru_cache
@lru_cache(100)
def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

maxsize设置为100就够了，fib(100)已经是573147844013817084101了。

我们可以比较一下这几种方案的效率。

可见使用lru_cache的效率是最高的，直接递归的效率低的惊人，毕竟是指数级别的时间复杂度。全局变量缓存和类的方案因为有很多自己写的赋值代码和list类的函数调用，会稍微慢一点。生成器的方案因为不方便直接计算fib(n)，要配合range函数使用，会慢上一个数量级，不过在合适的场景下生成器反而会很合适。

lru_cache比起成熟的缓存系统还有些不足之处，比如它不能设置缓存的时间，只能等到空间占满后再利用LRU算法淘汰出空间出来，并且不能自定义淘汰算法，但在简单的场景中很适合使用，就像本文的例子中写出简单直接的递归算法而不用担心其效率。

最后祝大家享受生活，享受代码。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python