记忆化技术：用缓存加速函数执行

为什么需要记忆化

想象你在解一道复杂的数学题。第一次计算时, 你需要用笔和纸仔细演算, 花费了 10 分钟。但如果有人问你同样的问题第二次、第三次, 你不需要重新计算——你已经知道答案了, 可以直接从记忆中提取。

记忆化(Memoization)就是这个思想在编程中的应用:当函数被相同的参数调用时, 不重新计算, 而是直接返回之前缓存的结果。这种技术特别适合处理:

• 昂贵的计算: 如复杂的数学运算
• 重复调用: 函数会被相同参数多次调用
• 纯函数: 相同输入总是产生相同输出

基础实现

1. 最简单的记忆化

// 未优化的斐波那契
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.time("fib(40)");
console.log(fibonacci(40)); // 102334155
console.timeEnd("fib(40)"); // ~1000ms (非常慢!)

// 手动记忆化版本
const cache = {};

function fibonacciMemo(n) {
  // 检查缓存
  if (n in cache) {
    return cache[n];
  }

  // 基础情况
  if (n <= 1) {
    return n;
  }

  // 计算并缓存结果
  const result = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
  cache[n] = result;

  return result;
}

console.time("fibMemo(40)");
console.log(fibonacciMemo(40)); // 102334155
console.timeEnd("fibMemo(40)"); // ~1ms (快了1000倍!)

这个简单的改变带来了巨大的性能提升。让我们看看为什么:

// fibonacci(5) 的调用树(未优化)
                    fib(5)
                  /        \
            fib(4)          fib(3)
           /      \        /      \
       fib(3)   fib(2)  fib(2)  fib(1)
      /    \    /   \   /   \
  fib(2) fib(1) ... ... ... ...

// 注意 fib(3) 被计算了 2 次, fib(2) 被计算了 3 次!
// 记忆化后, 每个值只计算一次

2. 通用的记忆化函数

function memoize(fn) {
  const cache = new Map();

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

    // 检查缓存
    if (cache.has(key)) {
      console.log(`缓存命中: ${key}`);
      return cache.get(key);
    }

    // 计算结果
    console.log(`计算新值: ${key}`);
    const result = fn(...args);

    // 存入缓存
    cache.set(key, result);

    return result;
  };
}

// 应用到任何函数
const add = (a, b) => {
  console.log("执行加法");
  return a + b;
};

const memoizedAdd = memoize(add);

console.log(memoizedAdd(2, 3)); // 计算新值: [2,3]  执行加法  => 5
console.log(memoizedAdd(2, 3)); // 缓存命中: [2,3]  => 5
console.log(memoizedAdd(5, 7)); // 计算新值: [5,7]  执行加法  => 12

高级记忆化技术

1. 自定义缓存键生成器

function memoizeWithKeyGen(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(...args);
    cache.set(key, result);

    return result;
  };
}

// 处理对象参数时, 可以自定义键生成
const getUserData = (user) => {
  console.log("Fetching user data...");
  return { ...user, fetched: new Date() };
};

const memoizedGetUserData = memoizeWithKeyGen(
  getUserData,
  (user) => user.id // 只用 id 作为键
);

const user1 = { id: 1, name: "John" };
const user2 = { id: 1, name: "John Doe" }; // 不同的 name

console.log(memoizedGetUserData(user1)); // Fetching user data...
console.log(memoizedGetUserData(user2)); // 使用缓存 (因为 id 相同)

2. LRU(最近最少使用)缓存

限制缓存大小, 移除最久未使用的条目:

class LRUCache {
  constructor(maxSize = 100) {
    this.maxSize = maxSize;
    this.cache = new Map();
  }

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

    // 获取值并移到最后(标记为最近使用)
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);

    return value;
  }

  set(key, value) {
    // 如果键已存在, 先删除旧的
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }

    // 如果超过大小限制, 删除最老的条目
    if (this.cache.size >= this.maxSize) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }

    // 添加新条目
    this.cache.set(key, value);
  }

  has(key) {
    return this.cache.has(key);
  }
}

function memoizeWithLRU(fn, maxSize = 100) {
  const cache = new LRUCache(maxSize);

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

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

    const result = fn(...args);
    cache.set(key, result);

    return result;
  };
}

// 使用示例: 只缓存最近 5 次调用
const expensiveCalc = memoizeWithLRU(
  (n) => {
    let sum = 0;
    for (let i = 0; i < n; i++) {
      sum += i;
    }
    return sum;
  },
  5 // 最多缓存 5 个结果
);

3. 带过期时间的缓存

