未加星标

从斐波那契数列求值优化谈 _.memoize 方法

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二04 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏

斐波那契数列 应该都很熟悉,如何能够快速求得斐波那契数列中某项的值呢?

一个很显然的方法是正向地叠加求解:

"use strict"; const N = 1000; let fibonacciNumber = []; for (let i = 0; i < 1000; i++) { if (i < 2) fibonacciNumber[i] = i; else fibonacciNumber[i] = fibonacciNumber[i - 2] + fibonacciNumber[i - 1]; }

这样做有个「预处理」的过程,我们不知道需要预处理多大的数据,这就比较棘手,如果能给个数据范围,这无疑是最高效又简便的方法。

接着我们考虑每次独立求解(非严格模式下,函数内的 fibonacci 也能用 arguments.callee 来代替):

function fibonacci(n) { return n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1); }

很经典的递归,但是这样做出现了大量重复递归运算。我们可以缓存中间运算结果,大大提高效率,有点「记忆化」的意思:

"use strict"; let fibonacci = function() { // 缓存过程中计算结果 let cache = {}; return function(n) { // 没有被计算过 if (!cache[n]) cache[n] = n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1); return cache[n]; } }();

我们可以将 memoize 函数封装起来:

"use strict"; let memoize = function(func) { let cache = {}; return function(key) { if (!cache[key]) cache[key] = func.apply(this, arguments); return cache[key]; } } let fibonacci = memoize(function(n) { return n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1); });

与最开始的递归版相比,只是外面包了个 memoize 方法而已,使得整个 func 的计算能保存中间已经计算过的值。

最后我们来看看 underscore 对其的实现:

// Memoize an expensive function by storing its results. //「记忆化」,存储中间运算结果,提高效率 // 参数 hasher 是个 function,用来计算 key // 如果传入了 hasher,则用 hasher 来计算 key // 否则用 key 参数直接当 key(即 memoize 方法传入的第一个参数) // _.memoize(function, [hashFunction]) // 适用于需要大量重复求值的场景 // 比如递归求解菲波那切数 // @http://www.jameskrob.com/memoize.html // create hash for storing "expensive" function outputs // run expensive function // check whether function has already been run with given arguments via hash lookup // if false - run function, and store output in hash // if true, return output stored in hash _.memoize = function(func, hasher) { var memoize = function(key) { // 储存变量,方便使用 var cache = memoize.cache; // 求 key // 如果传入了 hasher,则用 hasher 函数来计算 key // 否则用 参数 key(即 memoize 方法传入的第一个参数)当 key var address = '' + (hasher ? hasher.apply(this, arguments) : key); // 如果这个 key 还没被 hash 过(还没求过值) if (!_.has(cache, address)) cache[address] = func.apply(this, arguments); // 返回 return cache[address]; }; // cache 对象被当做 key-value 键值对缓存中间运算结果 memoize.cache = {}; // 返回一个函数(经典闭包) return memoize; };

实现原理和 memoize 差不多,underscore 将缓存中间结果的 cache 对象绑在了闭包返回的函数上(当做函数的属性),同时增加了一个 hasher 函数选项,如果函数有好几个参数,那么我们可以传入这个 hasher 函数来计算 key 值,从而来 hash。

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

主题: 数据变量
分页:12
转载请注明
本文标题:从斐波那契数列求值优化谈 _.memoize 方法
本站链接:http://www.codesec.net/view/482869.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(24)