记忆化缓存怎么设计?为什么给递归函数包一层不一定加速递归?
先理解原理和示例,再练习完整口述与追问。
回答要点
缓存所有参数及必要的 this;对象按身份或显式业务键;区分缺失与缓存 undefined;有失效和容量策略;递归需要经过缓存入口。
原理拆解
memoize 保存函数输入与输出的对应关系,相同输入再次调用时直接返回缓存结果。它适合纯计算或具有明确失效策略的数据读取。只用第一个参数作键会让多参数调用互相覆盖;用参数拼接字符串会产生碰撞;JSON.stringify 对函数、Symbol、undefined、循环引用和对象键顺序都有边界,也不等于通用参数相等判断。
可以用多层 Map,按 this 和每个参数逐层索引,对象使用引用身份,原始值使用 Map 的键规则。如果计算区分 +0 和 -0,还应专门编码,因为 Map 默认把这两者看成相同。缓存节点需要单独的命中标记,不能用结果是否 undefined 判断命中。长期使用必须考虑 LRU、TTL、主动清理、对象被缓存强引用、错误是否缓存,以及返回可变对象会不会被调用方修改。
const fastFib = memoize(fib) 只包住外层,而 fib 内部仍调用原来的 fib 时,递归子问题不会经过 fastFib,只会缓存顶层输入。应让递归通过记忆化后的入口,例如先声明变量,再赋值为 memoize 包装的递归实现,并在函数内部调用这个变量。异步缓存还要额外决定是否复用进行中的 Promise、拒绝后是否删除与何时过期,不能套用同步缓存规则。
示例与推演
计算 f(a,b) 时缓存结构逐层使用 a、b,否则 f(1,2) 与 f(1,3) 会冲突。对于 f(object),两个内容相同但引用不同的对象在身份缓存中不是同一个键。若函数输出 undefined,仍应第二次命中;若抛错,可以按契约不缓存,避免一次暂时失败永久污染结果。
易错点
长期缓存要明确容量和失效,缓存返回的可变对象不能被任意修改。把原递归函数套壳,只缓存外层,不会改写内部递归入口。
参考回答可直接练习口述
memoize 保存函数输入与输出的对应关系,相同输入再次调用时直接返回缓存结果。它适合纯计算或具有明确失效策略的数据读取。只用第一个参数作键会让多参数调用互相覆盖;用参数拼接字符串会产生碰撞;JSON.stringify 对函数、Symbol、undefined、循环引用和对象键顺序都有边界,也不等于通用参数相等判断。