function memoizeWithTTL(fn, ttl = 60000) {
  // 默认 60 秒
  const cache = new Map();
  const timestamps = new Map();

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

    // 检查缓存是否存在且未过期
    if (cache.has(key)) {
      const timestamp = timestamps.get(key);

      if (now - timestamp < ttl) {
        console.log("缓存命中:", key);
        return cache.get(key);
      }

      // 过期则删除
      console.log("缓存已过期:", key);
      cache.delete(key);
      timestamps.delete(key);
    }

    // 计算新结果
    console.log("计算新值:", key);
    const result = fn(...args);

    // 存入缓存
    cache.set(key, result);
    timestamps.set(key, now);

    return result;
  };
}

// 模拟 API 调用
const fetchWeather = (city) => {
  console.log(`正在获取 ${city} 的天气...`);
  return { city, temp: Math.random() * 30, time: new Date() };
};

const cachedFetchWeather = memoizeWithTTL(fetchWeather, 5000); // 缓存 5 秒

console.log(cachedFetchWeather("Beijing")); // 计算新值
console.log(cachedFetchWeather("Beijing")); // 缓存命中

setTimeout(() => {
  console.log(cachedFetchWeather("Beijing")); // 缓存已过期, 重新获取
}, 6000);

4. 条件记忆化

只对满足特定条件的调用进行缓存:

function memoizeIf(fn, shouldCache) {
  const cache = new Map();

  return function (...args) {
    // 检查是否应该缓存这次调用
    if (!shouldCache(...args)) {
      return fn(...args);
    }

    const key = JSON.stringify(args);

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

    const result = fn(...args);
    cache.set(key, result);

    return result;
  };
}

// 只缓存大于 10 的计算
const heavyCalc = memoizeIf(
  (n) => {
    let result = 0;
    for (let i = 0; i < n; i++) {
      result += Math.sqrt(i);
    }
    return result;
  },
  (n) => n > 10 // 只缓存参数大于 10 的结果
);

console.log(heavyCalc(5)); // 不缓存
console.log(heavyCalc(100)); // 缓存
console.log(heavyCalc(100)); // 使用缓存

实际应用场景

1. React 组件优化

// React.memo 就是一种记忆化
import React, { useMemo, useCallback } from "react";

function ExpensiveComponent({ data, filter }) {
  // 记忆化昂贵的计算
  const filteredData = useMemo(() => {
    console.log("正在过滤数据...");
    return data.filter((item) => item.category === filter);
  }, [data, filter]); // 只在 data 或 filter 改变时重新计算

  // 记忆化回调函数
  const handleClick = useCallback(() => {
    console.log("处理点击");
  }, []); // 回调函数不会在每次渲染时重新创建

  return (
    <div>
      {filteredData.map((item) => (
        <div key={item.id} onClick={handleClick}>
          {item.name}
        </div>
      ))}
    </div>
  );
}

// 记忆化整个组件
const MemoizedComponent = React.memo(ExpensiveComponent);

2. API 请求缓存

class APIClient {
  constructor() {
    this.cache = new Map();
    this.pendingRequests = new Map();
  }

  async get(url, options = {}) {
    const cacheKey = `${url}:${JSON.stringify(options)}`;

    // 检查缓存
    if (this.cache.has(cacheKey)) {
      const { data, timestamp } = this.cache.get(cacheKey);
      const maxAge = options.maxAge || 60000;

      if (Date.now() - timestamp < maxAge) {
        console.log("使用缓存:", url);
        return data;
      }
    }

    // 检查是否有进行中的相同请求
    if (this.pendingRequests.has(cacheKey)) {
      console.log("等待进行中的请求:", url);
      return this.pendingRequests.get(cacheKey);
    }

    // 发起新请求
    console.log("发起新请求:", url);
    const promise = fetch(url, options)
      .then((res) => res.json())
      .then((data) => {
        // 存入缓存
        this.cache.set(cacheKey, {
          data,
          timestamp: Date.now(),
        });

        // 移除进行中的请求标记
        this.pendingRequests.delete(cacheKey);

        return data;
      });

    // 标记为进行中
    this.pendingRequests.set(cacheKey, promise);

    return promise;
  }

  clearCache() {
    this.cache.clear();
  }
}

// 使用
const api = new APIClient();

// 这三个调用会共享同一个请求
Promise.all([
  api.get("/api/users", { maxAge: 5000 }),
  api.get("/api/users", { maxAge: 5000 }),
  api.get("/api/users", { maxAge: 5000 }),
]).then((results) => {
  console.log("所有请求完成");
});

3. 复杂计算缓存

// 计算两点之间的最短路径
function findShortestPath(graph, start, end) {
  console.log(`计算从 ${start} 到 ${end} 的最短路径...`);

  // Dijkstra 算法实现...
  // 这里简化为示例
  return {
    path: [start, "A", "B", end],
    distance: 100,
  };
}

const memoizedFindPath = memoize(findShortestPath);

// 在地图应用中, 用户可能多次查询相同的路线
console.log(memoizedFindPath(graph, "Beijing", "Shanghai")); // 计算
console.log(memoizedFindPath(graph, "Beijing", "Shanghai")); // 缓存
console.log(memoizedFindPath(graph, "Shanghai", "Guangzhou")); // 计算
console.log(memoizedFindPath(graph, "Beijing", "Shanghai")); // 缓存

