JavaScript内核与高级编程之：`JavaScript`的`Memoization`：如何实现函数结果的缓存。 - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

各位老铁，早上好！今天咱们聊聊JavaScript里的一个神奇的小技巧，叫做“Memoization”（记忆化）。别害怕这个词，听起来唬人，其实就是给函数加个小本本，记下它算过的答案，下次再问直接查小本本，省得再算一遍。懒人必备，提高效率的利器！

一、啥是Memoization？为啥要用它？

想象一下，你有个特别复杂的数学题，每次都要算半天。如果你够聪明，你会把每次算出来的答案记下来，下次遇到同样的题直接抄答案，对不对？ Memoization就是这个道理。

简单来说，Memoization是一种优化技术，通过缓存函数调用的结果，并在下次使用相同的输入调用函数时返回缓存的结果，从而避免重复计算。

为啥要用它？

提高效率： 对于计算量大的函数，尤其是递归函数，可以显著减少计算时间。
减少资源消耗： 避免重复计算，节省 CPU 和内存资源。
优化用户体验： 让你的网页或应用运行得更快更流畅。

二、Memoization的原理

Memoization的核心在于两点：

缓存： 创建一个数据结构（通常是对象或Map）来存储函数调用的结果。键是函数的输入参数，值是函数的返回值。
查找： 在函数执行之前，先检查缓存中是否存在相同的输入参数。如果存在，直接返回缓存的结果；如果不存在，执行函数，并将结果存入缓存。

三、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 factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

const memoizedFactorial = memoize(factorial);

console.log(memoizedFactorial(5)); // 计算新结果，输出 120
console.log(memoizedFactorial(5)); // 从缓存中获取结果，输出 120
console.log(memoizedFactorial(6)); // 计算新结果，输出 720

代码解释：

memoize(func) 函数接收一个函数 func 作为参数，返回一个“记忆化”后的新函数。
cache 对象用于存储函数的计算结果，键是函数的参数（转换为字符串），值是函数的返回值。
返回的新函数在执行时，先检查 cache 对象中是否存在相同的参数。如果存在，直接返回缓存的结果；如果不存在，执行原始函数 func，并将结果存入 cache 对象。
factorial(n) 是一个计算阶乘的函数。
memoizedFactorial 是 factorial 函数的记忆化版本。

四、使用Map实现Memoization

用对象做缓存有个问题，就是对象的键只能是字符串。如果函数的参数是对象或其他复杂类型，就没法直接用对象做缓存的键了。这时候，可以使用ES6的 Map 对象，Map 对象的键可以是任意类型。

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

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

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

// 例子：计算两个对象的属性和
function sumObjectProperties(obj1, obj2) {
  let sum = 0;
  for (let key in obj1) {
    if (obj1.hasOwnProperty(key) && typeof obj1[key] === 'number') {
      sum += obj1[key];
    }
  }
    for (let key in obj2) {
    if (obj2.hasOwnProperty(key) && typeof obj2[key] === 'number') {
      sum += obj2[key];
    }
  }
  return sum;
}

const memoizedSum = memoizeWithMap(sumObjectProperties);

const obj1 = { a: 1, b: 2 };
const obj2 = { c: 3, d: 4 };

console.log(memoizedSum(obj1, obj2)); // 计算新结果，输出 10
console.log(memoizedSum(obj1, obj2)); // 从Map缓存中获取结果，输出 10

代码解释：

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

五、Memoization的适用场景

Memoization 并非万能的，它只适用于满足以下条件的函数：

纯函数： 函数的返回值只依赖于输入参数，没有副作用（不会修改外部状态）。
计算密集型： 函数的计算成本较高，重复计算会带来明显的性能损失。
相同的输入参数会频繁出现： 如果函数的输入参数很少重复，Memoization 的效果就不明显。

以下是一些适合使用 Memoization 的场景：

递归函数： 例如斐波那契数列、阶乘等。
复杂数学计算： 例如矩阵运算、图像处理等。
网络请求： 如果需要频繁请求相同的数据，可以将请求结果缓存起来。

六、Memoization的注意事项

缓存大小： 缓存会占用内存空间。如果缓存的数据量太大，可能会导致内存溢出。可以使用 LRU (Least Recently Used) 算法等策略来限制缓存的大小。
缓存失效： 缓存的数据可能会过期或失效。需要定期清理缓存，以保证数据的准确性。
参数序列化： 将函数的参数转换为字符串作为缓存的键时，需要注意参数的序列化方式。不同的序列化方式可能会导致相同的参数被识别为不同的键。通常使用 JSON.stringify 进行序列化。
this 上下文： 注意 this 上下文的绑定。在使用 apply 方法调用原始函数时，需要将 this 上下文传递给原始函数。

