知识卡片
内存缓存(memoization):用空间换重复计算的时间
对于纯函数(相同输入必定得到相同输出)且计算成本较高的场景,把已经算过的结果存进数组或 map,下次遇到相同输入直接查表返回,能把重复的子计算全部消除。书中以递归斐波那契数列为例,加了内存缓存后耗时从数秒降到毫秒级。发散:这是”空间换时间”最朴素直接的体现——递归逻辑本身没有变,只是在函数入口加了一层查表短路,说明很多性能优化不需要重写算法本身,只需要在薄弱环节插入一层缓存。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
原书出处
参考来源
- 位置:《Go入门指南》第6章《6.12 通过内存缓存来提升性能》(源文件:_epub-src/OEBPS/6.12 通过内存缓存来提升性能.md.html)
- 结论依据:原文在该章节围绕“对于纯函数(相同输入必定得到相同输出)且计算成本较高的场景,把已经算过的结果存进数组或map,下次遇到相同输入…”给出定义、示例或限制条件;摘录中的术语、代码片段或对比关系直接支撑本卡片的结论。
- 原始内容:组中索引为 n 的位置(详见第 7 章),然后在数组中查找是否已经计算过,如果没有找到,则再进行计算。 程序 Listing 6.17 - fibonacci_memoization.go 就是依照这个原则实现的,下面是计算到第 40 位数字的性能对比: 普通写法:4.730270 秒 内存缓存:0.001000 秒 内存缓存的优势显而易…