JS专题之memoization
前言
在计算机领域,记忆(memoization)是主要用于加速程序计算的一种优化技术,它使得函数避免重复演算之前已被处理过的输入,而返回已缓存的结果。 – wikipedia
Memoization
的原理就是把函数的每次执行结果都放入一个对象中,在接下来的执行中,在对象中查找是否已经有相应执行过的值,如果有,直接返回该值,没有才真正执行函数体的求值部分。在对象里找值是要比执行函数的速度要快的。
另外,Memoization
只适用于确定性算法,对于相同的输入总是生成相同的输出,即纯函数。
一、简单实现
通过 Memoization 的定义和原理,我们就可以初步实现 Memoization 了。
1 | let memoize = function(func) { |
是不是很简单~ 函数记忆其实就是利用闭包,将函数参数作为存储对象的键(key),函数结果作为存储对象的 value 值。
二、underscore 实现
underscore 的源码中有 Memoization 方法的封装,它支持传入一个 hasher 用来计算缓存对象 key 的计算方式。
1 | _.memoize = function(func, hasher) { |
三、应用 - 判断素数
质数为在大于 1 的自然数中,除了 1 和它本身以外不再有其他因数。
我们通过判断素数的函数,看看使用了函数记忆后的效果。
1 | function isPrime(value) { |
四、应用 - 计算斐波那契数列
斐波那契数列的特点是后一个数等于前面两个数的和
指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波那契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=Fn-1+Fn-2
计算斐波那契数列是用来演示函数记忆很好的例子,因为计算斐波那契数列函数里面用了大量的递归。
1 | var count = 0; |
我们可以看出,如果从 0 开始打印斐波那契数列,fibonacci 函数被执行了 453 次。那我们就牺牲一小部分内存,用来缓存每次计算的值。
1 | fibonacci = memoize(fibonacci); |
通过 memoize 函数记忆,使得函数执行次数只需要 12 次,大大优化了函数执行计算的性能消耗,
总结
函数记忆(memoization)将函数的参数和结果值,保存在对象当中,用一部分的内存开销来提高程序计算的性能,常用在递归和重复运算较多的场景。