七、更高级的Memoization技巧

自定义键生成函数：

有时候，直接使用 JSON.stringify 序列化参数可能不够灵活。你可以自定义一个函数，根据参数生成唯一的键。例如，对于对象参数，可以只使用对象的某些属性来生成键。

function memoizeWithCustomKey(func, keyGenerator) {
  const cache = new Map();

  return function(...args) {
    const key = keyGenerator(...args);

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

// 例子：只使用对象的 a 属性生成键
function keyGenerator(obj) {
  return obj.a;
}

function myFunc(obj) {
  console.log("执行 myFunc");
  return obj.a + obj.b;
}

const memoizedMyFunc = memoizeWithCustomKey(myFunc, keyGenerator);

const obj1 = { a: 1, b: 2 };
const obj2 = { a: 1, b: 3 }; // obj1 和 obj2 的 a 属性相同

console.log(memoizedMyFunc(obj1)); // 执行 myFunc，输出 3
console.log(memoizedMyFunc(obj2)); // 从自定义键缓存中获取结果，输出 3

使用 WeakMap：

如果缓存的对象不再被其他地方引用，使用 WeakMap 可以让垃圾回收器自动回收这些对象，避免内存泄漏。 WeakMap 的键只能是对象。

function memoizeWithWeakMap(func) {
  const cache = new WeakMap();

  return function(obj) { // 假设函数只接收一个对象作为参数
    if (cache.has(obj)) {
      console.log("从WeakMap缓存中获取结果");
      return cache.get(obj);
    } else {
      console.log("计算新结果");
      const result = func(obj);
      cache.set(obj, result);
      return result;
    }
  };
}

// 例子：
function processObject(obj) {
  console.log("处理对象");
  return obj.value * 2;
}

const memoizedProcessObject = memoizeWithWeakMap(processObject);

const obj1 = { value: 5 };
const obj2 = { value: 10 };

console.log(memoizedProcessObject(obj1)); // 处理对象，输出 10
console.log(memoizedProcessObject(obj1)); // 从WeakMap缓存中获取结果，输出 10

obj1 = null; // obj1 不再被引用，可以被垃圾回收器回收，WeakMap 中的缓存也会被清除

八、实际案例分析

咱们来分析一个实际的案例，看看 Memoization 在优化递归函数方面的威力。

斐波那契数列：

// 原始的斐波那契数列函数（没有 Memoization）
function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.time("fibonacci");
console.log(fibonacci(40)); // 计算时间很长
console.timeEnd("fibonacci");

// 使用 Memoization 优化的斐波那契数列函数
function memoizeFibonacci() {
  const cache = {};

  function fibonacciMemoized(n) {
    if (n in cache) {
      return cache[n];
    } else {
      if (n <= 1) {
        return n;
      }
      const result = fibonacciMemoized(n - 1) + fibonacciMemoized(n - 2);
      cache[n] = result;
      return result;
    }
  }

  return fibonacciMemoized;
}

const fibonacciMemo = memoizeFibonacci();

console.time("fibonacciMemoized");
console.log(fibonacciMemo(40)); // 计算时间非常短
console.timeEnd("fibonacciMemoized");

分析：

没有 Memoization 的 fibonacci(40) 函数，由于存在大量的重复计算，计算时间非常长。
使用了 Memoization 的 fibonacciMemo(40) 函数，由于缓存了中间结果，避免了重复计算，计算时间大大缩短。

表格总结：

功能	描述
Memoization	一种优化技术，通过缓存函数调用的结果，并在下次使用相同的输入调用函数时返回缓存的结果，从而避免重复计算。
适用场景	纯函数、计算密集型、相同的输入参数会频繁出现。
实现方式	使用对象或 Map 对象作为缓存，键是函数的输入参数，值是函数的返回值。
注意事项	缓存大小、缓存失效、参数序列化、this 上下文。
优点	提高效率，减少资源消耗，优化用户体验。
缺点	需要占用内存空间，可能导致内存泄漏，只适用于特定类型的函数。
进阶技巧	自定义键生成函数，使用 WeakMap。
核心思想	用空间换时间。

九、总结

Memoization 是一个简单而强大的优化技巧，可以显著提高 JavaScript 代码的性能。掌握 Memoization 的原理和使用方法，可以让你写出更高效、更优雅的代码。记住，懒人改变世界，用 Memoization 让你的代码更懒，运行更快！

今天的讲座就到这里，各位老铁，下次再见！

发表回复 取消回复

发表回复取消回复