记忆模式(Memoization)的性能优化

记忆模式(Memoization)的性能优化

记忆模式是一种通过缓存函数计算结果来避免重复计算的优化技术。当函数被再次调用时，如果参数相同，则直接返回缓存的结果，而不是重新计算。这种模式特别适用于计算密集型或递归函数，可以显著提升性能。

记忆模式的实现原理

记忆模式的核心思想是建立一个缓存对象，将函数的输入参数作为键，计算结果作为值存储起来。每次调用函数时，首先检查缓存中是否存在对应的计算结果，如果存在则直接返回，否则执行计算并将结果存入缓存。

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 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);
});

// 性能对比
console.time('原始斐波那契');
fibonacci(40); // 耗时约1秒
console.timeEnd('原始斐波那契');

console.time('记忆化斐波那契');
memoizedFibonacci(40); // 耗时约1毫秒
console.timeEnd('记忆化斐波那契');

高级记忆模式实现

对于更复杂的场景，我们可以实现更强大的记忆化函数：

function advancedMemoize(fn, options = {}) {
  const {
    resolver = (...args) => JSON.stringify(args),
    maxSize = Infinity,
    ttl = Infinity
  } = options;
  
  const cache = new Map();
  const lruKeys = [];
  
  return function(...args) {
    const key = resolver(...args);
    
    // 检查缓存是否存在且未过期
    if (cache.has(key)) {
      const { value, timestamp } = cache.get(key);
      if (Date.now() - timestamp < ttl) {
        // 更新LRU顺序
        const index = lruKeys.indexOf(key);
        if (index > -1) {
          lruKeys.splice(index, 1);
          lruKeys.push(key);
        }
        return value;
      }
      cache.delete(key);
    }
    
    // 执行函数并缓存结果
    const result = fn.apply(this, args);
    cache.set(key, {
      value: result,
      timestamp: Date.now()
    });
    lruKeys.push(key);
    
    // 检查缓存大小限制
    if (cache.size > maxSize) {
      const oldestKey = lruKeys.shift();
      cache.delete(oldestKey);
    }
    
    return result;
  };
}

记忆模式的应用场景

记忆模式特别适合以下场景：

1. 纯函数：输出仅依赖于输入，没有副作用的函数
2. 计算密集型函数：执行成本高的计算
3. 递归函数：避免重复计算相同的子问题
4. API请求：缓存相同参数的请求结果

// 缓存API请求示例
const cachedFetch = memoize(async function(url) {
  const response = await fetch(url);
  return response.json();
});

// 多次调用相同URL只会发起一次请求
cachedFetch('/api/data').then(data => console.log(data));
cachedFetch('/api/data').then(data => console.log(data)); // 从缓存读取

记忆模式的局限性

虽然记忆模式能提升性能，但也有其局限性：

1. 内存消耗：缓存会占用内存，特别是缓存大量结果时
2. 非纯函数：不适用于依赖外部状态或有副作用的函数
3. 参数序列化：复杂对象的序列化可能影响性能
4. 缓存失效：需要手动处理缓存过期或清除

// 参数序列化问题示例
const obj1 = { a: 1, b: 2 };
const obj2 = { b: 2, a: 1 };

// 这两个对象内容相同但序列化结果不同
console.log(JSON.stringify(obj1)); // {"a":1,"b":2}
console.log(JSON.stringify(obj2)); // {"b":2,"a":1}

React中的记忆模式应用

React提供了useMemo和useCallback钩子来实现组件级别的记忆化：

import React, { useMemo } from 'react';

function ExpensiveComponent({ list, filter }) {
  const filteredList = useMemo(() => {
    return list.filter(item => item.includes(filter));
  }, [list, filter]); // 只有当list或filter变化时重新计算

  return (
    <ul>
      {filteredList.map(item => (
        <li key={item}>{item}</li>
      ))}
    </ul>
  );
}

记忆模式与动态规划

记忆模式是动态规划算法的基础技术之一。许多动态规划问题可以通过记忆化递归来解决：

// 背包问题的记忆化解决方案
function knapsack(values, weights, capacity) {
  const memo = {};
  
  function recurse(i, remainingCapacity) {
    const key = `${i},${remainingCapacity}`;
    if (key in memo) return memo[key];
    
    if (i === values.length || remainingCapacity <= 0) {
      return 0;
    }
    
    if (weights[i] > remainingCapacity) {
      return recurse(i + 1, remainingCapacity);
    }
    
    const include = values[i] + recurse(i + 1, remainingCapacity - weights[i]);
    const exclude = recurse(i + 1, remainingCapacity);
    
    memo[key] = Math.max(include, exclude);
    return memo[key];
  }
  
  return recurse(0, capacity);
}

记忆模式的替代方案

在某些情况下，其他优化技术可能比记忆模式更合适：

1. 循环替代递归：避免递归调用栈限制
2. 预计算：提前计算并存储所有可能结果
3. 惰性计算：只在需要时计算
4. 分治策略：将问题分解为更小的子问题

// 斐波那契数列的迭代解法
function fibonacciIterative(n) {
  if (n <= 1) return n;
  
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    const temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}

记忆模式的性能考量

实现记忆模式时需要考虑以下性能因素：

1. 缓存键生成：简单快速的键生成算法
2. 缓存数据结构：根据场景选择对象、Map或WeakMap
3. 缓存大小限制：避免内存泄漏
4. 缓存清除策略：LRU、定时清除等

// 使用WeakMap处理对象键
const weakMemoize = (fn) => {
  const cache = new WeakMap();
  return (obj) => {
    if (cache.has(obj)) {
      return cache.get(obj);
    }
    const result = fn(obj);
    cache.set(obj, result);
    return result;
  };
};

记忆模式在函数式编程中的应用

在函数式编程中，记忆模式可以与其他函数组合技术结合使用：

// 结合柯里化的记忆化函数
function curryMemoize(fn) {
  const cache = new Map();
  
  function 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 add = curryMemoize((a, b, c) => a + b + c);
console.log(add(1)(2)(3)); // 6
console.log(add(1)(2)(3)); // 从缓存读取