基于动态规划的内存缓存：Memoization表性能优势存疑

一、Memoization表怎么在CPU访问RAM时实现性能提升？ #

核心逻辑是用RAM的访问成本替换更高昂的计算成本——尽管RAM速度远慢于CPU，但很多场景下，重复计算的耗时比几次RAM读写要大得多：

• 对于复杂计算（比如递归求解斐波那契数列、大整数因式分解、高维矩阵运算），单次计算可能需要几十到上百个CPU周期，甚至更多；而现代RAM的随机访问延迟大概是几十纳秒（对应几百个CPU周期），但如果某个值需要重复计算十几次甚至上千次，把结果存在Memo表（RAM中），每次直接读取的总耗时，远低于反复执行计算的总耗时。
• 另外，Memoization通常会配合CPU的缓存机制（L1/L2/L3缓存）工作：当你多次读取Memo表中的同一个值时，这个值会被CPU缓存到更靠近核心的层级，后续的访问速度会接近CPU寄存器的速度，进一步缩小RAM访问的开销影响。

举个实际例子：计算斐波那契(100)的递归实现，不做Memo的话会重复计算斐波那契(50)上百万次；而用Memo表存一次结果后，后续只需要读取一次，哪怕第一次读RAM要几十纳秒，也比上百万次加法运算快几个数量级。

二、为什么没法让CPU始终在本地完成重复计算？ #

CPU的本地存储（寄存器、各级缓存）有天生的容量限制，这是核心原因：

• 寄存器数量极少（通常只有几十个），只能存放当前正在处理的少量变量；L1缓存一般只有几十KB，L2缓存几MB，L3缓存也才几十MB——如果你的计算需要缓存的结果数量超过这个规模（比如动态规划问题中需要存储上百万个状态值），CPU本地根本装不下，只能放到RAM里。
• 就算是小规模的计算，CPU的上下文切换、线程调度也会清空或替换寄存器/缓存中的内容：当CPU切换到其他任务后，之前存的计算结果可能被挤出缓存，下次再需要时还是得从RAM重新读取，这时候Memo表的持久化存储（RAM中）反而更可靠。
• 还有些计算的依赖链很长，CPU无法同时把所有需要的变量都放在本地存储中，必须从RAM加载中间值，这时候Memo化存储这些中间值，至少能避免重复计算它们。

简单说：CPU本地存储是“高速但极小”的，RAM是“低速但极大”的，Memoization是在两者之间做了平衡——用可接受的RAM访问成本，避免了远更昂贵的重复计算。

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