4. 数据转换管道缓存

// 复杂的数据处理管道
const processData = memoize((data) => {
  console.log("处理数据...");

  return data
    .filter((item) => item.active)
    .map((item) => ({
      ...item,
      fullName: `${item.firstName} ${item.lastName}`,
      age: new Date().getFullYear() - item.birthYear,
    }))
    .sort((a, b) => b.age - a.age);
});

const rawData = [
  { id: 1, firstName: "John", lastName: "Doe", birthYear: 1990, active: true },
  {
    id: 2,
    firstName: "Jane",
    lastName: "Smith",
    birthYear: 1985,
    active: true,
  },
  {
    id: 3,
    firstName: "Bob",
    lastName: "Johnson",
    birthYear: 1995,
    active: false,
  },
];

console.log(processData(rawData)); // 处理数据...
console.log(processData(rawData)); // 使用缓存

性能分析

让我们比较记忆化前后的性能差异:

// 性能测试工具
function benchmark(fn, iterations = 1000) {
  const start = performance.now();

  for (let i = 0; i < iterations; i++) {
    fn();
  }

  const end = performance.now();
  return end - start;
}

// 测试函数: 计算阶乘
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

const memoizedFactorial = memoize(factorial);

// 基准测试
console.log("=== 性能对比 ===");

console.log("未记忆化:");
console.log(benchmark(() => factorial(20)));

console.log("记忆化 (首次):");
console.log(benchmark(() => memoizedFactorial(20)));

console.log("记忆化 (缓存):");
console.log(benchmark(() => memoizedFactorial(20)));

// 典型结果:
// 未记忆化: ~15ms
// 记忆化 (首次): ~15ms
// 记忆化 (缓存): ~0.1ms (快 150 倍!)

注意事项和最佳实践

1. 何时使用记忆化

✅ 适合记忆化的场景:

• 纯函数(相同输入总是产生相同输出)
• 昂贵的计算
• 会被重复调用
• 参数空间有限

❌ 不适合记忆化的场景:

• 有副作用的函数
• 参数空间太大(会占用大量内存)
• 很少被重复调用
• 计算本身很快

// ❌ 不适合记忆化 - 有副作用
function saveUser(user) {
  fetch("/api/users", {
    method: "POST",
    body: JSON.stringify(user),
  });
}

// ❌ 不适合记忆化 - 返回随机值
function random() {
  return Math.random();
}

// ✅ 适合记忆化 - 纯函数, 昂贵计算
function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

2. 内存管理

// 监控缓存大小
function memoizeWithMonitoring(fn, maxSize = 1000) {
  const cache = new Map();

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

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

    const result = fn(...args);

    // 检查缓存大小
    if (cache.size >= maxSize) {
      console.warn(`缓存已满(${maxSize}), 清理最早的条目`);
      const firstKey = cache.keys().next().value;
      cache.delete(firstKey);
    }

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

  // 添加工具方法
  memoized.cache = cache;
  memoized.clearCache = () => cache.clear();
  memoized.getCacheSize = () => cache.size;

  return memoized;
}

const fn = memoizeWithMonitoring(expensiveCalc, 100);

// 监控和管理
console.log("缓存大小:", fn.getCacheSize());
fn.clearCache(); // 手动清理

3. 调试支持

function memoizeWithDebug(fn, name = fn.name) {
  const cache = new Map();
  let hits = 0;
  let misses = 0;

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

    if (cache.has(key)) {
      hits++;
      console.log(`[${name}] 缓存命中 (${hits}/${hits + misses})`);
      return cache.get(key);
    }

    misses++;
    console.log(`[${name}] 缓存未命中 (${hits}/${hits + misses})`);

    const result = fn(...args);
    cache.set(key, result);

    return result;
  };

  memoized.getStats = () => ({
    hits,
    misses,
    hitRate: hits / (hits + misses),
    cacheSize: cache.size,
  });

  return memoized;
}

const fn = memoizeWithDebug(expensiveFunction, "myFunc");

// 使用后查看统计
console.log(fn.getStats());
// { hits: 15, misses: 5, hitRate: 0.75, cacheSize: 5 }

小结

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

1. 原理简单: 用空间换时间, 缓存昂贵计算的结果
2. 适用场景: 纯函数、昂贵计算、重复调用
3. 高级特性: LRU 缓存、TTL、条件缓存
4. 实际应用: React 优化、API 缓存、复杂计算
5. 注意事项: 内存管理、只用于纯函数

掌握记忆化技术, 能让你的应用性能获得数量级的提升, 特别是在处理复杂计算和数据转换时。但不要过早优化, 先确保代码正确, 再根据实际性能瓶颈应用记忆化。

---