跳到主要内容

JavaScript 函数记忆化

什么是函数记忆化?

函数记忆化(Memoization)是一种优化技术,主要用于提高程序的性能。其核心思想是缓存函数的计算结果,当下次以相同的参数调用该函数时,直接返回缓存的结果,而不必再次执行整个函数体的运算过程。

记忆化特别适用于:

  • 计算量大的函数
  • 具有相同输入多次调用的函数
  • 纯函数(相同输入总是产生相同输出,无副作用)
备注

"记忆化"这个术语来源于"记忆"一词,表示函数"记住"了之前计算过的结果。

记忆化的基本实现

让我们从一个简单的例子开始理解记忆化的原理:

javascript
// 没有记忆化的函数
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}

// 使用记忆化的fibonacci函数
function memoizedFibonacci() {
// 创建缓存对象
const cache = {};

// 返回接受参数的内部函数
return function(n) {
// 如果结果已经缓存,直接返回
if (n in cache) {
console.log(`从缓存获取fibonacci(${n})`);
return cache[n];
}

// 否则计算结果并缓存
console.log(`计算fibonacci(${n})`);
let result;
if (n <= 1) {
result = n;
} else {
result = this(n - 1) + this(n - 2);
}

cache[n] = result;
return result;
};
}

// 创建记忆化fibonacci函数实例
const fib = memoizedFibonacci();

console.log(fib(5)); // 首次计算
console.log(fib(5)); // 从缓存获取

输出结果:

计算fibonacci(5)
计算fibonacci(4)
计算fibonacci(3)
计算fibonacci(2)
计算fibonacci(1)
计算fibonacci(0)
计算fibonacci(1)
计算fibonacci(2)
计算fibonacci(3)
5
从缓存获取fibonacci(5)
5

通用记忆化函数

我们可以创建一个通用的记忆化高阶函数,用于包装任何需要记忆化的函数:

javascript
function memoize(fn) {
const cache = {};

return function(...args) {
// 使用参数作为缓存键
const key = JSON.stringify(args);

if (key in cache) {
return cache[key];
}

const result = fn.apply(this, args);
cache[key] = result;
return result;
};
}

// 使用示例
function slowAdd(a, b) {
console.log('执行复杂计算...');
// 模拟耗时计算
const start = Date.now();
while (Date.now() - start < 100) { /* 等待100毫秒 */ }
return a + b;
}

const fastAdd = memoize(slowAdd);

console.log(fastAdd(1, 2)); // 首次调用,执行slowAdd
console.log(fastAdd(1, 2)); // 从缓存获取结果

输出结果:

执行复杂计算...
3
3

函数记忆化的适用场景

1. 递归函数优化

递归函数如斐波那契数列计算、阶乘计算等,通过记忆化可以避免重复计算子问题。

javascript
// 记忆化阶乘函数
const factorial = memoize(function(n) {
console.log(`计算factorial(${n})`);
if (n === 0 || n === 1) return 1;
return n * factorial(n - 1);
});

console.log(factorial(5));
console.log(factorial(6)); // 只需额外计算6*factorial(5)

2. API请求缓存

当需要多次获取相同资源时,可以用记忆化避免重复网络请求:

javascript
const fetchUserData = memoize(async function(userId) {
console.log(`Fetching data for user ${userId}...`);
const response = await fetch(`https://api.example.com/users/${userId}`);
return response.json();
});

// 首次调用会发起请求,后续相同参数调用将使用缓存
fetchUserData(123).then(data => console.log("First call"));
fetchUserData(123).then(data => console.log("Second call (from cache)"));

3. 计算密集型操作

例如,图像处理、复杂数学计算等:

javascript
const processImage = memoize(function(imageData, filterType) {
console.log(`应用${filterType}滤镜...`);
// 计算密集型图像处理...
return /* 处理后的图像数据 */;
});

记忆化的注意事项和限制

虽然函数记忆化非常有用,但需要注意以下几点:

警告
  1. 内存使用:缓存会占用内存,对于大量不同输入值的函数,可能导致内存问题。
  2. 非纯函数:依赖外部状态或有副作用的函数不适合记忆化。
  3. 复杂参数:使用对象作为参数时,需要确保正确生成缓存键。

带有过期时间的记忆化

有时我们需要让缓存在一定时间后失效:

javascript
function memoizeWithExpiration(fn, maxAge) {
const cache = {};

return function(...args) {
const key = JSON.stringify(args);

const currentTime = Date.now();
if (key in cache && currentTime - cache[key].timestamp < maxAge) {
return cache[key].value;
}

const result = fn.apply(this, args);
cache[key] = {
value: result,
timestamp: currentTime
};
return result;
};
}

