Mathematica中的动态编程：如何自动定位和/或清除记忆函数的定义 [英] Dynamic Programming in Mathematica: how to automatically localize and / or clear memoized function's definitions

问题描述

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

In Mathematica 8.0, suppose I have some constants:

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

，我想用它们来评估一些相互关联的函数

and I want to use them to evaluate some interlinked functions

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

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

But this is really slow and in need of dynamic programming, or else you get an exponential slowdown:

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函数中使用它），我们必须清除 g 和 h 。如果我们有复杂的相互依赖关系，那么每次我们想要从 g 和 h 。

Now it's really fast, but if we ever want to change the constants(say, to use this in a Manipulate function) we have to Clear g and h each time. If we had complex interdependencies, it might be really annoying to clear them all out every single time we wanted a value from g and h.

是否有一种简单的方法来运行 g 和 h 在 Module 或 Block 或类似的模块中，这样，每次进行评估时，我都可以获得新的结果，而无需指数放缓？甚至是一种很好的方式为 g 和 h 建立结果表的快速方法？如前所述，我希望能够通过 Manipulate g 和 h 来计算函数。

Is there an easy way to run g and h in a Module or Block or similar, so that I can get a fresh result back each time it's evaluated without the exponential slowdown? Or even a fast way to build up a table of results for both g and h in a nice way? As said, I want to be able to compute g and h in a Manipulate function.

推荐答案

这是使用 Block 根据您的要求：

Here is one way, using Block as you requested:

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.}

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

There are no global memoized definitions left after each call - Block takes care to destroy them just before the execution exits Block. In particular, here I will change the parameters and call them again:

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 传递给函数，扩展其形式参数列表（签名），但这具有较旧的记忆定义的缺点对应于过去不同参数值的值不会自动清除。这种方法的另一个问题是，生成的代码将更加脆弱，参数数量将发生变化，等等。

An alternative to this scheme would be to explicitly pass all parameters like a,b,c,d,e,f to functions, extending their formal parameter lists (signatures), but this has a disadvantage that the older memoized definitions corresponding to different past parameter values would not be automatically cleared. Another problem with that approach is that the resulting code will be more fragile, w.r.t changes in the number of parameters, etc.

EDIT

但是，如果您想建立一个结果表，这可能会更快一些，因为您可以一劳永逸地做到，在这种情况下，您可以做希望保留所有记忆的定义。因此，下面是代码：

However, if you want to build a table of results, this could be somewhat faster since you do it once and for all, and in this case you do want to keep all memoized definitions. So, here is the code:

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;

您调用它，并显式传递参数：

You call it, passing the parameters explicitly:

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

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

(I was using the original parameters). You can check that the memoized definitions remain in the global rule base, in this method. Next time you call a function with exact same parameters, it will fetch the memoized definition rather than recompute. Apart from the problems with this approach that I outlined above, you should also watch for the memory usage, since nothing gets cleared.

这篇关于Mathematica中的动态编程：如何自动定位和/或清除记忆函数的定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！