Memoization in JavaScript
栏目: JavaScript · 发布时间: 5年前
内容简介:在一个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);
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
《裂变:秒懂人工智能的基础课》
王天一 / 电子工业出版社·博文视点 / 2018-6-13 / 59.00元
人工智能是指通过普通计算机程序实现的人类智能技术,这一学科不仅具有非凡的科学意义,对人类自身生存方式的影响也在不断加深。本书作为人工智能领域的入门读物,内容围绕人工智能的核心框架展开,具体包括数学基础知识、机器学习算法、人工神经网络原理、深度学习方法与实例、深度学习之外的人工智能和实践应用场景等模块。本书力图为人工智能初学者提供关于这一领域的全面认识,也为进一步的深入研究建立坚实的基础。一起来看看 《《裂变:秒懂人工智能的基础课》》 这本书的介绍吧!