JavaScript中的Memoization

Memoization: 基本理念

如果我们有CPU密集型操作，我们可以通过将初始操作的结果存储在缓存中来优化使用。如果操作必然会再次执行，我们将不再麻烦再次使用我们的CPU，因为相同结果的结果存储在某个地方，我们只是简单地返回结果。

可以看下面的例子:

function longOp(arg) {
  if( cache has operation result for arg) {
    return the cache
  }
  else {
    假设执行一个耗时30分钟的操作
    把结果存在`cache`缓存里
  }
  return the result
}
longOp('lp') // 因为第一次执行这个参数的操作，所以需要耗时30分钟
// 接下来会把结果缓存起来
longOp('bp') // 同样的第一次执行bp参数的操作，也需要耗时30分钟
// 同样会把结果缓存起来
longOp('bp') // 第二次出现了
// 会很快的把结果从缓存里取出来
longOp('lp') //也同样出现过了
// 快速的取出结果

• 就CPU使用而言，上面的伪函数longOp是一种耗时的功能。上面的代码会把第一次的结果给缓存起来，后面具有相同输入的调用都会从缓存中提取结果，这样就会绕过时间和资源消耗。

下面看一个平方根的例子:

function sqrt(arg) {
  return Math.sqrt(arg);
}
log(sqrt(4)) // 2
log(sqrt(9)) // 3

现在我们可以使用memoize来处理这个函数:

function sqrt(arg) {
  if (!sqrt.cache) {
    sqrt.cache = {}
  }
  if (!sqrt.cache[arg]) {
    return sqrt.cache[arg] = Math.sqrt(arg)
  }
  return sqrt.cache[arg]
}

可以看到，结果会缓存在cache的属性里。

Memoization：履行

在上面部分，我们为函数添加了memoization。现在，我们可以创建一个独立的函数来记忆任何函数。我们将此函数称为memoize。

function memoize(fn) {
  return function () {
    var args = Array.prototype.slice.call(arguments)
    fn.cache = fn.cache || {};
    return fn.cache[args] ? fn.cache[args] : (fn.cache[args] = fn.apply(this,args))
  }
}

• 我们可以看到这段代码接收另外一个函数作为参数并返回。

要使用此函数，我们调用memoize将要缓存的函数作为参数传递。

memoizedFunction = memoize(funtionToMemoize)
memoizedFunction(args)

我们现在把上面的例子加入到这个里面：

function sqrt(arg) {
  return Math.sqrt(arg);
}
const memoizedSqrt = memoize(sqrt)

返回的函数memoizedSqrt现在是sqrt的memoized版本。

我们来调用下:

//...
memoizedSqrt(4) // 2 calculated(计算)
memoizedSqrt(4) // 2 cached
memoizedSqrt(9) // 3 calculated
memoizedSqrt(9) // 3 cached
memoizedSqrt(25) // 5 calculated
memoizedSqrt(25) // 5 cached

我们可以将memoize函数添加到Function原型中，以便我们的应用程序中定义的每个函数都继承memoize函数并可以调用它。

Function.prototype.memoize = function() {
  var self = this
  return function () {
    var args = Array.prototype.slice.call(arguments)
    self.cache = self.cache || {};
    return self.cache[args] ? self.cache[args] : (self.cache[args] = self(args))
  }
}

• 我们知道JS中定义的所有函数都是从Function.prototype继承的。因此，添加到Function.prototype的任何内容都可用于我们定义的所有函数。

我们现在再来试试:

function sqrt(arg) {
  return Math.sqrt(arg);
}
// ...
const memoizedSqrt = sqrt.memoize()
log(memoizedSqrt(4)) // 2, calculated
log(memoizedSqrt(4)) // 2, returns result from cache
log(memoizedSqrt(9)) // 3, calculated
log(memoizedSqrt(9)) // 3, returns result from cache
log(memoizedSqrt(25)) // 5, calculated
log(memoizedSqrt(25)) // 5, returns result from cache

Memoization: Speed and Benchmarking

memoization的目标是速度，他通过内存来提升速度。

看下面的对比: 文件名: memo.js:

function memoize(fn) {
  return function () {
    var args = Array.prototype.slice.call(arguments)
    fn.cache = fn.cache || {};
    return fn.cache[args] ? fn.cache[args] : (fn.cache[args] = fn.apply(this,args))
  }
}

function sqrt(arg) {
  return Math.sqrt(arg);
}
const memoizedSqrt = memoize(sqrt)
console.time("non-memoized call")
console.log(sqrt(4))
console.timeEnd("non-memoized call")
console.time("memoized call")
console.log(sqrt(4))
console.timeEnd("memoized call")

然后node memo.js可以发现输出，我这里是:

2
non-memoized call: 2.210ms
2
memoized call: 0.054ms

可以发现，速度还是提升了不少。

Memoization: 该什么时候使用

在这里，memoization通常会缩短执行时间并影响我们应用程序的性能。当我们知道一组输入将产生某个输出时，memoization最有效。

• 遵循最佳实践，应该在纯函数上实现memoization。纯函数输入什么就返回什么，不存在副作用。
• 记住这个是以空间换速度，所以最好确定你是否值得那么做，有些场景很有必要使用。
• 在处理递归函数时，Memoization最有效，递归函数用于执行诸如GUI渲染，Sprite和动画物理等繁重操作。

Memoization: 什么时候不要使用

不是纯函数的时候(输出不完全依赖于输入)。

使用案例：斐波那契系列(Fibonacci)

Fibonacci是许多复杂算法中的一种，使用memoization优化的作用很明显。

1,1,2,3,5,8,13,21,34,55,89 每个数字是前面两个数字的和。 现在我们用js实现:

function fibonacci(num) {
  if (num == 1 || num == 2) {
    return 1
  }
  return fibonacci(num-1) + fibonacci(num-2)
}

如果num超过2，则此函数是递归的。它以递减方式递归调用自身。

log(fibonacci(4)) // 3

让我们根据memoized版本对运行斐波那契的有效性进行测试。 memo.js文件:

function memoize(fn) {
  return function () {
    var args = Array.prototype.slice.call(arguments)
    fn.cache = fn.cache || {};
    return fn.cache[args] ? fn.cache[args] : (fn.cache[args] = fn.apply(this,args))
  }
}

function fibonacci(num) {
  if (num == 1 || num == 2) {
    return 1
  }
  return fibonacci(num-1) + fibonacci(num-2)
}

const memFib = memoize(fibonacci)
console.log('profiling tests for fibonacci')
console.time("non-memoized call")
console.log(memFib(6))
console.timeEnd("non-memoized call")
console.time("memoized call")
console.log(memFib(6))
console.timeEnd("memoized call")

接下来调用:

$ node memo.js
profiling tests for fibonacci
8
non-memoized call: 1.027ms
8
memoized call: 0.046ms