Memoization in JavaScript

栏目: JavaScript · 发布时间: 4年前

内容简介:在一个CPU密集型应用中,我们可以使用Memoization来进行优化,其主要用于通过存储昂贵的函数调用的结果来加速程序,并在再次发生相同的输入时返回缓存的结果。例如一个简单的求平方根的函数:我们实现一个通用的memoize函数,用它来包装任意纯函数,并缓存其计算结果。

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

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Web Designer's Idea Book

The Web Designer's Idea Book

Patrick Mcneil / How / 2008-10-6 / USD 25.00

The Web Designer's Idea Book includes more than 700 websites arranged thematically, so you can find inspiration for layout, color, style and more. Author Patrick McNeil has cataloged more than 5,000 s......一起来看看 《The Web Designer's Idea Book》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具