JavaScript Memoization缓存技术

Memoization是一种用来优化计算程序使之更快的技术,通过储存调用函数的结果并在传进同样参数的时候直接返回其返回值来实现。

而通常,我们只在递归函数中才需要反复调用一个已经执行过的函数的返回值。所以这里以一个最基本的计算阶乘的递归函数为例,如下所示

let times = 0;

function factorial(n) {
  if (n === 0 || n === 1) return 1;
  if (n === 2) return 2;

  console.log(`calculating ${++times} times`)

  return n * factorial(n - 1);
}

factorial(10)
factorial(10)
factorial(10)
factorial(10)

我们执行了四次factorial()函数,并且都是传递了同一参数,但是计算机照样还是会从头执行一遍,这样就造成了资源浪费。

所以我们可以想到,如果我们可以把每次计算的结果缓存到内存里,如果参数没有改变,那就直接返回这个缓存的结果就好了。这是一种以空间换时间的优化方式。

接着再看一个简单的例子

const double = n => n * 2;

const memoize = (fn) => {
  const cache = {}; // 创建一个缓存对象

  return (n) => {
    if (n in cache) {
      console.log('在缓存中');
      return cache[n];
    }

    console.log('从头运算');
    const result = fn(n);

    cache[n] = result; // 将其存储在缓存中

    return result;
  }
}

const memoizedDouble = memoize(double);

memoizedDouble(4) // 从头运算
memoizedDouble(4) // 在缓存中
memoizedDouble(5) // 从头运算
memoizedDouble(5) // 在缓存中
memoizedDouble(4) // 在缓存中

这也是所谓JavaScript闭包的典型运用,上面的memoize()函数实际上是实现了一个 size 无限大的缓存,只要不同的参数,运算过一次以后,都会存入缓存中。

但是我们传入一个递归函数进去是无法实现目的的,这个时候应该确保递归时,也应调用这个记忆后的函数。

// same memoize function
const memoize = (fn) => {
  const cache = {}; // 创建一个缓存对象

  return (n) => {
    if (n in cache) {
      console.log('在缓存中');
      return cache[n];
    }

    console.log('从头运算');
    const result = fn(n);

    cache[n] = result; // 将其存储在缓存中

    return result;
  }
}

const factorial = memoize(
  (n) => {
    if (n === 0) return 1;
    return n * factorial(n - 1);
  }
)

factorial(10) // 从头运算
factorial(10) // 在缓存中

可以发现实际上缓存中实际上保存从 1 到 10 所有的阶乘结果。

缓存这种存储某些数据以给将来的使用这一概念,实际上运用的方向非常多,比如HTTP缓存,而Memoization基本上就是这种特定的,缓存函数返回值的技术。

在哪些地方运用

通常我们并不会在所有的地方都使用这种空间换时间的优化技术,一般来说有下面几个规律:

  • 函数首先必须是一个 pure function,每次对于相同的输入,都应该有相同的返回。

  • 因为是为了以空间交换时间,因此函数必须有着有限的输入范围,来让缓存的值可以呗被频繁的多次使用。

  • 最合适的使用时机,应该是针对需要大量计算的 heavy computational function, 可以极大的提高性能。

如果对React相关生态的比较熟悉的话,就知道有一个 Reselect 的工具库,来帮助优化从state树提取数据映射到相关组件这一过程。它的源码也非常短小精悍,值得一读。

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注