Memoization 是一种常用的技术,可以帮助显着加快代码速度。
这种技术依赖于缓存来存储先前完成的计算或执行的结果。缓存的目的是避免多次执行相同的工作。基于当前处理的方案,很容易清晰界定使用的边界:
以 斐波那契 为例:连续调用 fibonacci(32)
10次。
const fibonacci = (n) => (n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2))
for (let i = 1; i <= 10; i++) {
fibonacci(32)
} // ~600ms
Proxy/apply
实现const memoize = fn => new Proxy(fn, {
_cache: new Map(),
apply(target, thisArg, argumentsList) {
let key = argumentsList.toString()
if (!this._cache.has(key))
this._cache.set(key, target.apply(thisArg, argumentsList))
return this._cache.get(key)
}
})
const memoizedFibonacci = memoize(fibonacci);
for (let i = 1; i <= 10; i++) {
memoizedFibonacci(32)
} // ~62ms
仔细查看可得知,由于fibonacci
函数存在递归调用,所以上述 Memoization 形式只符合对整个函数执行结果进行缓存。
for (let i = 1; i <= 32; i++) {
fibonacci(i)
} // ~90ms
for (let i = 1; i <= 32; i++) {
memoizedFibonacci(i)
} // ~90ms
上述,起不到任何“记忆”效果。
const fibonacci = (function () {
let _caches = Object.create(null)
return function (n) {
if (!_caches[n])
_caches[n] = n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2)
return _caches[n]
}
})()
for (let i = 0; i < 32; i++) {
fibonacci(i)
} // ~0.2ms
前提:某函数存在在相同情况下多次调用的场景。