如何用记忆化缓存JavaScript函数结果来加速你的代码

推酷

函数是编程的基本组成,它能让我们的代码 模块化, 可重用性更好。

通常我们会使用函数把程序分块,之后可以调用函数完成一些有用的操作。

有的时候,函数调用很多次的代价是很昂贵的(比如计算一个数的 阶乘的函数)。但是我们可以通过 缓存优化这样的函数让它们执行快很多。

例如,比方说我们有返回一个数的阶乘的函数。

function factorial(n) {
    
    return factorial
}

很好,让我们执行 factorial(50)。计算机会执行计算并返回最后的结果,棒极了。

完成这个之后,让我们执行 factorial(51)。计算机又一次执行了一些计算并给我们返回了结果,但是你可能注意到我们已经重复了一些本来可以避免的步骤。一个优化的方法可以是这样:

factorial(51) = factorial(50) * 51

但是我们的 function每次调用的时候仍然执行了计算:

factorial(51) = 51 * 50 * 49 * ... * 2 * 1

如果我们的 factorial函数能从之前的计算里记住那些值,然后用它们来加速执行是不是很酷呢? 于是 记忆化呼之欲出,这是一种能让我们的 function记住(缓存)结果的方法。现在你应该对我们想实现的有一个基础的理解,这是标准定义:

记忆化 是一种优化技巧,主要通过存储代价高的函数调用的结果,当需要执行同样的计算时直接返回已经缓存的结果,来加速计算机程序运行。

Memoizing简单来说就是在内存里 记住或者存储。记忆化的函数通常很快,因为函数已经有之前计算的结果,之后调用并不会执行之前的计算,我们可以直接从缓存里得到结果。

这是一个简单的记忆化函数,大概长这样(如果你想修改,这是 CodePen地址)

// 一个简单的加法函数
const add = (n) => (n + 10);
add(9);
const memoizedAdd = () => {
  let cache = {};
  return (n) => {
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result');
      let result = n + 10;
      cache[n] = result;
      return result;
    }
  }
}
const newAdd = memoizedAdd();
console.log(newAdd(9)); 
console.log(newAdd(9)); 

记忆化的要点

以上的代码有几个要点:

实现你自己的记忆化函数

之前的代码运行很好,但是如果我们想要把任意一个函数转换成记忆化的函数呢?

这是如何去实现你自己的记忆化函数( codepen):

const add = (n) => (n + 10);
console.log('Simple call', add(3));
const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];  
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result');
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  }
}
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3));  
console.log(memoizedAdd(3));  
console.log(memoizedAdd(4));  
console.log(memoizedAdd(4));  

现在非常棒!这个简单的 memoize函数会把任意一个函数包装成等价的记忆化函数。这段代码对简单的函数很有效,也可以根据你的需要调整成处理任意数量的 arguments。

记忆化递归函数

如果你给 memoize函数或者Lodash的 _.memoize传入递归函数,结果并不会和你预期一样,因为递归函数会在之后的调用里最终变成调用自己而不是调用记忆化函数,因此 cache会失效。 只要保证你的递归函数是调用记忆化的函数就可以了。这是如何调整教科书式的 阶乘函数的实例( codepen):

const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];
    if (n in cache) {
      console.log('Fetching from cache', n);
      return cache[n];
    }
    else {
      console.log('Calculating result', n);
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  }
}
const factorial = memoize(
  (x) => {
    if (x === 0) {
      return 1;
    }
    else {
      return x * factorial(x - 1);
    }
  }
);
console.log(factorial(5)); 
console.log(factorial(6)); 

这段代码要注意的几点:

  • 阶乘函数是递归调用了自己的记忆化的版本。
  • 记忆化的函数是缓存了之前的阶乘结果,这能显著提升计算速度,因为这些结果能重用,比如 factorial(6) = 6 * factorial(5)。

记忆化和缓存是一回事吗?

是的,有点像。记忆化实际上是一种特殊的缓存。一般来说缓存是指任意为了以后能重用的存储技巧(像 HTTP缓存),记忆化特指缓存函数的返回值。

什么时候让函数记忆化

尽管看上去记忆化可以用在所有的函数上,实际上是有一些限制的:

  • 为了让函数记忆化,函数必须是纯的,这样返回值对同样的输入每次都是同样的。
  • 记忆化是内存空间增长与执行速度增加的一种权衡,因此仅对于输入范围有限于是缓存的值可以更频繁使用的函数更加有效。
  • 看上去你应该记忆你的API调用,然而这并没有必要,因为浏览器已经为你自动缓存了。查看 HTTP缓存的更多细节。
  • 我发现的最好的记忆化函数的实例是 计算量很大的函数,对性能提升很大(阶乘、斐波那契函数并不是好的实例)。
  • 如果你对React/Redux有兴趣可以查看 reselect,这是使用记忆化的选择器来保证只在状态树相关的部分有变化时才去计算。

延伸阅读

如果你想详细了解这篇文章的一些话题,以下链接会很有用:

我希望这篇文章会对你有用,你已经对JavaScript的记忆化有了更好的理解。 别忘了点赞,如果你想让我写点别的东西,请告诉我。

本文由 黑白世界4648 第一时间收藏到GET,原文来自 → www.tuicool.com

「GetParty」

关注微信号,推送好文章

微信中长按图片即可关注

更多精选文章

评论
微博一键登入