动态规划之使用备忘录来改进Javascript函数

第动态规划之使用备忘录来改进Javascript函数目录什么是备忘录备忘录的概念1.引用透明2.查找表比较函数使用备忘录和不用备忘录解决方法是记录调用函数的返回结果备忘录的意义结论：什么是备忘录前言;

动态规划已出现了十多年。根据维基百科，它既是一种数学优化方法，也是一种计算机编程方法。一个问题要真正应用动态规划，必须具有两个关键属性：最优结构和重叠子结构。本文不会细讲动态规划，而是将关注重叠子结构如何成为动态规划的关键属性之一。由于这关系到接下来的存储解决方案问题，所以对它的讨论非常重要。

本文将介绍什么是备忘录，备忘录对Javascript开发人员来说具有哪些价值，以及如何使用它来改进Javascript函数，从而对备忘录本身以及备忘录对优化应用程序的意义有一个深入了解。

在本文中，我们将讨论以下几个主题：

什么是备忘录备忘录的主要概念函数使用备忘录和不用备忘录的比较备忘录的意义

什么是备忘录

备忘录是缓存的一种形式，是一种方便进入和后续使用的值存储方法。备忘录是将已解决问题的结果记录下来，这样下次需要再次执行相同操作时，就不必重新计算了。不过，一个函数要使用备忘录，需要满足一定条件：它必须是引用透明的，即只有在调用函数的效果与用函数的返回值替换函数调用的效果完全相同的情况下才可以使用。

在Ruby、C++、Python等大多数编程语言中都有备忘录，这些语言中甚至有很多库可以简化。在本文中，我们将重点关注Javascript。编程语言或许不同，但其中的概念和思想是一致的。

备忘录的概念

备忘录需要理解以下两个概念：

1.引用透明

如果一个表达式可以在不改变程序行为的情况下被其对应的值替换(反之亦然)，那么它就被称为引用透明。这要求表达式必须是纯的，即对于相同的输入，表达式的值必须相同，并且它的求值必须没有副作用。非引用透明的表达式称为引用不透明。

有了上面的解释，我们可以很快地把它和备忘录的行为联系起来，这个概念让我们可以写出一个带备忘录的函数。

2.查找表

查找表(LUT)是一个数组，它用更为简单的数组索引操作取代运行时计算。该过程被称为直接寻址，LUT与哈希表的不同之处在于它检索的是一个值。

比较函数使用备忘录和不用备忘录

以经典的斐波那契数列定义为例：

function

Fibo(n)

{

if

(n

2)

{

return

n;

}

return

Fibo(n

-

1)

+

Fibo(n

-

2);

}

你可能预料到了，一旦开始使用大于20的数字，这个过程就会变得非常缓慢。而当你处理35左右的数字时，计算机估计也撑不住了。

解决方法是记录调用函数的返回结果

var

IterMemoFib

=

function()

{

var

cache

=

[1,

1];

var

fib

=

function(n)

{

if

(n

=

cache.length)

{

for

(var

i

=

cache.length;

i

i++)

{

cache[i]

=

cache[i

-

2]

+

cache[i

-

1];

}

}

return

cache[n];

}

return

fib;

}();

这部分有点麻烦，也不完全可读，或者你也可以让计算机来协助完成：

Fib

=

Fib.memoize();

由于技术(浏览器安全策略)限制，备忘录函数的参数只能是数组或标量值，不能是对象。

下面的代码扩展了Function对象以添加备忘录功能。如果函数是一个方法，则可以将对象传递给memoize()。

Ftotype.memoize

=

function

()

{

var

pad

=

{};

var

self

=

this;

var

obj

=

arguments.length

0

arguments[i]

:

null;

var

memoizedFn

=

function

()

{

//

Copy

the

arguments

object

into

an

array:

allows

it

to

be

used

as

//

a

cache

key.

var

args

=

[];

for

(var

i

=

0;

i

arguments.length;

i++)

{

args[i]

=

arguments[i];

}

//

Evaluate

the

memoized

function

if

it

hasn't

been

evaluated

with

//

these

arguments

before.

if

(!(args

in

pad))

{

pad[args]

=

self.apply(obj,

arguments);

}

return

pad[args];

memoizedFn.unmemoize

=

function

()

{

return

self;

};

return

memoizedFn;

Ftotype.unmemoize

=

function

()

{

alert("Attempt

to

unmemoize

an

unmemoized

function.");

return

null;

};

备忘录的意义

记住与某组特定输入相对应的结果备忘录降低了函数的时间成本以换取空间成本备忘录更不