JavaScript内核与高级编程之：`JavaScript`的`Memoization`：如何实现函数结果的缓存，避免重复计算。

各位亲爱的代码爱好者们，晚上好！我是今晚的讲师，很高兴能跟大家聊聊JavaScript里的一个超级实用技巧——Memoization（备忘录模式）。这玩意儿就像给你的函数装了个小脑瓜，能记住算过的值，下次再算同样的，直接从“记忆”里拿，省时省力！

今天咱们就来深入扒一扒 Memoization，保证让各位听完之后，下次写代码的时候也能优雅地用上它，让你的程序跑得更快更顺畅。

一、啥是 Memoization？别被名字吓着！

Memoization，翻译过来就是“备忘录”，顾名思义，就是把函数的结果“记住”，下次再用同样的参数调用这个函数，直接返回之前的结果，避免重复计算。

可以这样理解：你第一次做一道复杂的数学题，算了半天得出答案。下次又遇到这道题，你直接把之前的答案抄过来，是不是快多了？Memoization 干的就是这个事儿。

二、Memoization 的适用场景：哪些函数适合“装脑瓜”？

Memoization 并不是万能的，它只对特定类型的函数有效。一般来说，以下类型的函数适合使用 Memoization：

1. 计算密集型函数： 这种函数计算量大，耗时较长，重复计算的代价很高。比如计算斐波那契数列、阶乘、或者一些复杂的数学公式。
2. 纯函数： 纯函数是指，给定相同的输入，永远返回相同的输出，而且没有任何副作用。这意味着，相同的参数一定能得到相同的结果，可以安全地缓存。
3. 参数范围有限的函数： 如果函数的参数范围很大，那么缓存所有结果可能会占用大量内存，得不偿失。所以参数范围有限的函数更适合 Memoization。

三、JavaScript 实现 Memoization 的几种方式：手把手教你“装脑瓜”

接下来，咱们就来实战一下，看看在 JavaScript 里怎么给函数“装脑瓜”。

1. 简单粗暴版：用对象缓存结果

这是最简单的实现方式，用一个对象来存储函数的参数和结果。

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

  return function(...args) {
    const key = JSON.stringify(args); // 将参数序列化为字符串作为 key
    if (cache[key]) {
      console.log("从缓存中读取结果");
      return cache[key]; // 如果缓存中有结果，直接返回
    } else {
      console.log("计算并缓存结果");
      const result = func.apply(this, args); // 调用原始函数计算结果
      cache[key] = result; // 将结果存入缓存
      return result; // 返回结果
    }
  };
}

// 举个栗子：计算阶乘
function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

const memoizedFactorial = memoize(factorial); // 创建 memoized 版本的 factorial

console.log(memoizedFactorial(5)); // 计算并缓存结果
console.log(memoizedFactorial(5)); // 从缓存中读取结果
console.log(memoizedFactorial(6)); // 计算并缓存结果

这个例子里，memoize 函数接收一个函数 func 作为参数，返回一个新的函数。这个新函数会先检查缓存对象 cache 中是否存在对应参数的结果，如果存在，直接返回；如果不存在，就调用原始函数 func 计算结果，并将结果存入缓存对象，然后返回。

优点： 简单易懂，容易实现。

缺点：

• 只能缓存原始类型的参数（因为对象的 key 只能是字符串）。
• JSON.stringify 序列化参数可能会影响性能，特别是参数结构复杂的时候。
• 没有考虑缓存大小限制，可能会导致内存泄漏。
• this 上下文丢失，如果原始函数依赖 this，需要 bind 或者 apply 处理。

2. 升级版：使用 Map 缓存结果

ES6 引入了 Map 数据结构，它允许使用任意类型的值作为 key，这解决了简单粗暴版的第一个缺点。

function memoize(func) {
  const cache = new Map(); // 使用 Map 作为缓存

  return function(...args) {
    const key = args.join('-'); // 将参数组合成字符串作为 key，更高效

    if (cache.has(key)) {
      console.log("从缓存中读取结果");
      return cache.get(key); // 如果缓存中有结果，直接返回
    } else {
      console.log("计算并缓存结果");
      const result = func.apply(this, args); // 调用原始函数计算结果
      cache.set(key, result); // 将结果存入缓存
      return result; // 返回结果
    }
  };
}

