您现在的位置是：网站首页 > 记忆模式(Memoization)的性能优化文章详情
记忆模式(Memoization)的性能优化
陈川
【
JavaScript
】
27396人已围观
7099字
记忆模式(Memoization)的性能优化
记忆模式是一种通过缓存函数计算结果来避免重复计算的优化技术。当函数被再次调用时，如果参数相同，则直接返回缓存的结果，而不是重新执行计算。这种模式特别适用于计算密集型或递归函数，可以显著提升性能。
记忆模式的实现原理
记忆模式的核心思想是建立一个缓存对象，将函数的输入参数作为键，计算结果作为值存储起来。每次函数调用时，首先检查缓存中是否存在对应的计算结果，如果存在则直接返回，否则执行计算并将结果存入缓存。
function memoize(fn) {
const cache = {};
return function(...args) {
const key = JSON.stringify(args);
if (cache[key] !== undefined) {
return cache[key];
}
const result = fn.apply(this, args);
cache[key] = result;
return result;
};
}
这个基本实现有几个关键点：
- 使用闭包保存缓存对象
- 将参数序列化为字符串作为缓存键
- 只有在缓存未命中时才执行原函数
记忆模式的应用场景
递归函数优化
斐波那契数列计算是记忆模式的经典用例：
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(function(n) {
if (n <= 1) return n;
return memoizedFibonacci(n - 1) + memoizedFibonacci(n - 2);
});
未经记忆化的版本时间复杂度为O(2^n)，而记忆化后降为O(n)，性能提升显著。
复杂计算缓存
对于需要复杂数学运算的函数：
function expensiveCalculation(x, y) {
// 模拟耗时计算
for(let i = 0; i < 1000000000; i++) {}
return x * y + x / y;
}
const memoizedCalculation = memoize(expensiveCalculation);
API响应缓存
在需要频繁调用相同API的场景：
async function fetchUserData(userId) {
const response = await fetch(`/api/users/${userId}`);
return response.json();
}
const memoizedFetch = memoize(fetchUserData);
高级记忆化技术
自定义缓存键生成
默认的JSON.stringify可能不够灵活，可以自定义键生成函数：
function memoize(fn, keyGenerator) {
const cache = new Map();
return function(...args) {
const key = keyGenerator ? keyGenerator(...args) : JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}
基于WeakMap的缓存
对于对象参数，使用WeakMap可以避免内存泄漏：
function memoizeWeak(fn) {
const cache = new WeakMap();
return function(arg) {
if (cache.has(arg)) {
return cache.get(arg);
}
const result = fn.call(this, arg);
cache.set(arg, result);
return result;
};
}
LRU缓存策略
限制缓存大小，使用最近最少使用策略：
function memoizeLRU(fn, limit = 100) {
const cache = new Map();
return function(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
const value = cache.get(key);
cache.delete(key);
cache.set(key, value);
return value;
}
const result = fn.apply(this, args);
if (cache.size >= limit) {
const firstKey = cache.keys().next().value;
cache.delete(firstKey);
}
cache.set(key, result);
return result;
};
}
React中的记忆化应用
React提供了useMemo和useCallback来实现组件级别的记忆化：
function ExpensiveComponent({ data }) {
const processedData = useMemo(() => {
return data.map(item => ({
...item,
fullName: `${item.firstName} ${item.lastName}`,
age: new Date().getFullYear() - item.birthYear
}));
}, [data]);
return <div>{/* 使用processedData */}</div>;
}
对于事件处理函数：
function InteractiveComponent() {
const handleClick = useCallback(() => {
console.log('Clicked');
}, []);
return <button onClick={handleClick}>Click me</button>;
}
记忆模式的局限性
- 内存消耗：缓存会占用内存，特别是缓存大量结果时
- 参数变化：对于频繁变化的参数，缓存命中率低，反而增加开销
- 纯函数要求：记忆化只适用于纯函数，即相同输入总是产生相同输出
- 对象比较：对象参数需要深度比较或自定义比较逻辑
性能优化实践
选择性记忆化
不是所有函数都适合记忆化，应该针对性地选择：
// 适合记忆化
function calculateDistance(x1, y1, x2, y2) {
return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
}
// 不适合记忆化
function generateRandomId() {
return Math.random().toString(36).substr(2, 9);
}
缓存失效策略
实现缓存过期机制：
function memoizeWithExpiry(fn, ttl = 60000) {
const cache = {};
return function(...args) {
const key = JSON.stringify(args);
const now = Date.now();
if (cache[key] && now - cache[key].timestamp < ttl) {
return cache[key].value;
}
const result = fn.apply(this, args);
cache[key] = {
value: result,
timestamp: now
};
return result;
};
}
性能测试对比
使用console.time进行简单性能测试：
function testPerformance() {
// 普通斐波那契
console.time('normal');
fibonacci(40);
console.timeEnd('normal');
// 记忆化斐波那契
console.time('memoized');
memoizedFibonacci(40);
console.timeEnd('memoized');
}
记忆模式与其他模式的结合
与工厂模式结合
创建可配置的记忆化函数工厂：
function createMemoizer(options = {}) {
const {
maxSize = Infinity,
ttl = Infinity,
keyGenerator = JSON.stringify
} = options;
return function memoize(fn) {
const cache = new Map();
const timers = new Map();
return function(...args) {
const key = keyGenerator(...args);
// 检查缓存是否存在且未过期
if (cache.has(key)) {
if (Date.now() - cache.get(key).timestamp < ttl) {
return cache.get(key).value;
}
// 清除过期缓存
cache.delete(key);
if (timers.has(key)) {
clearTimeout(timers.get(key));
timers.delete(key);
}
}
// 执行函数并缓存结果
const result = fn.apply(this, args);
cache.set(key, {
value: result,
timestamp: Date.now()
});
// 设置缓存过期
if (ttl < Infinity) {
timers.set(key, setTimeout(() => {
cache.delete(key);
timers.delete(key);
}, ttl));
}
// 检查缓存大小
if (cache.size > maxSize) {
const oldestKey = cache.keys().next().value;
cache.delete(oldestKey);
if (timers.has(oldestKey)) {
clearTimeout(timers.get(oldestKey));
timers.delete(oldestKey);
}
}
return result;
};
};
}
与装饰器模式结合
在支持装饰器的环境中：
@memoize
class Calculator {
static add(a, b) {
console.log('Calculating...');
return a + b;
}
@memoize
multiply(a, b) {
console.log('Calculating...');
return a * b;
}
}
浏览器缓存API的记忆化应用
利用localStorage实现持久化记忆：
function memoizeWithStorage(fn, keyPrefix = 'memo_') {
return async function(...args) {
const key = keyPrefix + JSON.stringify(args);
try {
const cached = localStorage.getItem(key);
if (cached) {
return JSON.parse(cached);
}
const result = await fn.apply(this, args);
localStorage.setItem(key, JSON.stringify(result));
return result;
} catch (e) {
console.error('Storage error:', e);
return fn.apply(this, args);
}
};
}
记忆模式在函数式编程中的应用
在函数式编程中，记忆化可以保持函数的纯粹性：
// 柯里化函数与记忆化结合
function curryMemoize(fn) {
const cache = new Map();
const curried = (...args) => {
if (args.length >= fn.length) {
const key = JSON.stringify(args);
if (cache.has(key)) return cache.get(key);
const result = fn(...args);
cache.set(key, result);
return result;
}
return (...moreArgs) => curried(...args, ...moreArgs);
};
return curried;
}
const memoizedAdd = curryMemoize((a, b, c) => a + b + c);
memoizedAdd(1)(2)(3); // 计算并缓存
memoizedAdd(1)(2)(3); // 从缓存读取
