当前位置： 文江博客话题详情

Mathematica 中的动态编程：如何自动本地化和/或清除记忆函数的定义

发布于 2024-12-03 12:02:10 字数 962 浏览 5 评论 0原文

在 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 中获取值时，将它们全部清除可能真的很烦人。

有没有一种简单的方法可以在 Module 或 Block 或类似内容中运行 g 和 h ，以便我可以每次评估时都能得到新的结果，而不会出现指数级减速？或者甚至是一种以良好的方式快速构建 g 和 h 结果表的方法？如前所述，我希望能够在 Manipulate 函数中计算 g 和 h 。

原文

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

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.

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.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（2）

趁微风不噪 2024-12-10 12:02:10

这是一种方法，根据您的要求使用 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.}

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

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];

We will use this to give definitions to f and h as

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

We call now:

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}

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.

回复 原文
街道布景 2024-12-10 12:02:10

使用辅助符号进行记忆

可以修改问题中展示的记忆技术，以便不需要重新定义 g 和 h 。每当需要清除缓存时就建立。这个想法是将记忆值存储在辅助符号上，而不是直接存储在 g 和 h 上：

g[0,k_] = 0;
g[t_,0] = e;
g[t_,k_] := memo[g, t, k] /. _memo :> (memo[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_] := memo[h, t, k] /. _memo :> (memo[h, t, k] = h[t-1,k]*c+g[t-1,k-1]*d)

定义本质上与 g 的原始记忆版本相同 和 h 不同之处在于引入了新符号 memo。完成这些定义后，只需使用 Clear@memo 即可清除缓存 - 无需重新定义 g 和 h。更好的是，可以通过将 memo 放置在 Block 中来本地化缓存，从而：

Block[{memo, a = 7, b = 9, c = 13, d = 0.002, e = 2, f = 1}
, Table[g[t, k], {t, 0, 100}, {k, 0, 100}]
]

退出该块时，缓存将被丢弃。

使用建议进行记忆化

原始和修订后的记忆化技术需要对函数g和h进行侵入性更改。有时，事后引入记忆是很方便的。做到这一点的一种方法是使用建议技术——一种类似于 OO 编程中的子类化的函数式编程。 函数建议的特定实现定期出现在StackOverflow 页面。然而，该技术也是侵入性的。让我们考虑另一种技术，在不改变全局定义的情况下向 g 和 h 添加建议。

诀窍是在 Block 中临时重新定义 g 和 h。重新定义将首先检查缓存中的结果，如果失败，则从块外部调用原始定义。让我们回到 g 和 h 的原始定义，它们完全不知道记忆化：

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

该技术的基本架构如下所示：

Module[{gg, hh}
, copyDownValues[g, gg]
; copyDownValues[h, hh]
; Block[{g, h}
  , m:g[a___] := m = gg[a]
  ; m:h[a___] := m = hh[a]
  ; (* ... do something with g and h ... *)
  ]
]

临时符号 gg<引入 /code> 和 hh 来保存 g 和 h 的原始定义。然后，g 和 h 在本地反弹到新的缓存定义，并根据需要委托给原始定义。以下是 copyDownValues 的定义：

ClearAll@copyDownValues
copyDownValues[from_Symbol, to_Symbol] :=
  DownValues[to] =
    Replace[
      DownValues[from]
    , (Verbatim[HoldPattern][from[a___]] :> d_) :> (HoldPattern[to[a]] :> d)
    , {1}
    ]

为了使这篇文章简短（呃），此“复制”功能仅涉及向下值。一般建议工具还需要考虑上值、下值、符号属性等。

这种通用模式很容易实现自动化，尽管很乏味。下面的宏函数 memoize 可以做到这一点，但几乎没有任何注释：

ClearAll@memoize
SetAttributes[memoize, HoldRest]
memoize[symbols:{_Symbol..}, body_] :=
  Module[{pairs, copy, define, cdv, sd, s, m, a}
  , pairs = Rule[#, Unique[#, Temporary]]& /@ symbols
  ; copy = pairs /. (f_ -> t_) :> cdv[f, t]
  ; define = pairs /. (f_ -> t_) :> (m: f[a___]) ~sd~ (m ~s~ t[a])
  ; With[{ temps = pairs[[All, 2]]
         , setup1 = Sequence @@ copy
         , setup2 = Sequence @@ define }
    , Hold[Module[temps, setup1; Block[symbols, setup2; body]]] /.
        { cdv -> copyDownValues, s -> Set, sd -> SetDelayed }
    ] // ReleaseHold
  ]

费了一番周折，我们现在可以对 g 的非缓存版本进行外部记忆化，并且h：

memoize[{g, h}
, Block[{a = 7, b = 9, c = 13, d = .002, e = 2, f = 1}
  , Table[g[t, k], {t, 0, 100}, {k, 0, 100}]
  ]
]

将它们放在一起，我们现在可以创建一个响应式 Manipulate 块：

Manipulate[
  memoize[{g, h}
  , Table[g[t, k], {t, 0, tMax}, {k, 0, kMax}] //
      ListPlot3D[#, InterpolationOrder -> 0, PlotRange -> All, Mesh -> None] &
  ]
, {{tMax, 10}, 5, 25}
, {{kMax, 10}, 5, 25}
, {{a, 7}, 0, 20}
, {{b, 9}, 0, 20}
, {{c, 13}, 0, 20}
, {{d, 0.002}, 0, 20}
, {{e, 2}, 0, 20}
, {{f, 1}, 0, 20}
, LocalizeVariables -> False
, TrackedSymbols -> All
]

“操作屏幕截图”

LocalizeVariables 和 TrackedSymbols 选项是 g 和 h 对全局符号 的依赖关系的产物a 到 f。

Memoization Using Auxiliary Symbol

The memoization technique exhibited in the question can be modified so that the definitions of g and h do not need to be re-established whenever the cache needs to be cleared. The idea is to store the memoized values on an auxiliary symbol instead of directly on g and h:

g[0,k_] = 0;
g[t_,0] = e;
g[t_,k_] := memo[g, t, k] /. _memo :> (memo[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_] := memo[h, t, k] /. _memo :> (memo[h, t, k] = h[t-1,k]*c+g[t-1,k-1]*d)

The definitions are essentially the same as the original memoized versions of g and h except that a new symbol, memo, has been introduced. With these definitions in place, the cache can be cleared simply using Clear@memo -- there is no need to redefine g and h anew. Better still, the cache can be localized by placing memo in Block, thus:

Block[{memo, a = 7, b = 9, c = 13, d = 0.002, e = 2, f = 1}
, Table[g[t, k], {t, 0, 100}, {k, 0, 100}]
]

The cache is discarded when the block is exited.

Memoization Using Advice

The original and revised memoization techniques required invasive changes within the function g and h. Sometimes, it is convenient to introduce memoization after the fact. One way to do this would be to use the technique of advising -- a kind of functional programming analog to subclassing in OO programming. A particular implementation of function advice appears regularly in the pages of StackOverflow. However, that technique is also invasive. Let's consider an alternate technique of adding advice to g and h without altering their global definitions.

The trick will be to temporarily redefine g and h within a Block. The redefinitions will first check the cache for the result and, failing that, call the original definitions from outside the block. Let's go back to the original definitions of g and h that are blissfully unaware of memoization:

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

The basic schema for this technique looks like this:

Module[{gg, hh}
, copyDownValues[g, gg]
; copyDownValues[h, hh]
; Block[{g, h}
  , m:g[a___] := m = gg[a]
  ; m:h[a___] := m = hh[a]
  ; (* ... do something with g and h ... *)
  ]
]

The temporary symbols gg and hh are introduced to hold the original definitions of g and h. Then g and h are locally rebound to new caching definitions that delegate to the original definitions as necessary. Here is definition of copyDownValues:

ClearAll@copyDownValues
copyDownValues[from_Symbol, to_Symbol] :=
  DownValues[to] =
    Replace[
      DownValues[from]
    , (Verbatim[HoldPattern][from[a___]] :> d_) :> (HoldPattern[to[a]] :> d)
    , {1}
    ]

In an effort to keep this post short(er), this "copy" function is concerned only with down-values. A general advice facility also needs to account for up-values, subvalues, symbol attributes and so on.

This general pattern is easy, if tedious, to automate. The following macro function memoize does this, presented with little comment:

ClearAll@memoize
SetAttributes[memoize, HoldRest]
memoize[symbols:{_Symbol..}, body_] :=
  Module[{pairs, copy, define, cdv, sd, s, m, a}
  , pairs = Rule[#, Unique[#, Temporary]]& /@ symbols
  ; copy = pairs /. (f_ -> t_) :> cdv[f, t]
  ; define = pairs /. (f_ -> t_) :> (m: f[a___]) ~sd~ (m ~s~ t[a])
  ; With[{ temps = pairs[[All, 2]]
         , setup1 = Sequence @@ copy
         , setup2 = Sequence @@ define }
    , Hold[Module[temps, setup1; Block[symbols, setup2; body]]] /.
        { cdv -> copyDownValues, s -> Set, sd -> SetDelayed }
    ] // ReleaseHold
  ]

After much ado, we are now in a position to externally impose memoization upon the non-caching versions of g and h:

memoize[{g, h}
, Block[{a = 7, b = 9, c = 13, d = .002, e = 2, f = 1}
  , Table[g[t, k], {t, 0, 100}, {k, 0, 100}]
  ]
]

Putting it all together, we can now create a responsive Manipulate block:

Manipulate[
  memoize[{g, h}
  , Table[g[t, k], {t, 0, tMax}, {k, 0, kMax}] //
      ListPlot3D[#, InterpolationOrder -> 0, PlotRange -> All, Mesh -> None] &
  ]
, {{tMax, 10}, 5, 25}
, {{kMax, 10}, 5, 25}
, {{a, 7}, 0, 20}
, {{b, 9}, 0, 20}
, {{c, 13}, 0, 20}
, {{d, 0.002}, 0, 20}
, {{e, 2}, 0, 20}
, {{f, 1}, 0, 20}
, LocalizeVariables -> False
, TrackedSymbols -> All
]

Manipulate screenshot

The LocalizeVariables and TrackedSymbols options are artifacts of the dependencies that g and h have on the global symbols a through f.

回复 原文
~没有更多了~

关于作者

莳間冲淡了誓言ζ

暂无简介

文章
评论
27 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

忆悲凉

文章 0 评论 0

hgfg1645

文章 0 评论 0

qq_qLPLYi

文章 0 评论 0

戏舞

文章 0 评论 0

殊姿

文章 0 评论 0

﹂绝世的画

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文