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

斐波那契数列 应该都很熟悉,如何能够快速求得斐波那契数列中某项的值呢? 一个很显然的方法是正向地叠加求解: "use s

斐波那契数列

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

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

"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。

未登录用户
全部评论0
到底啦