做的事：给朴素递归fib加一个装饰器
不改函数体一个字，只加@lru_cache。
代码from functools import lru_cache @lru_cache(maxsize=128) def fib_cached(n): if n < 2: return n return fib_cached(n-1) + fib_cached(n-2) def fib_plain(n): if n < 2: return n return fib_plain(n-1) + fib_plain(n-2)
验证：加了缓存之后，调用次数从269万次砍到31次
同样算fib(30)，两个函数体逻辑完全一样。
结果fib_cached(30) = 832040, 调用次数: 31, cache_info: CacheInfo(hits=28, misses=31, maxsize=128, currsize=31) fib_plain(30) 调用次数: 2692537
差了86856倍——朴素递归每算fib(n)都要重新展开fib(n-1)和fib(n-2)整棵子树，指数级增长；加了@lru_cache之后，fib_cached(28)这类已经算过的中间结果被缓存住了，第二次需要它时（比如算fib(29)=fib(28)+fib(27)时的fib(28)），直接从缓存里取，不会再往下展开子树——这正是把指数级递归压成线性递归的经典手段（memoization），misses=31恰好对应fib(0)到fib(30)这31个不重复的n值，每个只被计算了一次。
验证：缓存命中后，单次调用只要约52纳秒
跟朴素递归fib_plain(28)要29毫秒对比一下。
结果1000次缓存命中fib_cached(28)总耗时: 5.17e-05秒 → 单次约51.7纳秒 cache_clear()后第一次fib_cached(28)(冷缓存但仍是记忆化递归): 9.42e-06秒, 调用29次 fib_plain(28)完全不用缓存: 0.0292秒 加速比(naive/冷缓存首次): 约3102倍
这里拆出了三种不同的耗时：缓存命中（51.7纳秒，本质是一次字典查找）、缓存刚清空后的首次计算（9.42微秒，虽然缓存是空的，但递归本身依然是记忆化的，只需要29次调用而不是2^28次）、完全不用缓存的朴素递归（29.2毫秒，货真价实的指数级展开）。结论是：
lru_cache带来的核心收益不是"缓存命中快"（这只是锦上添花），而是它把递归的调用模式本身从指数级改造成了线性级——哪怕缓存是空的，只要函数体本身写成了"用已缓存的自身结果拼出下一个结果"这种递归形式，第一次计算也是线性时间，这跟命中率高不高是两件独立的事。
分步演示：缓存省下的不只是命中那一下
每一步都是本文上面用functools.lru_cache跑出来的原始结果。
lru_cache把指数级递归压成了线性
这一步新验证的场景
本文用到的工具
- 本机 Python 3.14.7
functools.lru_cache/cache_info()/cache_clear()：对比缓存命中、冷缓存首次调用和无缓存三种耗时
下一篇 · PYTHON 30
weakref：弱引用为什么不会阻止对象被回收
京公网安备11010502063487号