记忆化的递归函数.如何让它们万无一失? [英] Memoized recursive functions. How to make them fool-proof?
问题描述
记忆化函数是记住它们找到的值的函数.如有必要,请在文档中心查看 Mathematica 中有关此内容的一些背景信息.
Memoized functions are functions which remember values they have found. Look in the doc center for some background on this in Mathematica, if necessary.
假设你有以下定义
f[0] = f[1] = 1
f[x_] := f[x] = f[x - 1] + f[x - 2]
在您的一个包裹中.用户可以加载包并立即开始询问 f[1000].这将触发 $RecursionLimit::reclim 错误消息并中止.即使用户随后尝试更小的东西,例如 f[20],现在 f 的定义已损坏,结果不再好.当然,包开发人员可能会增加递归限制并警告用户,但我的问题是:
in one of your packages. A user may load the package and start asking right away f[1000]. This will trigger a $RecursionLimit::reclim error message and abort. Even if the user then tries something smaller, say f[20], by now the definition of f is corrupt and the result is not good anymore.Of course the package developer might increase the recursion limit and warn the user, but my question is:
您如何改进 f 定义,以便如果用户要求 f[1000],他/她可以毫无问题地得到答案?我对捕获用户输入、分析它并采取任何必要步骤来评估 f[1000] 的方法感兴趣.
How can you improve the f definition so that if the user asks for f[1000] he/she gets the answer without any problem? I am interested in a way to trap the user input, analyze it and take whatever steps are necessary to evaluate f[1000].
我可以很容易地想象,如果输入超过 255,人们可以更改递归限制(然后将其恢复到原始级别),但我真正想看到的是,如果有一种方法可以f 找出它知道"多少个值 (fknownvalues) 并接受任何输入 <=fknownvalues+$RecursionLimit 没有问题,或者如果输入更高则增加 $RecursionLimit.
I can easily imagine that one can change the recursion limit if the input is more than 255 (and then bring it back to the original level), but what I would really like to see is, if there is a way for the f to find out how many values it "knows" (fknownvalues) and accept any input <=fknownvalues+$RecursionLimit without problems or increase the $RecursionLimit if the input is higher.
感谢您的帮助
推荐答案
这里的代码假设您可以根据输入参数的值确定 $RecursionLimit
的值:
Here is the code assuming that you can determine a value of $RecursionLimit
from the value of the input argument:
Clear[f];
Module[{ff},
ff[0] = ff[1] = 1;
ff[x_] := ff[x] = ff[x - 1] + ff[x - 2];
f[x_Integer] :=f[x] =
Block[{$RecursionLimit = x + 5},
ff[x]
]]
我使用本地函数 ff
来完成主要工作,而 f
只是调用它包装在 Block
中,并为$RecursionLimit
:
I am using a local function ff
to do the main work, while f
just calls it wrapped in Block
with a proper value for $RecursionLimit
:
In[1552]:= f[1000]
Out[1552]= 7033036771142281582183525487718354977018126983635873274260490508715453711819693357974224
9494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125
598767690091902245245323403501
编辑
如果想更精确的设置$RecursionLimit
,可以将上面的部分代码修改为:
If you want to be more precise with the setting of $RecursionLimit
, you can modify the part of the code above as:
f[x_Integer] :=
f[x] =
Block[{$RecursionLimit = x - Length[DownValues[ff]] + 10},
Print["Current $RecursionLimit: ", $RecursionLimit];
ff[x]]]
Print
语句用于说明.值 10
是相当随意的 - 要获得它的下限,必须计算必要的递归深度,并考虑到已知结果的数量是 Length[DownValues[ff]] - 2
(因为 ff
有 2 个一般定义).下面是一些用法:
The Print
statement is here for illustration. The value 10
is rather arbitrary - to get a lower bound on it, one has to compute the necessary depth of recursion, and take into account that the number of known results is Length[DownValues[ff]] - 2
(since ff
has 2 general definitions). Here is some usage:
In[1567]:= f[500]//Short
During evaluation of In[1567]:= Current $RecursionLimit: 507
Out[1567]//Short= 22559151616193633087251269<<53>>83405015987052796968498626
In[1568]:= f[800]//Short
During evaluation of In[1568]:= Current $RecursionLimit: 308
Out[1568]//Short= 11210238130165701975392213<<116>>44406006693244742562963426
如果您还想限制最大的 $RecursionLimit
可能,这也很容易做到,沿着相同的路线.在这里,例如,我们将它限制为 10000(同样,这在 Module
中):
If you also want to limit the maximal $RecursionLimit
possible, this is also easy to do, along the same lines. Here, for example, we will limit it to 10000 (again, this goes inside Module
):
f::tooLarge =
"The parameter value `1` is too large for single recursive step. \
Try building the result incrementally";
f[x_Integer] :=
With[{reclim = x - Length[DownValues[ff]] + 10},
(f[x] =
Block[{$RecursionLimit = reclim },
Print["Current $RecursionLimit: ", $RecursionLimit];
ff[x]]) /; reclim < 10000];
f[x_Integer] := "" /; Message[f::tooLarge, x]]
例如:
In[1581]:= f[11000]//Short
During evaluation of In[1581]:= f::tooLarge: The parameter value 11000 is too
large for single recursive step. Try building the result incrementally
Out[1581]//Short= f[11000]
In[1582]:=
f[9000];
f[11000]//Short
During evaluation of In[1582]:= Current $RecursionLimit: 9007
During evaluation of In[1582]:= Current $RecursionLimit: 2008
Out[1583]//Short= 5291092912053548874786829<<2248>>91481844337702018068766626
这篇关于记忆化的递归函数.如何让它们万无一失?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!