f[0] = 0;
f[1] = 1;
f[x_] := f[x-1] + f[x-2]
这个函数在 Mathematica 中运行缓慢,我需要提高速度。我必须使用函数式编程和递归。我不确定为什么它运行得这么慢,即使是最轻微的想法如何改进它也会有所帮助。
f[0] = 0;
f[1] = 1;
f[x_] := f[x-1] + f[x-2]
这个函数在 Mathematica 中运行缓慢,我需要提高速度。我必须使用函数式编程和递归。我不确定为什么它运行得这么慢,即使是最轻微的想法如何改进它也会有所帮助。
编写更快的递归函数的一个好方法是让它记住以前的值。当然,这确实是以内存为代价的,但在这种情况下它会有所帮助。为了计算f[x]
,你计算- 然后计算f[x-1]
,你再计算;您最终会多次重新计算很多值。(原谅我的不精确!)f[x-2]
f[x-1]
f[x-2]
要随时随地存储东西,您可以使用以下成语:
f[x_] := ( f[x] = (* calculation of f[x] goes here *) )
编辑:我在这台机器上没有mathematica,但我很确定这不可能计算出错误的值。
f[0] = 0;
f[1] = 1;
f[x_] := ( f[x] = f[x-1] + f[x-2] );
f[256]
就像我在下面的评论中所说的那样,如果您对 有其他定义f
,您可能想先用Clear[f]
.
感谢 rcollyer:小心$RecursionLimit
!它默认为 256。(当然,这是有充分理由的。真正的深度递归通常是个坏主意。)
杰弗罗米是对的。看看维基百科上的记忆。他们使用阶乘的例子以及如何通过记忆化来加速它。
记忆 是编写更快的递归函数的好方法。但是,在这种情况下,有一个递归替代方案,它的运行速度比原始函数快得多,而且不需要记忆。
关键观察是看到原始定义执行了很多冗余计算。考虑如果我们计算会发生什么fib[4]
:
fib[4] = fib[3] + fib[2]
fib[3] = fib[2] + fib[1]
fib[2] = fib[1] + fib[0]
fib[1] = 1
fib[0] = 1
∴ fib[2] = 1 + 1 = 2
fib[1] = 1
∴ fib[3] = 2 + 1 = 3
fib[2] = fib[1] + fib[0]
fib[1] = 1
fib[0] = 1
∴ fib[2] = 1 + 1 = 2
∴ fib[4] = 2 + 1 = 3
在这个过程中,fib[2]
每次fib[0]
计算两次,fib[1]
三次计算。对于更大的计算,浪费会急剧增加——事实上是指数级的。
如果要手动计算相同的斐波那契数,可能会进行如下操作:
0: given 0
1: given 1
2: 0 + 1 = 1
3: 1 + 1 = 2
4: 1 + 2 = 3
没有多余的计算。在任何给定点,只需要考虑前两个结果。后一种方法可以递归地表示为:
fib2[0] = 0;
fib2[n_] :=
Module[{f},
f[n, p1_, _] := p1;
f[x_, p1_, p2_] := f[x + 1, p1 + p2, p1];
f[1, 1, 0]
]
Block[{$IterationLimit = Infinity}, fib2[100000]]
毫无疑问,这个表格不像原来的那样容易阅读。另一方面,原始函数fib[35]
在我的机器上计算需要 35 秒,而修改后的函数的运行时间报告为零。此外,修改后的函数计算fib2[100000]
时间为 0.281 秒,不需要任何额外的记忆存储。 fib[100000]
原始功能完全超出了范围,并且记忆化的版本使 我的 Mathematica 7.01 内核崩溃了——也许记忆化的规则太多了?
请注意,默认情况下,Mathematica 将迭代一个函数不超过 4096 次。要提高该限制,您必须分配更高的值,$IterationLimit
如上例所示。
当然,在 Mathematica 中,有很多非递归方法可以计算斐波那契数,包括内置Fibonacci
函数。但这不是本练习的重点。
总是希望使用尾调用来表达递归函数。这允许通过简单的迭代来执行递归,而无需在堆栈上保留中间结果的开销。 fib2
是尾递归的。一些语言,如 Scheme,要求尾调用优化。其他语言,如Java,可以支持它但不支持(或不会,如Python的情况)。
在 Mathematica 的情况下,尚不清楚尾调用优化的执行程度。有关这一点的进一步讨论,请参阅另一个 SO question。