// 缓存结果,有效期10秒
const fetchDataWithCache = memoizeWithExpiration(fetchData, 10 * 1000);

高级记忆化技术

使用Map或WeakMap

使用Map可以允许任何类型的键,而WeakMap则提供了更好的垃圾回收支持:

javascript
function memoizeWithMap(fn) {
const cache = new Map();

return function(...args) {
// 使用第一个参数作为键(适用于单参数函数)
const key = args[0];

if (cache.has(key)) {
return cache.get(key);
}

const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}

LRU缓存策略

当内存是个问题时,可以实现最近最少使用(LRU)缓存策略,限制缓存大小:

javascript
function memoizeWithLRU(fn, capacity = 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 >= capacity) {
const oldestKey = cache.keys().next().value;
cache.delete(oldestKey);
}

cache.set(key, result);
return result;
};
}

实际应用案例

案例1:优化网站搜索功能

javascript
// 搜索函数
function searchProducts(query, filters) {
// 复杂搜索逻辑...
console.log('执行搜索,查询:', query, '过滤:', filters);

// 模拟搜索耗时
return new Promise(resolve => {
setTimeout(() => {
resolve([
{ id: 1, name: `产品 ${query}-1` },
{ id: 2, name: `产品 ${query}-2` }
]);
}, 500);
});
}

// 记忆化搜索函数
const memoizedSearch = memoize(searchProducts);

// 用户多次搜索相同内容时,只会执行一次实际搜索
async function handleUserSearch() {
console.time('首次搜索');
await memoizedSearch('手机', { price: 'high' });
console.timeEnd('首次搜索');

console.time('重复搜索');
await memoizedSearch('手机', { price: 'high' });
console.timeEnd('重复搜索');
}

// 在用户界面调用这个函数
handleUserSearch();

案例2:图表计算优化

javascript
// 图表数据处理函数
function processChartData(rawData) {
console.log('处理图表数据...');

// 假设这是一个复杂的数据转换过程
const results = rawData.map(item => {
// 复杂计算...
return {
label: item.name,
value: item.value * 1.5,
percentage: (item.value / 1000) * 100
};
});

return results;
}

// 记忆化处理函数
const memoizedProcessChart = memoize(processChartData);

// 在图表组件中使用
function renderChart(data) {
// 每次渲染图表时都调用数据处理函数
const processedData = memoizedProcessChart(data);

// 使用处理后的数据绘制图表...
console.log('图表已绘制:', processedData.length, '个数据点');
}

// 多次使用相同数据渲染图表
const sampleData = [
{ name: 'A', value: 300 },
{ name: 'B', value: 500 },
{ name: 'C', value: 200 }
];

renderChart(sampleData); // 首次处理数据
renderChart(sampleData); // 使用缓存结果

记忆化与现代JavaScript

在现代JavaScript应用中,还可以结合记忆化与其他模式:

结合React hooks

javascript
// React自定义hook中使用记忆化
function useMemoizedFetch() {
const cache = React.useRef({});

return React.useCallback(async (url) => {
if (cache.current[url]) {
return cache.current[url];
}

const response = await fetch(url);
const data = await response.json();
cache.current[url] = data;
return data;
}, []);
}

// 在组件中使用
function ProductList() {
const fetchData = useMemoizedFetch();
// ...
}

结合工具库

许多流行的JavaScript库提供内置的记忆化功能:

javascript
// 使用Lodash的memoize函数
import { memoize } from 'lodash';

const memoizedCalc = memoize(expensiveCalculation);

总结

函数记忆化是一种强大的性能优化技术,通过缓存函数调用结果来避免重复计算。主要优点包括:

  • 减少重复计算,提高性能
  • 特别适用于纯函数和计算密集型操作
  • 可以显著提升递归函数性能

主要注意事项:

  • 内存使用增加
  • 仅适用于纯函数
  • 需要正确处理复杂参数和缓存键

记忆化是JavaScript高级优化技术之一,掌握它可以帮助你编写更高效的代码,特别是在处理计算密集型应用或需要频繁重复计算的场景中。

练习与扩展

  1. 基础练习:实现一个记忆化的求平方根函数。
  2. 中级练习:创建一个带有最大缓存项数限制的记忆化函数。
  3. 高级练习:实现记忆化版本的深度优先搜索算法,用于解决迷宫问题。
延伸阅读
  • 《JavaScript设计模式》中的缓存模式
  • 研究Lodash或Ramda库中的记忆化实现
  • 探索不同缓存策略(LRU、FIFO等)的性能比较

通过这些练习和深入学习,你将能够自信地在项目中应用记忆化技术,提高应用性能。