函数记忆

记忆化（英语：memoization）是一种提高计算机程序执行速度的优化技术。通过储存大计算量函数的返回值，当这个结果再次被需要时将其从缓存提取，而不用再次计算来节省计算时间。

记忆化是一种典型的在计算时间与电脑存储器空间之中获取平衡的方案。

来源：维基百科

从上面的定义可以看出缓存是一种非常有用的技巧，它可以把一些函数结果储存起来在下次调用的时候返回。这里不讨论什么样场景使用缓存而是抛砖引玉如何编写一个可复用的 Memoization 函数

MemoizationSync

MemoizationSync 从字面就可以看出它是一个同步版本的 Memoization，下面的以 add 函数为例介绍如何编写一个通用的 memoization 来对结果进行缓存

const memo = {};

const add = (...args) => {
  const key = args.join();
  if (Object.prototype.hasOwnProperty.call(memo, key)) {
    return memo[key];
  }
  const result = args.reduce((a, b) => a + b, 0);
  memo[key] = result;
  return result;
};

add(1, 2, 3);
add(1, 2, 3);

如果要给 add 函数显示的添加一个缓存功能可能会按照上面的情况来编写，但是它存在问题。

这个函数同时做了两件事情

计算 args
读取 memo 的缓存但是这样显示违背了设计模式的单一原则，而且会给后续的维护带来麻烦，以及如果我们需要新的函数缓存是不是还要重新复制一份过去，显然不符合我们的要求，我们尝试将它进行一次抽离

const add = (...args) => {
  return args.reduce((a, b) => a + b, 0);
};

const memoizationSync = (fn, key) => {
  const memo = {};
  return function callback(...args) {
    if (memo.hasOwnProperty(key)) {
      return memo[key];
    }
    const result = fn.apply(this, args);
    memo[key] = result;
    return result;
  };
};

const argumentsArr = [1, 2, 3];
const memoizationAdd = memoizationSync(add, argumentsArr);
memoizationAdd(...argumentsArr);
memoizationAdd(...argumentsArr);

这样就得到了一个通用的 memoizationSync 函数，它接受一个 key ，通过 key 来进行区分缓存。

不过为了它的灵活性和符合更多的场景的要求我们还是需要对它进行一次改造，来改造前我们看下这个函数做了啥

根据 key 来读取缓存
无缓存来执行函数设置缓存显然这两步是不会改变的，但是我们可以对 key 下手提高 key 的唯一性，我们希望它可以是一个函数并且存在默认值，这样在复杂场景下可以由用户根据参数来指定缓存什么字段

const memoizationSync = (fn, getKey = (...args) => args.join('')) => {
  const memo = {};
  return function callback(...args) {
    const key = typeof getKey === 'function' ? getKey.apply(this, args) : getKey;
    if (memo.hasOwnProperty(key)) {
      return memo[key];
    }
    const result = fn.apply(this, args);
    memo[key] = result;
    return result;
  };
};

MemoizationAsync

在 JavaScript 中异步场景粗略可以分为两部分

回调函数
Promise（async 、Generator 都是基于 Promise）

下面就来讨论这两部分我们如何实现缓存

Callback

我现在有一个 getImgSize 的函数，它会根据 img 的 src 来返回图片的真实宽度和高度，如果成功就会调用 callback 来传递参数（node 回调风格），但是我希望如果 url 相同的时候就直接返回而不是继续调用一次 getImgSize

const getImgSize = (src, callback) => {
  const img = new Image();
  img.src = src;
  img.addEventListener('load', () => {
    callback(null, {
      width: img.naturalWidth,
      height: img.naturalHeight,
    });
  });

  img.addEventListener('error', (e) => {
    callback(new Error(e), null);
  });
};

const url = 'https://www.google.com/images/branding/googlelogo/1x/googlelogo_color_272x92dp.png';

getImgSize(url, (error, size) => {
  if (error) {
    return;
  }
  console.log(size);
});

在编写 memoizationAsync 函数之前我们先想一下以什么样的方式来编写这个函数，按照惯例我们希望不要对用户的使用方式有太多影响，所以期待的调用方式如下

const getImgSizeMemoization = memoizationAsync(getImgSize);
getImgSizeMemoization(url, (error, size) => {
  if (error) {
    return;
  }
  console.log(size);
});
// 相同参数使用缓存
getImgSizeMemoization(url, (error, size) => {
  if (error) {
    return;
  }
  console.log(size);
});

后面就是来编写这个函数

const memoizationAsync = (fn, getKey = (...args) => args.join()) => {
  const memo = {};
  const queue = {};
  return function (...rest) {
    const callback = Array.prototype.pop.call(rest);
    const key = getKey.apply(this, rest);
    const cb = (...args) => {
      memo[key] = args;
      queue[key].forEach((item) => {
        item.apply(this, args);
      });
      delete queue[key];
    };
    if (memo.hasOwnProperty(key)) {
      return memo[key];
    }
    if (!queue.hasOwnProperty(key)) {
      queue[key] = [callback];
    } else {
      queue[key].push(callback);
      // 后续加入等待第一个执行结束
      return;
    }
    fn.apply(this, [...rest, cb]);
  };
};

说一下这个函数编写的思路，通过自定义创建 cb 回调函数来完成记录缓存和调用用户传递的回调，其他的读取和设置缓存与上面一致。

而存在 queue 变量的原因是因为异步任务添加进来的时候可能正在请求，但是 memo 还没有被写入结果，所以通过队列来管理这个请求，等待第一个请求结束之后批量来执行队列的任务，最后删除。

Promise

回忆一下Promise 函数的特性

对象的状态不受外界影响
一旦状态改变，就不会再变，任何时候都可以得到这个结果

重点是第二点，它不同于回调函数，只要结果出来了任何时候都可以调用，我们在 click 监听一个事件如果错过了这个监听想要回溯是不可能的，但是 promise 你重复无数次的.then 调用，基于这个特性我们来编写 MemoizationAsync

const getImgSize = (src) => {
  return new Promise((resolve, reject) => {
    const img = new Image();
    img.src = src;
    img.addEventListener('load', () => {
      return resolve({
        width: img.naturalWidth,
        height: img.naturalHeight,
      });
    });

    img.addEventListener('error', (e) => {
      return reject(e);
    });
  });
};

const url = 'https://www.google.com/images/branding/googlelogo/1x/googlelogo_color_272x92dp.png';

const memoizationAsync = (fn, getKey = (...args) => args.join()) => {
  const memo = {};
  return async function (...args) {
    const key = getKey.apply(this, args);
    if (memo.hasOwnProperty(key)) {
      return memo[key];
    }
    const result = fn.apply(this, args);
    memo[key] = result;
    return result;
  };
};

const getImgSizeMemoization = memoizationAsync(getImgSize);

(async () => {
  const result = await Promise.all([getImgSizeMemoization(url), getImgSizeMemoization(url)]);
  console.log(result);
})();

memoizationAsync 函数编写的十分精简跟同步版本基本没区别，不同点在于我们只是返回了 Promise 的状态，而得益于 Promise 的特性在任何时候这个函数都会返回正确的结果

最后

如果对你有帮助可以关注、 star 一下，有什么错误欢迎指出

yliu

MemoizationSync

MemoizationAsync

Callback

Promise

最后

分类查看

近期文章