Python的`functools.lru_cache`用好了能省不少重复计算——递归函数加一行装饰器,跑起来快了一个数
写递归的人多少都遇到过重复计算的问题。拿最经典的斐波那契来说,一个朴素的递归实现,n稍微大一点就跑不动了。
先看这段代码。
def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2) print(fib(30)) 跑一下,几十秒才出结果。为什么慢,因为fib(28)被算了两遍,fib(27)被算了三遍,越往下重复得越离谱。这还只是n等于30,换成35基本就卡死了。
有人会说,那我就加个字典手动缓存呗。可以,代码大概长这样。
cache = {} def fib(n): if n in cache: return cache[n] if n < 2: result = n else: result = fib(n - 1) + fib(n - 2) cache[n] = result return result 能跑,也快了。问题在于每写一个需要缓存的函数,你就得把这一套搬一遍。 缓存逻辑和业务逻辑搅在一起,函数体被撑得很难看。 函数一多,这种重复的模板代码就开始到处散。
Python标准库早就给了答案, functools.lru_cache 。一行装饰器,把上面那段手动缓存全替掉。
from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2) print(fib(30)) 函数体回到了最干净的样子,缓存的事交给装饰器。fib(30)现在几乎是瞬间出结果,fib(100)也不在话下,虽然结果会溢出,那是整数精度的事,跟缓存无关。
maxsize参数值得说一句。传None表示不限制缓存大小,适合那种参数空间有限、结果稳定的函数。传一个具体数字,比如maxsize=128,它会用LRU策略淘汰最久没用的缓存项。 参数空间大的函数别乱传None,缓存会一直涨,内存迟早出事。
这东西不只对递归有用。任何纯函数,只要输入相同输出就相同,没有副作用,都可以挂上去。比如解析一段固定格式的配置文本,或者根据ID查一个不怎么变的基础数据。
from functools import lru_cache @lru_cache(maxsize=256) def parse_rule(rule_text): parts = rule_text.split(':') return {'field': parts[0], 'op': parts[1], 'value': parts[2]} 同一个规则文本反复解析,第一次算完就存住了,后面直接拿结果。调用方完全不用关心缓存这件事。
有个坑得提醒。被装饰的函数参数必须是可哈希的。传列表、字典进去会直接报错。遇到这种情况,把参数转成元组或者用frozenset,别硬传。
还有,缓存是挂在函数对象上的,进程内共享。多进程环境下每个进程各有一份,别指望跨进程共享缓存。想清缓存用fib.cache_clear(),想看命中情况用fib.cache_info(),调试的时候挺方便。
print(fib.cache_info()) CacheInfo(hits=28, misses=31, maxsize=None, currsize=31) hits是命中次数,misses是没命中、真算了一次的次数。看到hits远大于misses,说明这个缓存加对了。
很多人写递归、写重复调用的工具函数,第一反应是手动搞个字典。真没必要。 标准库摆在那,一行装饰器的事,代码干净,性能还稳。 下次再碰到纯函数反复算同一个输入,先想想lru_cache,别急着写缓存字典。