Memoization-in-JavaScript

1. 基本概念

在一个 CPU 密集型应用中，我们可以使用 Memoization 来进行优化，其主要用于通过存储昂贵的函数调用的结果来加速程序，并在再次发生相同的输入时返回缓存的结果。
例如一个简单的求平方根的函数：

const sqrt = Math.sqrt;
// 使用 cache 缓存
const sqrt =（arg）=>{if(!sqrt.cache){sqrt.cache = {};
    }
    if(!sqrt.cache[arg]){sqrt.cache[arg] = Math.sqrt(arg)
    }
    return sqrt.cache[arg]
}
// 简单的运行时间对比
// 第一次运行：console.time('start1')
sqrt(779)
console.timeEnd('start1')
VM516:3 start1: 0.01806640625ms
// 第二次运行：console.time('start1')
sqrt(779)
console.timeEnd('start1')
VM521:3 start1: 0.005859375ms

2. 简单通用实现

我们实现一个通用的 memoize 函数，用它来包装任意纯函数，并缓存其计算结果。

function memoize(fn){return function(){var args = Array.prototype.slice.call(arguments);
            fn.cache = fn.cache || {};
            return fn.cache[args] ?
                 fn.cache[args] :(fn.cache[args] = fn.apply(this,args))
        }
}

必须注意的是，memoize 的原理是在发生相同的输入时返回缓存的结果，这意味着其包装的函数应当是一个纯函数，当函数不纯时，相同的输入在不同时间可能返回不同的结果，此时再使用 memoize 明显不合时宜。

3. 常见的 memoize 库

3.1 lodash 库中的 memoize

在该库中，使用 Map 缓存计算结果，支持传入 resolver 函数将传入的参数转换为存入 Map 的键名（默认键名是第一个参数，当键名是引用类型时，引用不变，缓存不会更新）。

function memoize(func, resolver) {if (typeof func != 'function' || (resolver != null && typeof resolver != 'function')) {throw new TypeError('Expected a function')
  }
  const memoized = function(...args) {const key = resolver ? resolver.apply(this, args) : args[0]
    const cache = memoized.cache

    if (cache.has(key)) {return cache.get(key)
    }
    const result = func.apply(this, args)
    memoized.cache = cache.set(key, result) || cache
    return result
  }
  memoized.cache = new (memoize.Cache || Map)
  return memoized
}

memoize.Cache = Map

3.2 memoize-one

与 lodash 不同，memoize-one 仅仅保存上一次调用时的结果，如果下次参数变化，则更新缓存。因此不必担心由于 maxAge, maxSize, exclusions 等导致的内存泄漏。

// 源码
export default function<ResultFn: (...any[]) => mixed>(
  resultFn: ResultFn,
  isEqual?: EqualityFn = areInputsEqual,
): ResultFn {
  let lastThis: mixed;
  let lastArgs: mixed[] = [];
  let lastResult: mixed;
  let calledOnce: boolean = false;
// 函数调用过，this 没有变化，参数 isEqual 时返回缓存值。const result = function(...newArgs: mixed[]) {if (calledOnce && lastThis === this && isEqual(newArgs, lastArgs)) {return lastResult;}
    lastResult = resultFn.apply(this, newArgs);
    calledOnce = true;
    lastThis = this;
    lastArgs = newArgs;
    return lastResult;
  };

  return (result: any);
}

可以看到，可以通过第二个参数自定义参数是否相同，默认是 areInputsEqual 函数。

//areInputsEqual 实现
export default function areInputsEqual(newInputs: mixed[],
  lastInputs: mixed[],) {
// 先进行参数长度比较
  if (newInputs.length !== lastInputs.length) {return false;}
 // 参数浅比较
  for (let i = 0; i < newInputs.length; i++) {if (newInputs[i] !== lastInputs[i]) {return false;}
  }
  return true;
}

可以自定义参数比较函数进行深比较

import memoizeOne from 'memoize-one';
import isDeepEqual from 'lodash.isequal';

const identity = x => x;

const shallowMemoized = memoizeOne(identity);
const deepMemoized = memoizeOne(identity, isDeepEqual);

const result1 = shallowMemoized({foo: 'bar'});
const result2 = shallowMemoized({foo: 'bar'});

result1 === result2; // false - difference reference

const result3 = deepMemoized({foo: 'bar'});
const result4 = deepMemoized({foo: 'bar'});

result3 === result4; // true - arguments are deep equal

4. memoize-one 在 React 中的应用

在 React 中有这样一个应用场景，当部分 props 变化需要改变派生 state 时，可以在 getDerivedStateFromProps 中通过 if 判断是否需要重新计算，但它比它需要的更复杂，因为它必须单独跟踪和检测每个 props 和 state 的变化，当 props 很多时，这种判断方式会变得纠缠不清。

