在JavaScript中如何使用记忆化?
什么是记忆化?
记忆化是一种常用的技术,可以显著加快代码的运行速度。它依赖于一个缓存来存储先前完成的工作单元的结果。缓存的目的是避免重复执行相同的工作,从而加快后续调用耗时函数的速度。
使用记忆化的条件
根据其定义,我们可以很容易地推断出一些条件,帮助我们发现适合记忆化的好候选函数:
- 执行缓慢、代价高或耗时较长的函数调用可以从记忆化中受益
- 记忆化加速后续调用,因此最好在预期在相同情况下多次调用相同函数时使用
- 结果存储在内存中,因此当在非常不同的情况下多次调用相同函数时,应避免使用记忆化
记忆化一个函数
在JavaScript中,编写自己的记忆化函数非常简单。对于这个实现,我们将使用一个Map
来存储结果。Map
对象保存键值对并记住键的原始插入顺序。这使得它非常适合记忆化,因为我们可以使用函数的参数作为键,使用结果作为值。
const memoize = fn => {
const cache = new Map();
const cached = function (val) {
return cache.has(val)
? cache.get(val)
: cache.set(val, fn.call(this, val)) && cache.get(val);
};
cached.cache = cache;
return cached;
};
// 这个函数执行缓慢,将受益于记忆化
const anagrams = str => {
if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str];
return str
.split('')
.reduce(
(acc, letter, i) =>
acc.concat(
anagrams(str.slice(0, i) + str.slice(i + 1)).map(val => letter + val)
),
[]
);
};
```js
const anagramsCached = memoize(anagrams);
anagramsCached('javascript');
// 花费很长时间
anagramsCached('javascript');
// 由于已经缓存,返回几乎立即完成
使用代理对象进行记忆化
虽然前面的例子是实现记忆化的一种好方法,但是JavaScript的代理对象提供了一种有趣的替代方案,通过使用handler.apply()
陷阱。
使用陷阱,我们可以拦截函数调用并检查结果是否已经缓存。如果已经缓存,我们返回缓存的结果。如果没有缓存,我们调用原始函数并在返回之前缓存结果。
const memoize = fn => new Proxy(fn, {
cache: new Map(),
apply (target, thisArg, argsList) {
let cacheKey = argsList.toString();
if(!this.cache.has(cacheKey))
this.cache.set(cacheKey, target.apply(thisArg, argsList));
return this.cache.get(cacheKey);
}
});
const fibonacci = n => (n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2));
const memoizedFibonacci = memoize(fibonacci);
for (let i = 0; i < 100; i ++)
fibonacci(30); // ~5000ms
for (let i = 0; i < 100; i ++)
memoizedFibonacci(30); // ~50ms