JavaScript学习笔记之函数记忆

本文讲解函数记忆与菲波那切数列的实现，分享给大家，具体如下

定义

函数记忆是指将上次的计算结果缓存起来，当下次调用时，如果遇到相同的参数，就直接返回缓存中的数据。

举个例子：

function add(a, b) {  return a + b;}// 假设 memorize 可以实现函数记忆var memoizedAdd = memorize(add);memoizedAdd(1, 2) // 3memoizedAdd(1, 2) // 相同的参数，第二次调用时，从缓存中取出数据，而非重新计算一次

原理

实现这样一个 memorize 函数很简单，原理上只用把参数和对应的结果数据存到一个对象中，调用时，判断参数对应的数据是否存在，存在就返回对应的结果数据。

第一版

我们来写一版：

// 第一版 (来自《JavaScript权威指南》)function memoize(f) {  var cache = {};  return function(){    var key = arguments.length + Array.prototype.join.call(arguments, ",");    if (key in cache) {      return cache[key]    }    else return cache[key] = f.apply(this, arguments)  }}

我们来测试一下：

var add = function(a, b, c) { return a + b + c}var memoizedAdd = memorize(add)console.time('use memorize')for(var i = 0; i < 100000; i++) {  memoizedAdd(1, 2, 3)}console.timeEnd('use memorize')console.time('not use memorize')for(var i = 0; i < 100000; i++) {  add(1, 2, 3)}console.timeEnd('not use memorize')

在 Chrome 中，使用 memorize 大约耗时 60ms，如果我们不使用函数记忆，大约耗时 1.3 ms 左右。

注意

什么，我们使用了看似高大上的函数记忆，结果却更加耗时，这个例子近乎有 60 倍呢！

所以，函数记忆也并不是万能的，你看这个简单的场景，其实并不适合用函数记忆。

需要注意的是，函数记忆只是一种编程技巧，本质上是牺牲算法的空间复杂度以换取更优的时间复杂度，在客户端 JavaScript 中代码的执行时间复杂度往往成为瓶颈，因此在大多数场景下，这种牺牲空间换取时间的做法以提升程序执行效率的做法是非常可取的。

第二版

因为第一版使用了 join 方法，我们很容易想到当参数是对象的时候，就会自动调用 toString 方法转换成 [Object object]，再拼接字符串作为 key 值。我们写个 demo 验证一下这个问题：

var propValue = function(obj){  return obj.value}var memoizedAdd = memorize(propValue)console.log(memoizedAdd({value: 1})) // 1console.log(memoizedAdd({value: 2})) // 1

// 第二版 (来自 underscore 的实现)var memorize = function(func, hasher) {  var memoize = function(key) {    var cache = memoize.cache;    var address = '' + (hasher ? hasher.apply(this, arguments) : key);    if (!cache[address]) {      cache[address] = func.apply(this, arguments);    }    return cache[address];  };  memoize.cache = {};  return memoize;};

var add = function(a, b, c) { return a + b + c}var memoizedAdd = memorize(add)memoizedAdd(1, 2, 3) // 6memoizedAdd(1, 2, 4) // 6

var memoizedAdd = memorize(add, function(){  var args = Array.prototype.slice.call(arguments)  return JSON.stringify(args)})console.log(memoizedAdd(1, 2, 3)) // 6console.log(memoizedAdd(1, 2, 4)) // 7

适用场景

我们以斐波那契数列为例：

var count = 0;var fibonacci = function(n){  count++;  return n < 2? n : fibonacci(n-1) + fibonacci(n-2);};for (var i = 0; i <= 10; i++){  fibonacci(i)}console.log(count) // 453

我们会发现最后的 count 数为 453，也就是说 fibonacci 函数被调用了 453 次！也许你会想，我只是循环到了 10，为什么就被调用了这么多次，所以我们来具体分析下：

当执行 fib(0) 时，调用 1 次

当执行 fib(1) 时，调用 1 次

当执行 fib(2) 时，相当于 fib(1) + fib(0) 加上 fib(2) 本身这一次，共 1 + 1 + 1 = 3 次

当执行 fib(3) 时，相当于 fib(2) + fib(1) 加上 fib(3) 本身这一次，共 3 + 1 + 1 = 5 次

当执行 fib(4) 时，相当于 fib(3) + fib(2) 加上 fib(4) 本身这一次，共 5 + 3 + 1 = 9 次

当执行 fib(5) 时，相当于 fib(4) + fib(3) 加上 fib(5) 本身这一次，共 9 + 5 + 1 = 15 次

当执行 fib(6) 时，相当于 fib(5) + fib(4) 加上 fib(6) 本身这一次，共 15 + 9 + 1 = 25 次

当执行 fib(7) 时，相当于 fib(6) + fib(5) 加上 fib(7) 本身这一次，共 25 + 15 + 1 = 41 次

当执行 fib(8) 时，相当于 fib(7) + fib(6) 加上 fib(8) 本身这一次，共 41 + 25 + 1 = 67 次

当执行 fib(9) 时，相当于 fib(8) + fib(7) 加上 fib(9) 本身这一次，共 67 + 41 + 1 = 109 次

当执行 fib(10) 时，相当于 fib(9) + fib(8) 加上 fib(10) 本身这一次，共 109 + 67 + 1 = 177 次
所以执行的总次数为：177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 次！

如果我们使用函数记忆呢？

var count = 0;var fibonacci = function(n) {  count++;  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);};fibonacci = memorize(fibonacci)for (var i = 0; i <= 10; i++) {  fibonacci(i)}console.log(count) // 12

我们会发现最后的总次数为 12 次，因为使用了函数记忆，调用次数从 453 次降低为了 12 次!