// 举个栗子：计算两数之和
function add(a, b) {
  console.log(`执行 add 函数，a=${a}, b=${b}`);
  return a + b;
}

const memoizedAdd = memoize(add); // 创建 memoized 版本的 add

console.log(memoizedAdd(2, 3)); // 计算并缓存结果
console.log(memoizedAdd(2, 3)); // 从缓存中读取结果
console.log(memoizedAdd(4, 5)); // 计算并缓存结果

这个例子里，我们使用了 Map 代替了普通对象，并且使用 args.join('-') 拼接参数，比 JSON.stringify 更高效。

优点：

• 可以使用任意类型的值作为 key。
• 比 JSON.stringify 更高效。

缺点：

• 仍然没有考虑缓存大小限制。
• this 上下文丢失。

3. 高级版：带缓存大小限制的 Memoization

为了防止内存泄漏，我们可以给缓存加上大小限制，当缓存达到上限时，删除最久未使用的数据。

function memoize(func, maxSize = 10) {
  const cache = new Map();
  const keys = []; // 用于记录 key 的使用顺序

  return function(...args) {
    const key = args.join('-');

    if (cache.has(key)) {
      // 如果缓存中有结果，将 key 移动到队尾
      const index = keys.indexOf(key);
      keys.splice(index, 1);
      keys.push(key);

      console.log("从缓存中读取结果");
      return cache.get(key);
    } else {
      console.log("计算并缓存结果");
      const result = func.apply(this, args);
      cache.set(key, result);
      keys.push(key);

      // 如果缓存超出大小限制，删除最久未使用的数据
      if (keys.length > maxSize) {
        const oldestKey = keys.shift();
        cache.delete(oldestKey);
        console.log(`缓存超出限制，删除 key: ${oldestKey}`);
      }

      return result;
    }
  };
}

// 举个栗子：还是两数之和
function add(a, b) {
  console.log(`执行 add 函数，a=${a}, b=${b}`);
  return a + b;
}

const memoizedAdd = memoize(add, 3); // 创建 memoized 版本的 add，缓存大小为 3

console.log(memoizedAdd(1, 2));
console.log(memoizedAdd(2, 3));
console.log(memoizedAdd(3, 4));
console.log(memoizedAdd(1, 2)); // 从缓存读取
console.log(memoizedAdd(4, 5)); // 缓存超出限制，删除 (2,3)
console.log(memoizedAdd(2, 3)); // 重新计算并缓存

这个例子里，我们使用了一个数组 keys 来记录 key 的使用顺序，每次访问缓存时，都将 key 移动到队尾。当缓存超出大小限制时，删除数组头部（即最久未使用）的 key，并从缓存中删除对应的 value。

优点：

• 可以限制缓存大小，防止内存泄漏。

缺点：

• this 上下文丢失。
• 需要维护一个额外的数组 keys，增加了代码复杂度。

4. 终极版：完美解决所有问题

function memoize(func, options = {}) {
    const { maxSize = Infinity, resolver = (...args) => args.join('-'), thisArg = null } = options;
    const cache = new Map();
    const keys = [];

    return function(...args) {
        const key = resolver.apply(thisArg, args);

        if (cache.has(key)) {
            // 如果缓存中有结果，将 key 移动到队尾
            const index = keys.indexOf(key);
            keys.splice(index, 1);
            keys.push(key);

            console.log("从缓存中读取结果");
            return cache.get(key);
        } else {
            console.log("计算并缓存结果");
            const result = func.apply(thisArg, args);
            cache.set(key, result);
            keys.push(key);

            // 如果缓存超出大小限制，删除最久未使用的数据
            if (keys.length > maxSize) {
                const oldestKey = keys.shift();
                cache.delete(oldestKey);
                console.log(`缓存超出限制，删除 key: ${oldestKey}`);
            }

            return result;
        }
    };
}

// 举个栗子：
const myObject = {
    value: 10,
    add: function(a, b) {
        console.log(`执行 add 函数，a=${a}, b=${b}, this.value=${this.value}`);
        return a + b + this.value;
    }
};

const memoizedAdd = memoize(myObject.add, { thisArg: myObject, maxSize: 2, resolver: (a, b) => `${a}+${b}` });

