什么是函数缓存
为了讲明白这个概念, 假设你在开发一个天气 App. 开始你不知道怎么做, 正好有一个 NPM 包里有一个 getChanceOfRain 的方法可以调用:
- import { getChangeOfRain } from 'magic-weather-calculator';
- function showWeatherReport() {
- let result = getChangeOfRain(); // 这里调用
- console.log('The change of rain tomorrow is:', result);
- }
只是这样会遇到一个问题. 无论你做什么, 只要调用这个方法就会消耗 100 毫秒. 所以, 如果某个用户疯狂点击 "显示天气" 按钮, 每次点击 App 都会有一段时间没有响应.
- showWeatherReport(); // 触发计算
- showWeatherReport(); // 触发计算
- showWeatherReport(); // 触发计算
这很不理性. 在实际开发中, 如果你已经知道结果了, 那么你不会一次一次的计算结果. 重用上次的结果才是上佳选择. 这就是函数缓存. 函数缓存也就是缓存函数的结算结果, 这样就不需要一次一次的调用函数.
在下面的例子里, 我们会调用 memoizedGetChangeOfRain(). 在这个方法里我们会检查一下是否已经有结果了, 而不会每次都调用 getChangeOfRain()方法:
- import { getChangeOfRain } from 'magic-weather-calculator';
- let isCalculated = false;
- let lastResult;
- // 添加这个方法
- function momoizedGetChangeOfRain() {
- if (isCalculated) {
- // 不需要在计算一次
- return lastResult;
- }
- // 第一次运行时计算
- let result = getChangeOfRain();
- lastResult = result;
- isCalculated = true;
- return result;
- }
- function showWeatherReport() {
- let result = momoizedGetChangeOfRain();
- console.log('The chance of rain tomottow is:', result);
- }
多次调用 showWeatherReport()只会在第一次做计算, 其他都是返回第一次计算的结果.
- showWeatherReport(); // (!) 计算
- showWeatherReport(); // 直接返回结果
- showWeatherReport(); // Uses the calculated result
- showWeatherReport(); // Uses the calculated result
这就是函数缓存. 当我们说一个函数被缓存了, 不是说在 JavaScript 语言上做了什么. 而是当我们知道结果不变的情况下避免不必要的调用.
函数缓存和参数
一般的函数缓存模式:
检查是否存在一个结果
如果是, 则返回这个结果
如果没有, 计算结果并保存在以后返回
然而, 实际开发中需要考虑某些情况. 比如: getChangeOfRain()方法接收一个城市参数:
- function showWeatherReport(city) {
- let result = getChanceOfRain(city); // Pass the city
- console.log("The chance of rain tomorrow is:", result);
- }
如果只是简单的像之前一样缓存这个函数, 就会产生一个 bug:
- showWeatherReport('Tokyo'); // (!) Triggers the calculation
- showWeatherReport('London'); // Uses the calculated answer
发现了么? 东京和伦敦的天气是很不一样的, 所以我们不能直接使用之前的计算结果. 也就是说我们使用函数缓存的时候必须要考虑参数.
方法 1: 保存上一次的结果
最简单的方法就是缓存结果和这个结果依赖的参数. 也就是这样:
- import { getChanceOfRain } from 'magic-weather-calculator';
- let lastCity;
- let lastResult;
- function memoizedGetChanceOfRain(city) {
- if (city === lastCity) { // 检查城市!
- // 城市相同返回上次的结果
- return lastResult;
- }
- // 第一次计算, 或者参数变了则执行计算
- let result = getChanceOfRain(city);
- // 保留参数和结果.
- lastCity = city;
- lastResult = result;
- return result;
- }
- function showWeatherReport(city) {
- // 参数传递给缓存的参数
- let result = memoizedGetChanceOfRain(city);
- console.log("The chance of rain tomorrow is:", result);
- }
注意这个例子和第一个例子的些许不同. 不再是直接返回上次的计算结果, 而是比较 city === lastCity. 如果中途城市发生了变化就要重新计算结果.
- showWeatherReport('Tokyo'); // (!) 计算
- showWeatherReport('Tokyo'); // 使用缓存结果
- showWeatherReport('Tokyo'); // 使用缓存结果
- showWeatherReport('London'); // (!) 重新计算
- showWeatherReport('London'); // 使用缓存结果
这样虽然修改了第一个例子的 bug, 但是也不总是最好的解决办法. 如果每次调用参数都不一样, 上面的解决方法就没什么用处了.
- showWeatherReport('Tokyo'); // (!) 执行计算
- showWeatherReport('London'); // (!) 执行计算
- showWeatherReport('Tokyo'); // (!) 执行计算
- showWeatherReport('London'); // (!) 执行计算
- showWeatherReport('Tokyo'); // (!) 执行计算
无论何时使用函数缓存都要检查下是不是真的有帮助!
方法 2: 保留多个结果
另一件我们可以做的就是保留多个结果. 虽然我们可以为每个参数都定义一个变量, 比如: lastTokyoResult, lastLondonResult 等. 使用 Map 看起来是一个更好的方法.
- let resultsPerCity = new Map();
- function memoizedGetChangeOfRain(city) {
- if (resultsPerCity.has(city)) {
- // 返回已经存在的结果
- return resultsPerCity.get(city);
- }
- // 第一次获取城市数据
- let result = getChangeOfRain(city);
- // 保留整个城市的数据
- resultsPerCity.set(city, result);
- return result;
- }
- function showWeatherReport(city) {
- let result = memoizedGetChangeOfRain(city);
- console.log('The chance of rain tomorrow is:', result);
- }
整个方法和适合我们的用例. 因为它只会在第一次获取城市数据的时候计算. 使用相同的城市获取数据的时候都会返回已经保存在 Map 里的数据.
- showWeatherReport('Tokyo'); // (!) 执行计算
- showWeatherReport('London'); // (!) 执行计算
- showWeatherReport('Tokyo'); // 使用缓存结果
- showWeatherReport('London'); // 使用缓存结果
- showWeatherReport('Tokyo'); // 使用缓存结果
- showWeatherReport('Paris'); // (!) 执行计算
然而这样的方法也不是没有缺点. 尤其在我们城市参数不断增加的情况下, 我们保存在 Map 里的数据会不断增加.
所以, 这个方法在获得性能提升的同时在无节制的消耗内存. 在最坏的情况下会造成浏览器 tab 的崩溃.
其他方法
在 "只保存上一个结果" 和 "保存全部结果" 之间还有很多其他的办法. 比如, 保存最近使用的最后 N 个结果, 也就是我么熟知的 LRU, 或者 "最近最少使用" 缓存. 这些都是在 Map 之外添加其他逻辑的方法. 你也可以删除某些时间之后删掉过去的数据, 就如同浏览器在缓存过期之后会把他们删掉一样. 如果参数是一个对象(不是上例所示的字符串), 我们可以使用 WeakMap 来代替 Map. 现代一点的浏览器都支持. 使用 WeakMap 的好处是在作为 key 的对象不存在的时候会把键值对都删除. 函数缓存是一个非常灵活的技术, 你可以根据具体情况使用不同的策略.
函数缓存和函数纯度
我们知道函数缓存不总是安全的.
假设 getChangeOfRain()方法不接受一个城市作为参数, 而是直接接收用户输入:
- function getChangeOfRain() {
- // 显示输入框
- let city = prompt('Where do you live?');
- // 其他代码
- }
- // 我们的代码
- function showWeatherReport() {
- let result = getChangeOfRain();
- console.log('The chance of rain tomorrow is:', result);
- }
每次调用 showWeatherReport()方法都会出现一个输入框. 我们可以输入不同的城市, 在 console 里看到不同的结果. 但是如果缓存了 getChanceOfRain()方法, 我们只会看到一个输入框! 没法输入一个不同的城市.
所以函数缓存只有在那个函数是纯函数的情况下才是安全的. 也就是说: 只读取参数, 不和外界交互. 一个纯函数, 调用一次或者使用之前的缓存结果都是无所谓的.
这也是为什么在一个复杂的算法里, 把仅仅计算的代码和做什么的代码分离的原因. 纯计算的方法可以安全的缓存来避免多次调用. 而那些做什么的方法没法做相同的处理.
- // 如果这个方法值做计算的话, 那么可以被称为纯函数
- // 对它使用函数缓存是安全的.
- function getChanceOfRain(city) {
- // ... 计算代码...
- }
- // 这个方法要显示输入框给用户, 所以不是纯函数
- function showWeatherReport() {
- // 这里显示输入框
- let city = prompt('Where do you live?');
- let result = getChanceOfRain(city);
- console.log("The chance of rain tomorrow is:", result);
- }
现在可以安全的对 getChanceOfRain()做函数缓存.-- 因为它接受 city 作为参数, 而不是弹出一个输入框. 换句话说, 它是纯函数.
每次调用 showWeatherReport()还是会看到输入框. 但是得到结果之后对应的计算是可以避免的.
- let isCalculated = false;
- let lastResult;
- function memoizedGetChanceOfRain() {
- if (isCalculated) {
- return lastResult;
- }
- let result = getChanceOfRain();
- lastResult = result;
- isCalculated = true;
- return result;
- }
- function memoize() {
- let isCalculated = false;
- let lastResult;
- function memoizedGetChanceOfRain() {
- if (isCalculated) {
- return lastResult;
- }
- let result = getChanceOfRain();
- lastResult = result;
- isCalculated = true;
- return result;
- }
- }
- function memoize(fn) { // 声明 fn 参数
- let isCalculated = false;
- let lastResult;
- function memoizedGetChanceOfRain() {
- if (isCalculated) {
- return lastResult;
- }
- let result = fn(); // 调用传入的方法参数
- lastResult = result;
- isCalculated = true;
- return result;
- }
- }
- function memoize(fn) {
- let isCalculated = false;
- let lastResult;
- return function memoizedFn() {
- if (isCalculated) {
- return lastResult;
- }
- let result = fn();
- lastResult = result;
- isCalculated = true;
- return result;
- }
- }
- import { getChanceOfRain } from 'magic-weather-calculator';
- let memoizedGetChanceOfRain = memoize(getChanceOfRain);
- function showWeatherReport() {
- let result = memoizedGetChanceOfRain();
- console.log('The chance of rain tomorrow is:', result);
- }
- import {
- getChanceOfRain, getNextEarthquake, getCosmicRaysProbability
- } from 'magic-weather-calculator';
- let momoizedGetChanceOfRain = memoize(getChanceOfRain);
- let memoizedGetNextEarthquake = memoize(getNextEarthquake);
- let memoizedGetCosmicRaysProbability = memoize(getCosmicRaysProbability);
- import { getChanceOfRain } from 'magic-weather-calculator';
- function showWeatherReport() {
- let result = getChanceOfRain();
- console.log('The chance of rain tomorrow is:', result);
- }
- import { getChanceOfRain } from 'magic-weather-calculator';
- let isCalculated = false;
- let lastResult;
- function memoizedGetChanceOfRain() {
- if (isCalculated) {
- return lastResult;
- }
- let result = getChanceOfRain();
- lastResult = result;
- isCalculated = true;
- return result;
- }
- function showWeatherReport() {
- let result = memoizedGetChanceOfRain();
- console.log("The chance of rain tomorrow is:", result);
- }
来源: https://segmentfault.com/a/1190000040169934