class Example extends Component {
  state = {filterText: "",};
  static getDerivedStateFromProps(props, state) {
    if (
      props.list !== state.prevPropsList ||
      state.prevFilterText !== state.filterText
    ) {
      return {
        prevPropsList: props.list,
        prevFilterText: state.filterText,
        filteredList: props.list.filter(item => item.text.includes(state.filterText))
      };
    }
    return null;
  }
  handleChange = event => {this.setState({ filterText: event.target.value});
  };
  render() {
    return (
      <Fragment>
        <input onChange={this.handleChange} value={this.state.filterText} />
        <ul>{this.state.filteredList.map(item => <li key={item.id}>{item.text}</li>)}</ul>
      </Fragment>
    );
  }
}

而通过 Memoization，可以把上一次的计算结果保存下来，而避免重复计算。例如以下通过 memoize-one 库实现的记忆，可以让我们不用手动判断 list, filterText 是否变化，是否需要重新计算。

import memoize from "memoize-one";
class Example extends Component {
  // State only needs to hold the current filter text value:
  state = {filterText: ""};
  // Re-run the filter whenever the list array or filter text changes:
  filter = memoize((list, filterText) => list.filter(item => item.text.includes(filterText))
  );

  handleChange = event => {this.setState({ filterText: event.target.value});
  };

  render() {const filteredList = this.filter(this.props.list, this.state.filterText);
    return (
      <Fragment>
        <input onChange={this.handleChange} value={this.state.filterText} />
        <ul>{filteredList.map(item => <li key={item.id}>{item.text}</li>)}</ul>
      </Fragment>
    );
  }
}

5. 配合 Redux 使用的 memoize 库——reselect

在 react 中，每当组件重新渲染，计算派生状态的逻辑就会执行一遍（不管这些逻辑是放在 render 或者是放在 getDerivedStateFromProps 中，如果没有采用很多 if 限制的话）。上节介绍了使用 memoize-one 来缓存来避免重复计算，当我们使用 redux 时，通常在 mapStateToProps 中计算派生状态，每当 store 中的任意 state 更新时，都会触发 mapStateToProps 中的计算，然而，往往派生 state 通常只依赖部分 state，不必每次都计算。
Reselect 是一个十分贴近 redux 的 memoize 库，其和 memoize-one 一样只缓存前一次的计算值，并支持自定义 memoize 函数，自定义参数比较函数等；其输入参数由 inputSelectors functions 产生，生成的的依然是 inputSelectors functions，这意味的与 memoize 相比，这可以很容易的组合。
另外，mapStateProps 的第二个参数 ownProps 也可以传入 selector 中。

import {createSelector} from 'reselect'

fSelector = createSelector(
    a => state.a,
    b => state.b,
    (a, b) => f(a, b)
)
hSelector = createSelector(
    b => state.b,
    c => state.c,
    (b, c) => h(b, c)
)
gSelector =  createSelector(
    a => state.a,
    c => state.c,
    (a, c) => g(a, c)
)
uSelector = createSelector(
    a => state.a,
    b => state.b,
    c => state.c,
    (a, b, c) => u(a, b, c)
)

...
function mapStateToProps(state) {const { a, b, c} = state
    return {
        a,
        b,
        c,
        fab: fSelector(state),
        hbc: hSelector(state),
        gac: gSelector(state),
        uabc: uSelector(state)
    }
}

6. react 中 memoize 原生支持——React.memo

如果你的函数组件在给定相同的 props 的情况下呈现相同的结果，你可以 React.memo 通过记忆结果将它包装在一些调用中以提高性能。这意味着 React 将跳过渲染组件，并重用最后渲染的结果。

默认情况下，它只会浅显比较 props 对象中的复杂对象。如果要控制比较，还可以提供自定义比较函数作为第二个参数。

function MyComponent(props) {/* render using props */}
function areEqual(prevProps, nextProps) {
  /*
  return true if passing nextProps to render would return
  the same result as passing prevProps to render,
  otherwise return false
  */
}
export default React.memo(MyComponent, areEqual);

You Probably Don’t Need Derived State – React Blog
Understanding Memoization in JavaScript to Improve Performance
性能优化：memoization | Taobao FED | 淘宝前端团队
lodash/memoize.js at master · lodash/lodash · GitHub
GitHub – alexreardon/memoize-one: A memoization library which only remembers the latest invocation
为什么我们需要 reselect – 从 0 开始实现 react 技术栈 – SegmentFault 思否
React Hooks: Memoization – Sandro Dolidze – Medium