console.log(memoizedAdd(1, 2));
console.log(memoizedAdd(2, 3));
console.log(memoizedAdd(1, 2)); // 从缓存读取
console.log(memoizedAdd(3, 4)); // 缓存超出限制，删除 (2,3)
console.log(memoizedAdd(2, 3)); // 重新计算并缓存

const memoizedSimpleAdd = memoize((a,b) => a + b, {maxSize:2})
console.log(memoizedSimpleAdd(5,6))
console.log(memoizedSimpleAdd(5,6))

这个版本提供了以下几个增强：

• maxSize: 允许设置缓存的最大容量，默认是 Infinity（无限大）。
• resolver: 允许自定义生成缓存 key 的函数。默认使用 args.join('-')。这对于参数类型复杂或需要更精细的 key 生成逻辑的场景非常有用。
• thisArg: 允许指定函数执行时的 this 上下文。

优点：

• 完美解决了之前版本的所有缺点。
• 灵活性高，可以根据实际需求进行配置。

5. 使用现成库：lodash 的 _.memoize

如果你不想自己写 Memoization 函数，可以使用现成的库，比如 lodash。lodash 提供了 _.memoize 函数，可以方便地实现 Memoization。

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

function add(a, b) {
  console.log(`执行 add 函数，a=${a}, b=${b}`);
  return a + b;
}

const memoizedAdd = _.memoize(add); // 使用 lodash 的 _.memoize

console.log(memoizedAdd(2, 3));
console.log(memoizedAdd(2, 3));
console.log(memoizedAdd(4, 5));

优点：

• 方便快捷，无需自己实现。
• 经过充分测试，稳定可靠。

缺点：

• 需要引入额外的库。
• 定制性不如自己实现灵活。

四、Memoization 的注意事项：别踩坑！

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

1. 缓存的 key 必须是唯一的： 确保不同的参数组合生成不同的 key，否则会导致缓存失效。
2. 缓存大小的控制： 合理设置缓存大小，防止内存泄漏。
3. 纯函数的保证： 只有纯函数才能安全地使用 Memoization。
4. 参数类型的考虑： 复杂的参数类型可能需要自定义 key 生成逻辑。
5. this 上下文的处理： 如果原始函数依赖 this，需要正确绑定 this。

五、各种Memoization 方法对比

方法	优点	缺点	适用场景
简单对象缓存	简单易懂，容易实现。	只能缓存原始类型的参数，JSON.stringify 序列化参数可能影响性能，没有考虑缓存大小限制，this 上下文丢失。	快速原型验证，或者参数都是原始类型且数量较少，性能要求不高的场景。
Map 缓存	可以使用任意类型的值作为 key，比 JSON.stringify 更高效。	仍然没有考虑缓存大小限制，this 上下文丢失。	参数类型复杂，但数量不多，且对性能有一定要求的场景。
带大小限制的 Map 缓存	可以限制缓存大小，防止内存泄漏。	this 上下文丢失，需要维护一个额外的数组 keys，增加了代码复杂度。	需要控制内存占用，参数类型复杂，且对性能有一定要求的场景。
终极版	完美解决了之前版本的所有缺点，灵活性高，可以根据实际需求进行配置，可以自定义 key 生成逻辑和 this 上下文。	实现相对复杂，需要更多代码。	对灵活性和性能都有较高要求的场景，需要自定义 key 生成逻辑或者绑定 this 上下文。
lodash 的 _.memoize	方便快捷，无需自己实现，经过充分测试，稳定可靠。	需要引入额外的库，定制性不如自己实现灵活。	对性能要求不高，不需要自定义 key 生成逻辑或绑定 this 上下文，且已经使用了 lodash 的项目。

六、总结：Memoization，让你的代码飞起来！

Memoization 是一种非常实用的优化技巧，可以有效地减少重复计算，提高程序的性能。掌握 Memoization 的原理和实现方式，可以让你写出更高效、更优雅的代码。

当然，Memoization 并不是银弹，它只适用于特定类型的函数。在实际应用中，需要根据具体情况进行权衡，选择最合适的优化方案。

希望今天的讲座能帮助大家更好地理解和使用 Memoization。记住，代码优化没有止境，不断学习和实践，才能写出更好的代码！ 咱们下期再见！