Memoize算法

在计算机领域，记忆(Memoization)是主要用于加速程序的一种优化技术，它使得函数避免重复演算已被处理过得输入，而返回缓存得结果。
by wikipedia

Memozation的原理是把函数的每次执行结果存入一个对象中，在接下来的执行中，在对象中查找是否已经有相应执行的值，如果有，则直接返回该值，没有才执行函数体的求值部分，在对象中找值得速度比在函数中快。

另外，Memozation只适用于确定性算法

let memoize = (fn)=> { 
  let cache = []
  return funciton(key) { 
    if(!cache[key]) { 
      cache[key] = fn.apply(this,arguments)
    }
    return cache[key]
  }
}

Underscore.js是一个很精干的库，压缩后只有4KB。它提供了几十种函数式编程的方法，弥补了标准库的不足，大大方便了JavaScript的编程。MVC框架Backbone.js就将这个库作为自己的工具库。除了可以在浏览器环境使用，Underscore.js还可以用于Node.js。

Underscor.js定义了一个下划线（_）对象，函数库的所有方法都属于这个对象。这些方法大致上可以分成：集合（collection）、数组（array）、函数（function）、对象（object）和工具（utility）五大类。

_.memoize = function(func,hasher) { 
  var memoize = function(key) { 
    // 将存储对象的引用拿出来，以方便使用
    var cache = memoize.cache
    // 如果有hash算法，使用hash算法对key进行计算
    var address = '' + (hasher?hasher.apply(this,arguments):key)
    if(!_.has(cache,address)) { 
      cache[address] = func.apply(this,arguments)
    }
    return cache[address]
  }
  // 给memoize 挂载一个map
  memoize.cache = {} 
  // 返回该柯里化函数，此处有闭包
  return memoize
}

可以应用于一般算法,但能不能应用于递归呢？以下是斐波那契算法

var conunt = 0  // 记录fibonacci计算次数
var fibonacci = functioin(n) { 
  count++;
  return n<2 ?n:fibonacci(n-2) + functioin(n-1)
}
for(var i=0;i<=10;i++) { 
  console.log(`i:${i}+fibonacci(i)`)
}

fibonacci = memoize(fibonacci);

for(var i = 0; i<= 10; i++) {
    console.log(`i: ${i}, ` + fibonacci(i));
}
console.log(count); // 12次数 运算次数明显减少