JS `Memoization` (记忆化)：缓存函数结果，避免重复计算

咳咳，大家好！今天咱们来聊聊一个听起来高大上，但实际上贼好用的东西——Memoization（记忆化）。说白了，它就是个“偷懒”神器，让你的代码跑得更快！

什么是Memoization？为啥要用它？

想象一下，你是个数学天才，但有时候也会忘记之前算过的结果。每次遇到同样的题目，都要吭哧吭哧重新算一遍，是不是觉得很浪费时间？ Memoization 就是你的“小抄本”，专门用来记住那些已经算过的答案。下次再遇到同样的题目，直接从“小抄本”上抄，效率杠杠的！

在编程里，Memoization 是一种优化技术，它通过缓存函数调用的结果，避免对相同的输入重复计算。简单来说，就是“记住”函数的结果，下次再用相同的参数调用函数时，直接返回缓存的结果，而不用重新执行函数。

那为啥要用它呢？主要有以下几个原因：

提高性能： 避免重复计算，尤其是在计算密集型的场景下，性能提升非常明显。
减少资源消耗： 降低 CPU 使用率，减少内存占用（虽然缓存本身也会占用内存，但通常来说收益大于成本）。
改善用户体验： 响应更快，用户体验更好。

Memoization 的基本原理

Memoization 的核心就是：

缓存： 创建一个缓存（通常是对象或 Map）来存储函数调用的结果。
查找： 在函数执行之前，先在缓存中查找是否存在对应输入参数的结果。
命中： 如果缓存命中（找到了结果），直接返回缓存的结果。
计算： 如果缓存未命中（没找到结果），执行函数，并将结果存入缓存，然后返回结果。

JS 中的 Memoization 实现方式

在 JavaScript 中，实现 Memoization 有多种方式。咱们一个一个来看：

1. 手动实现

这是最基础的方式，可以让你深入理解 Memoization 的原理。

function memoize(func) {
  const cache = {}; // 创建一个缓存对象

  return function(...args) {
    const key = JSON.stringify(args); // 将参数转换为字符串作为缓存的键

    if (cache[key]) {
      console.log("从缓存中取值");
      return cache[key]; // 如果缓存命中，直接返回缓存的结果
    } else {
      console.log("重新计算");
      const result = func.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(fibonacci);

console.log(memoizedFibonacci(5)); // 重新计算，输出 5
console.log(memoizedFibonacci(5)); // 从缓存中取值，输出 5
console.log(memoizedFibonacci(6)); // 重新计算，输出 8

代码解释：

memoize(func) 函数接收一个函数 func 作为参数，并返回一个“记忆化”后的新函数。
cache 对象用于存储缓存的结果，键是参数的字符串表示，值是函数的结果。
返回的新函数接收任意数量的参数 ...args。
JSON.stringify(args) 将参数转换为字符串，作为缓存的键。这是因为 JavaScript 对象不能直接作为对象的键。
如果 cache[key] 存在，说明缓存命中，直接返回缓存的结果。
如果 cache[key] 不存在，说明缓存未命中，执行函数 func.apply(this, args)，并将结果存入缓存，然后返回结果。 func.apply(this, args) 的作用是以指定的 this 值和参数列表调用函数。

2. 使用 Map 对象

相比于普通对象，Map 对象更适合作为缓存，因为它允许使用任意类型的值作为键，而不仅仅是字符串。

function memoizeWithMap(func) {
  const cache = new Map();

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

    if (cache.has(key)) {
      console.log("从缓存中取值 (Map)");
      return cache.get(key);
    } else {
      console.log("重新计算 (Map)");
      const result = func.apply(this, args);
      cache.set(key, result);
      return result;
    }
  };
}

// 示例：计算阶乘
function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

const memoizedFactorial = memoizeWithMap(factorial);

console.log(memoizedFactorial(5)); // 重新计算 (Map)，输出 120
console.log(memoizedFactorial(5)); // 从缓存中取值 (Map)，输出 120
console.log(memoizedFactorial(6)); // 重新计算 (Map)，输出 720

代码解释：

memoizeWithMap(func) 函数与 memoize(func) 函数类似，只不过使用了 Map 对象作为缓存。
cache.has(key) 检查缓存中是否存在指定的键。
cache.get(key) 从缓存中获取指定键的值。
cache.set(key, result) 将键值对存入缓存。

3. 使用 Lodash 的 memoize 函数

Lodash 是一个非常流行的 JavaScript 工具库，它提供了很多实用的函数，包括 memoize 函数。使用 Lodash 的 memoize 函数可以更简洁地实现 Memoization。

const _ = require('lodash'); // 引入 Lodash 库

// 示例：计算立方和
function sumOfCubes(n) {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += Math.pow(i, 3);
  }
  return sum;
}

const memoizedSumOfCubes = _.memoize(sumOfCubes);

console.log(memoizedSumOfCubes(5)); // 输出 225
console.log(memoizedSumOfCubes(5)); // 输出 225 (从缓存中取值)
console.log(memoizedSumOfCubes(10)); // 输出 3025

代码解释：

_.memoize(func) 直接返回 func 函数的记忆化版本。
Lodash 的 memoize 函数默认使用函数的第一个参数作为缓存的键。如果需要自定义键的生成方式，可以传入一个 resolver 函数作为第二个参数。

4. 使用闭包和立即执行函数

这种方式可以更好地封装缓存，避免被外部访问和修改。

const memoizeWithClosure = (func => {
  const cache = {};

  return (...args) => {
    const key = JSON.stringify(args);
    if (cache[key]) {
      console.log("从缓存中取值 (闭包)");
      return cache[key];
    } else {
      console.log("重新计算 (闭包)");
      const result = func.apply(this, args);
      cache[key] = result;
      return result;
    }
  };
})(); // 立即执行函数

// 示例：判断一个数是否为质数
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;
}

