Memoization相关的知识
什么是Memoization
简单来说,memoization 是一种优化技术,其实就是一种缓存机制。主要用于通过存储昂贵的函数调用的结果来加速计算机程序,并在再次发生相同的输入时返回缓存的结果。
原理就是把函数的每次执行结果存放到一个散列表中,在接下来的执行中,在散列表中查找是否已经有相关执行过得值,如果有,直接返回该值,如果没有菜真正执行函数体的求职部分。很明显,找值,尤其是在散列中找值,比执行函数快多了。
例子1
Fibonacci数列的优化
//原始的fibonacc数列方法
function fibonacci(n) {
if (n === 0 || n === 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.time("fibonacci方法耗时");
fibonacci(20);
console.timeEnd("fibonacci方法耗时");
// 使用了Memoization的fibonacci
var fibonacci_memoization = (function () {
var cache = [];
return function (n) {
if(n === 0 || n === 1){
return n;
}else{
cache[n-1] = cache[n-1] || fibonacci_memoization(n-1);
cache[n-2] = cache[n-2] || fibonacci_memoization(n-2);
return cache[n-1]+cache[n-2];
}
}
})()
console.time("fibonacci_memoization方法耗时");
fibonacci_memoization(20);
console.timeEnd("fibonacci_memoization方法耗时");
例子2
// 普通阶乘函数
const factorial = n => {
if(n === 1){
return 1
} else{
return factorial(n-1) * n;
}
}
console.time("factorial方法耗时");
console.log(factorial(10));
console.timeEnd("factorial方法耗时");
// 使用了memoization
const cache = []
const factorial_memoization = n => {
if(n===1){
return 1;
} else if (cache[n-1]){
return cache[n-1];
} else {
let reault = factorial_memoization(n-1) * n
cache[n-1] = reault;
return reault;
}
}
console.time("factorial_memoization方法耗时");
console.log(factorial_memoization(10));;
console.timeEnd("factorial_memoization方法耗时");
// 常见的闭包形式
const factorialMemo = () => {
const cache = []
const factorial = n => {
if (n === 1) {
return 1
} else if (cache[n - 1]) {
console.log(`get factorial(${n}) from cache...`)
return cache[n - 1]
} else {
let result = factorial(n - 1) * n
cache[n - 1] = result
return result
}
}
return factorial
};
const factorialMemofun = factorialMemo();
console.time("factorialMemofun方法耗时");
console.log(factorialMemofun(10));;
console.timeEnd("factorialMemofun方法耗时");