Python 中 lru_cache 的使用和实现
在计算机软件领域,缓存(Cache)指的是将部分数据存储在内存中,以便下次能够更快地访问这些数据,这也是一个典型的用空间换时间的例子。一般用于缓存的内存空间是固定的,当有更多的数据需要缓存的时候,需要将已缓存的部分数据清除后再将新的缓存数据放进去。需要清除哪些数据,就涉及到了缓存置换的策略,LRU(Least Recently Used,最近最少使用)是很常见的一个,也是 Python 中提供的缓存置换策略。
下面我们通过一个简单的示例来看 Python 中的 lru_cache 是如何使用的。
上面的代码中定义了函数 factorial,通过递归的方式计算 n 的阶乘,并且在函数调用的时候打印出 n 的值。然后分别计算 5 和 3 的阶乘,并打印结果。运行上面的代码,输出如下
可以看到,factorial(3)
的结果在计算 factorial(5)
的时候已经被计算过了,但是后面又被重复计算了。为了避免这种重复计算,我们可以在定义函数 factorial 的时候加上 lru_cache 装饰器,如下所示
重新运行代码,输出如下
可以看到,这次在调用 factorial(3)
的时候没有打印相应的输出,也就是说 factorial(3)
是直接从缓存读取的结果,证明缓存生效了。
被 lru_cache 修饰的函数在被相同参数调用的时候,后续的调用都是直接从缓存读结果,而不用真正执行函数。下面我们深入源码,看看 Python 内部是怎么实现 lru_cache 的。写作时 Python 最新发行版是 3.9,所以这里使用的是 Python 3.9 的源码,并且保留了源码中的注释。
这段代码中有如下几个关键点
关键字参数
maxsize
表示缓存容量,如果为 None
表示容量不设限, typed
表示是否区分参数类型,注释中也给出了解释,如果 typed == True
,那么 f(3)
和 f(3.0)
会被认为是不同的函数调用。
第 24 行的条件分支
如果 lru_cache 的第一个参数是可调用的,直接返回 wrapper,也就是把 lru_cache 当做不带参数的装饰器,这是 Python 3.8 才有的特性,也就是说在 Python 3.8 及之后的版本中我们可以用下面的方式使用 lru_cache,可能是为了防止程序员在使用 lru_cache 的时候忘记加括号。
注意,Python 3.8 之前的版本运行上面代码会报错:TypeError: Expected maxsize to be an integer or None。
lru_cache 的具体逻辑是在 _lru_cache_wrapper 函数中实现的,还是一样,列出源码,保留注释。
函数开始的地方 2~14 行定义了一些关键变量
hits
和misses
分别表示缓存命中和没有命中的次数root
双向循环链表的头结点,每个节点保存前向指针、后向指针、key 和 key 对应的 result,其中 key 为_make_key
函数根据参数结算出来的字符串,result 为被修饰的函数在给定的参数下返回的结果。注意,root 是不保存数据 key 和 result 的。cache
是真正保存缓存数据的地方,类型为 dict。cache
中的 key 也是_make_key
函数根据参数结算出来的字符串,value 保存的是 key 对应的双向循环链表中的节点。
接下来根据 maxsize
不同,定义不同的 wrapper
。
maxsize == 0
,其实也就是没有缓存,那么每次函数调用都不会命中,并且没有命中的次数misses
加 1。maxsize is None
,不限制缓存大小,如果函数调用不命中,将没有命中次数misses
加 1,否则将命中次数hits
加 1。限制缓存的大小,那么需要根据 LRU 算法来更新
cache
,也就是 42~97 行的代码。如果缓存命中 key,那么将命中节点移到双向循环链表的结尾,并且返回结果(47~58 行)
如果没有命中,并且缓存满了,那么需要将最久没有使用的节点(root 的下一个节点)删除,并且将新的节点添加到链表结尾。在实现中有一个优化,直接将当前的 root 的 key 和 result 替换成新的值,将 root 的下一个节点置为新的 root,这样得到的双向循环链表结构跟删除 root 的下一个节点并且将新节点加到链表结尾是一样的,但是避免了删除和添加节点的操作(68~88 行)
如果没有命中,并且缓存没满,那么直接将新节点添加到双向循环链表的结尾(
root[PREV]
,这里我认为是结尾,但是代码注释中写的是开头)(89~96 行)
最后给 wrapper
添加两个属性函数 cache_info
和 cache_clear
,cache_info
显示当前缓存的命中情况的统计数据,cache_clear
用于清空缓存。对于上面阶乘相关的代码,如果在最后执行 factorial.cache_info()
,会输出
第一次执行 factorial(5)
的时候都没命中,所以 misses = 5,第二次执行 factorial(3)
的时候,缓存命中,所以 hits = 1。
最后需要说明的是,对于有多个关键字参数的函数,如果两次调用函数关键字参数传入的顺序不同,会被认为是不同的调用,不会命中缓存。另外,被 lru_cache 装饰的函数不能包含可变类型参数如 list,因为它们不支持 hash。
总结一下,这篇文章首先简介了一下缓存的概念,然后展示了在 Python 中 lru_cache
的使用方法,最后通过源码分析了 Python 中 lru_cache
的实现细节。
版权声明: 本文为 InfoQ 作者【zikcheng】的原创文章。
原文链接:【http://xie.infoq.cn/article/48b884d6258aa6607370dc5ca】。文章转载请联系作者。
评论