recursion - Mathematica中的动态编程: how to automatically localize and/or clear memoized function's definitions

Question

在Mathematica 8.0中，假设我有一些常数:

a:=7
b:=9
c:=13
d:=.002
e:=2
f:=1

我想用它们来评估一些相互关联的功能

g[0,k_]:=0
g[t_,0]:=e
g[t_,k_]:=g[t-1,k]*a+h[t-1,k-1]*b

h[0,k_]:=0
h[t_,0]:=f
h[t_,k_]:=h[t-1,k]*c+g[t-1,k-1]*d

但这确实很慢，并且需要动态编程，否则您将得到指数级的减速:

g[0, k_] := 0
g[t_, 0] := e
g[t_, k_] := g[t, k] = g[t - 1, k]*a + h[t - 1, k - 1]*b

h[0, k_] := 0
h[t_, 0] := f
h[t_, k_] := h[t, k] = h[t - 1, k]*c + g[t - 1, k - 1]*d

现在确实非常快，但是如果我们想更改常量(例如，要在Manipulate函数中使用它)，则每次都必须 Clear g和 h。如果我们有复杂的相互依赖关系，那么每次我们都想从 g和 h中获取一个值时，将它们全部清除可能会很烦人。

是否有一种简单的方法可以在 g或 h或类似格式中运行 Module和 Block，以便每次评估时都能得到新的结果，而不会出现指数减慢？还是以一种不错的方式为 g和 h建立结果表的快速方法？如前所述，我希望能够在 g函数中计算 h和 Manipulate。

Answer 1

这是一种按照您的要求使用Block的方法:

ClearAll[defWrap];
SetAttributes[defWrap, HoldFirst];
defWrap[fcall_] :=
  Block[{g, h},
     (* Same defintions with memoization as you had, but within Block*)

     g[0, k_] := 0;
     g[t_, 0] := e;
     g[t_, k_] := g[t, k] = g[t - 1, k]*a + h[t - 1, k - 1]*b;   
     h[0, k_] := 0;
     h[t_, 0] := f;
     h[t_, k_] := h[t, k] = h[t - 1, k]*c + g[t - 1, k - 1]*d;

     (* Our function call, but within a dynamic scope of Block *)
     fcall];

我们将使用它为 f和 h给出定义，如下所示:

ClearAll[g, h];
g[tt_, kk_] := defWrap[g[tt, kk]];
h[tt_, kk_] := defWrap[h[tt, kk]];

我们现在调用:

In[1246]:= g[20,10]//Timing
Out[1246]= {0.,253809.}

In[1247]:= h[20,10]//Timing
Out[1247]= {6.50868*10^-15,126904.}

在每次调用之后，就没有全局记录的定义了- Block会在执行退出 Block之前小心地销毁它们。特别是在这里，我将更改参数并再次调用它们:

In[1271]:= 
a:=1
b:=2
c:=3
d:=.01
e:=4
f:=5

In[1279]:= g[20,10]//Timing
Out[1279]= {0.015,0.808192}

In[1280]:= h[20,10]//Timing
Out[1280]= {0.,1.01024}

此方案的替代方法是将所有参数(如 a,b,c,d,e,f)显式传递给函数，以扩展其正式参数列表(签名)，但是这样做的缺点是，不会自动清除与不同的过去参数值相对应的较旧的备注定义。这种方法的另一个问题是，生成的代码将更加脆弱，如果不更改参数数量，等等。

编辑

但是，如果您要建立一个结果表，这可能会更快一些，因为您要一劳永逸地这样做，在这种情况下，您确实希望保留所有记录的定义。所以，这是代码:

ClearAll[g, h];
g[0, k_, _] := 0;
g[t_, 0, {a_, b_, c_, d_, e_, f_}] := e;
g[t_, k_, {a_, b_, c_, d_, e_, f_}] := 
     g[t, k, {a, b, c, d, e, f}] = 
        g[t - 1, k, {a, b, c, d, e, f}]*a +  h[t - 1, k - 1, {a, b, c, d, e, f}]*b;

h[0, k_, _] := 0;
h[t_, 0, {a_, b_, c_, d_, e_, f_}] := f;
h[t_, k_, {a_, b_, c_, d_, e_, f_}] := 
     h[t, k, {a, b, c, d, e, f}] = 
        h[t - 1, k, {a, b, c, d, e, f}]*c +  g[t - 1, k - 1, {a, b, c, d, e, f}]*d;

您调用它，显式传递参数:

In[1317]:= g[20,10,{a,b,c,d,e,f}]//Timing
Out[1317]= {0.,253809.}

(我使用的是原始参数)。您可以使用此方法检查记住的定义是否保留在全局规则库中。下次调用具有完全相同参数的函数时，它将获取已内存的定义，而不是重新计算。除了上面概述的这种方法存在的问题外，您还应该注意内存使用情况，因为没有清除任何东西。