const memoizedIsPrime = memoizeWithClosure(isPrime);

console.log(memoizedIsPrime(7)); // 重新计算 (闭包)，输出 true
console.log(memoizedIsPrime(7)); // 从缓存中取值 (闭包)，输出 true
console.log(memoizedIsPrime(11)); // 重新计算 (闭包)，输出 true

代码解释：

使用立即执行函数 (func => { ... })() 创建一个闭包，将 cache 对象封装在闭包内部。
外部无法直接访问 cache 对象，只能通过返回的函数来访问和修改。

Memoization 的适用场景

Memoization 并非万能的，它只适用于某些特定的场景。一般来说，以下情况比较适合使用 Memoization：

计算密集型函数： 函数的执行时间较长，且需要频繁调用。
纯函数： 函数的返回值只依赖于输入参数，没有副作用。也就是说，对于相同的输入参数，函数总是返回相同的结果。
重复调用： 函数会被使用相同的参数多次调用。

以下是一些常见的适用场景：

递归函数： 例如斐波那契数列、阶乘等。
图形处理： 例如图像滤波、颜色转换等。
游戏开发： 例如碰撞检测、路径查找等。
数据分析： 例如复杂的数据转换、统计计算等。

Memoization 的注意事项

在使用 Memoization 时，需要注意以下几点：

缓存大小： 缓存会占用内存，如果缓存太大，可能会导致内存溢出。需要根据实际情况控制缓存的大小，例如使用 LRU (Least Recently Used) 算法来淘汰最久未使用的缓存项。
缓存失效： 如果函数的返回值依赖于外部状态（例如全局变量、数据库等），则缓存可能会失效。需要在外部状态发生变化时，手动清除缓存。
参数序列化： 将参数转换为字符串作为缓存的键时，需要注意参数的类型和顺序。如果参数是对象或数组，需要使用 JSON.stringify 等方法进行序列化。如果参数的顺序不同，但逻辑上是相同的，需要进行参数排序。
副作用： Memoization 只能用于纯函数。如果函数有副作用（例如修改全局变量、发送网络请求等），则 Memoization 可能会导致意想不到的结果。
Key 的选择: 选择合适的 Key 是非常重要的。简单的场景可以直接使用参数，复杂场景需要仔细设计 Key 的生成逻辑，确保唯一性和有效性。
复杂参数： 对于包含循环引用或者无法安全序列化的参数，Memoization 可能无法正常工作。
调试难度： Memoization 可能会增加代码的调试难度，因为缓存的存在会使代码的行为更加复杂。

Memoization 的一些优化技巧

惰性初始化： 只有在第一次调用函数时才创建缓存。
自定义 Key 生成函数： 根据实际情况自定义 Key 的生成方式，例如只使用参数的一部分作为 Key。
使用 WeakMap： 如果 Key 是对象，可以使用 WeakMap 来避免内存泄漏。 WeakMap 的 Key 是弱引用，当 Key 对象被垃圾回收时，对应的缓存项也会被自动删除。
结合其他优化技术： Memoization 可以与其他优化技术结合使用，例如尾递归优化、循环展开等。

总结

Memoization 是一种简单而有效的优化技术，可以显著提高代码的性能。但是，在使用 Memoization 时，需要根据实际情况进行权衡，并注意一些潜在的问题。

表格总结

特性	描述	优点	缺点
基本原理	缓存函数结果，避免重复计算	提高性能，减少资源消耗	增加内存占用，不适用于有副作用的函数，缓存失效问题，需要注意参数序列化
适用场景	计算密集型函数，纯函数，重复调用	显著提升性能，尤其对于递归函数	仅适用于特定场景，需要仔细考虑缓存大小和失效策略
实现方式	手动实现，使用 Map 对象，使用 Lodash 的 `memoize` 函数，使用闭包和立即执行函数	灵活性高，可控性强，方便快捷，封装性好	代码量增加，需要理解 Map 对象的使用，依赖外部库，代码相对复杂
注意事项	缓存大小，缓存失效，参数序列化，副作用	确保缓存的有效性和可控性	需要仔细考虑各种情况，避免出现意想不到的结果
优化技巧	惰性初始化，自定义 Key 生成函数，使用 WeakMap，结合其他优化技术	进一步提升性能和效率	需要更深入的理解和掌握

希望今天的讲座能帮助大家更好地理解和使用 Memoization！记住，写代码要像做人一样，能偷懒就偷懒！当然，前提是要保证代码的正确性和可维护性。下课！

发表回复 取消回复

发表回复取消回复