8

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ますか? それとも、との両方の結果の表を作成するための迅速な方法でしょうか? 前述のように、関数内で計算できるようにしたいと考えています。hModuleBlockghghManipulate

4

2 に答える 2

11

Blockあなたが要求したように使用する1つの方法は次のとおりです。

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、それらの正式なパラメーター リスト (シグネチャ) を拡張することもできますが、これには、過去のさまざまなパラメーター値に対応する古いメモ化された定義が自動的にクリアされないという欠点があります。このアプローチのもう 1 つの問題は、結果として得られるコードがより壊れやすくなり、パラメータ数の変更などがあることです。

編集

ただし、結果の表を作成したい場合は、これを 1 回だけ実行するため、いくらか高速になる可能性があります。この場合、すべてのメモ化された定義を保持する必要があります。だから、ここにコードがあります：

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

(元のパラメーターを使用していました)。このメソッドでは、メモ化された定義がグローバル ルール ベースに残っていることを確認できます。次にまったく同じパラメーターで関数を呼び出すと、再計算ではなくメモ化された定義がフェッチされます。上記で概説したこのアプローチの問題とは別に、何もクリアされないため、メモリ使用量にも注意する必要があります。

于 2011-09-08T08:33:04.220 に答える
8

補助記号を使用したメモ化

g質問で示されているメモ化手法を変更して、キャッシュをクリアする必要があるたびにとの定義をh再確立する必要がないようにすることができます。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)

定義は、新しい記号 ,が導入されたことを除いて、元のメモ化されたバージョンのgand と基本的に同じです。これらの定義が整っていれば、次のコマンドを使用するだけでキャッシュをクリアできます。再定義して新たに作成する必要はありません。さらに良いことに、キャッシュは次のように配置することでローカライズできます。hmemoClear@memoghmemoBlock

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た。後からメモ化を導入すると便利な場合もあります。これを行う 1 つの方法は、アドバイジングの手法を使用することです。これは、OO プログラミングのサブクラス化に類似した一種の関数型プログラミングです。関数アドバイスの特定の実装は、StackOverflow のページに定期的に表示されます。ただし、その手法は侵襲的でもあります。グローバル定義を変更せずにgアドバイスを追加する別の手法を考えてみましょう。h

トリックは、一時的にgとh内で再定義することBlockです。再定義は、最初に結果のキャッシュをチェックし、それが失敗すると、ブロックの外側から元の定義を呼び出します。gandの元の定義に戻りましょう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とhhが導入されています。次に、必要に応じて元の定義に委譲する新しいキャッシュ定義にローカルで再バインドされます。の定義は次のとおりです。ghghcopyDownValues

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苦労の末、非キャッシュ バージョンの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}]
  ]
]

すべてをまとめると、レスポンシブ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です。af

于 2011-09-11T17:00:49.067 に答える