Python实现记忆化是否有等价Java对象的缓存存储结构？

Python 原生的dict（字典类型）就是你需要的键值对存储结构，和Java对象的键值存储逻辑完全一致，只会保存实际计算过的索引和对应结果，不会出现列表预分配带来的大量空占位问题，存储效率更高。

你最初编写的代码存在三个明显问题：

• 默认参数里引用了未定义的fibn变量，运行时会直接抛出名称错误
• 预分配列表的逻辑本身不成立：调用函数前你无法提前获知输入的n大小，根本没法确定要初始化多长的列表
• 递归调用子函数时没有把memo参数传进去，就算列表初始化正确，递归层也拿不到已经存储的缓存值

手动字典缓存实现 #

直接用空字典作为缓存载体即可，注意要规避Python可变默认参数的初始化陷阱，首次调用时再生成空字典：

def fib(n, memo=None):
    # 首次调用初始化缓存字典
    if memo is None:
        memo = {}
    # 基准情况直接返回
    if n <= 2:
        return 1
    # 命中缓存直接返回存储值
    if n in memo:
        return memo[n]
    # 递归计算结果存入缓存
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

这个实现运行时的memo结构和你预期的完全一致，比如调用fib(7)时，缓存字典的内容为{3:2, 4:3, 5:5, 6:8, 7:13}，没有任何冗余空值。

更简便的内置方案 #

Python标准库已经提供了现成的记忆化装饰器functools.lru_cache，不需要手动维护缓存字典，底层自动用键值对结构存储计算结果，代码更简洁：

from functools import lru_cache

# maxsize=None表示不限制缓存大小
@lru_cache(maxsize=None)
def fib(n):
    if n <= 2:
        return 1
    return fib(n-1) + fib(n-2)

内容的提问来源于stack exchange，提问作者Snopix