JS实现缓存函数(记忆函数)

题目

现给定一个函数 fn ，返回该函数的一个 记忆化 版本。

一个 记忆化 的函数是一个函数，它不会被相同的输入调用两次。而是会返回一个缓存的值。

函数 fn 可以是任何函数，对它所接受的值类型没有任何限制。如果两个输入值在 JavaScript 中使用 === 运算符比较时相等，则它们被视为相同。

示例 1

输入： getInputs = () => [[2,2],[2,2],[1,2]] fn = function (a, b) { return a + b; } 输出：[{"val":4,"calls":1},{"val":4,"calls":1},{"val":3,"calls":2}] 解释： const inputs = getInputs(); const memoized = memoize(fn); for (const arr of inputs) { memoized(...arr); }

对于参数为 (2, 2) 的输入: 2 + 2 = 4，需要调用 fn() 。 对于参数为 (2, 2) 的输入: 2 + 2 = 4，这些输入之前已经出现过，因此不需要再次调用 fn()。 对于参数为 (1, 2) 的输入: 1 + 2 = 3，需要再次调用 fn()，总共调用了 2 次。

示例 2

输入： getInputs = () => [[{},{}],[{},{}],[{},{}]] fn = function (a, b) { return a + b; } 输出：[{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}] 解释： 将两个空对象合并总是会得到一个空对象。尽管看起来应该缓存命中并只调用一次 fn()，但是这些空对象彼此之间都不是 === 相等的。

示例 3

输入： getInputs = () => { const o = {}; return [[o,o],[o,o],[o,o]]; } fn = function (a, b) { return ({...a, ...b}); } 输出：[{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}] 解释： 将两个空对象合并总是会得到一个空对象。因为传入的每个对象都是相同的，所以第二个和第三个函数调用都会命中缓存。

题解

分析

要根据函数的入参缓存结果, 就需要将出现过的每一个入参缓存起来

可以将同一个位置的入参放到一个层级进行映射, 下一个位置的入参作为上一个位置入参的value, 直到最后一个参数才会对应函数的返回值

映射最方便的就是对象或者Map, map提供了一些方法让我们很方便的操作其中的对象

每一个入参的类型可以使对象或者原始类型, 需要考虑Map将引用类型作为key时候的GC问题, 但是WeakMap能很好的解决这引用类型的GC问题

因此可以考虑将原类型与引用类型分开, 引用类型用WeakMap, 原始类型用Map

// 字典类
class DictMap {
  map = new Map();
  weakMap = new WeakMap(); // WeakMap-->key不能是原始类型,可避免内存泄漏
  isSave = false; // 是否缓存过值
  value = null; // 缓存的值
  saveVal(val) {
    // 用于将值存储起来
    this.value = val;
    this.isSave = true;
  }
}

// 判断是对象类型
const isObj = (val) =>
  typeof val === "function" || (val !== null && typeof val === "object");

// 记忆函数
function useMemo(fn) {
  const rootMap = new DictMap();
  return function (...args) {
    let dict = rootMap;
    let map;
    // 遍历每一个参数
    for (const item of args) {
      // 根据当前入参类型选择字典存储Map
      map = isObj(item) ? dict.weakMap : dict.map;
      // 若当前参数在这个形参位置上是第一次出现, 则在字典内新增位置
      if (!map.has(item)) map.set(item, new DictMap());
      dict = map.get(item); // 指针向内层移动, 参数遍历完, dict就指向最后一个参数对应的空间
    }
    if (dict.isSave) return dict.value;
    else dict.saveVal(fn(...args));
  };
}