记忆化(Memoization)

记忆化(Memoization)是一种以空间换时间的优化技术,指把函数的计算结果按输入参数缓存起来,当同样的输入再次出现时,直接返回已缓存的结果而不重新计算。

概述

记忆化的前提通常是被优化的函数为纯函数,即相同输入总是产生相同输出且没有副作用。这样才能保证缓存的结果始终有效。它与通用意义上的缓存类似,但特指在函数调用层面自动保存与复用返回值。

核心原理

记忆化的实现一般会为函数包裹一层缓存结构:

• 用一个映射表(如哈希表)以输入参数为键、以计算结果为值进行存储。
• 每次调用先查表,命中则直接返回缓存;未命中才执行真实计算,并把结果写回缓存。
• 对于多参数函数,需要把参数序列化为唯一的缓存键。

经典案例是斐波那契数列的递归计算。朴素递归会导致指数级的重复调用,而加入记忆化后,每个子问题只计算一次,时间复杂度降为线性。这也正是自顶向下动态规划的基本思路。

应用场景

记忆化广泛用于递归算法优化、动态规划、前端框架中的计算属性缓存,以及函数式编程中对纯函数结果的复用。许多语言和框架提供了现成的记忆化工具,如 Python 的装饰器、React 中的相关钩子等。

常见问题

问:记忆化和缓存有什么区别?答:记忆化是缓存的一个子集,专指在函数调用层面缓存返回值;而缓存是更宽泛的概念,可用于数据库、页面、网络等各个层面。

问:记忆化会带来什么风险?答:缓存会持续占用内存,若输入种类繁多可能造成内存膨胀,因此常需配合容量上限或淘汰策略;此外它不适用于有副作用或结果会随时间变化的函数。