『再帰計算を速くする方法』

Maple で漸化式などの再帰計算をを行う場合に役立つ Tips を紹介します。
この Tips を用いれば再帰計算をより速く行うことができるようになります。

以下は、教科書に出てくるような再帰計算の典型例、フィボナッチ数列を定義するための Maple 手続き表現です。

>    restart:

>    fibStandard := proc(n)
  if n<2 then
    n;
  else
    fibStandard(n-1) + fibStandard(n-2);
  end if;
end proc:

いま定義した fibStandard 関数でフィボナッチ数列の計算を行ってみます。

>    st := time():
fibStandard(30);
time() - st;

832040

6.569

高々30項までの計算をするだけなのに、6.6 秒もの時間がかかっています。
(この計算は Pentium M 800MHz 相当のマシンで実行されています)

一般的なプログラミング言語と同様に、再帰計算を行う場合は事前の計算結果を保存するようにコードを与えることで、再帰計算をより速く行うことができるようになります。

Maple で事前の計算結果を保存するには、proc 関数による手続き表現の定義内で option remember を与えることで可能となります。次の改善版のフィボナッチ数列関数を参照してください;

>    fibImproved := proc(n)
  option remember; # this is for recursive definition

  if n<2 then
    n;
  else
    fibImproved(n-1) + fibImproved(n-2);
  end if;
end proc:

この関数 fibImproved で計算した結果は以下のようになります;

>    st := time():
fibImproved(30);
time() - st;

832040

0.

関数自体の呼び出し回数も大幅に異なります。

profile コマンドを利用してその違いを確認してみましょう。

>    profile(fibStandard, fibImproved);

>    [fibStandard(10), fibImproved(60)]:

>    showprofile();

function           depth    calls     time    time%         bytes   bytes%

---------------------------------------------------------------------------

fibStandard           10      177    0.000     0.00        103148    71.58

fibImproved           31       61    0.000     0.00         40960    28.42

---------------------------------------------------------------------------

total:                41      238    0.000     0.00        144108   100.00

fibStandard 関数では第10項の計算ですでに177回もの呼び出しが行われていますが、fibImproved 関数では第60項の計算でも高々61回の呼び出しで済んでいます。また消費したメモリ量についても fibStandard は fibImproved の2倍以上のメモリを消費していることがわかります。

(fibImproved は一度計算した結果を保存するため、再度第60項以内の項を求める場合でも計算を必要としません)

このように、漸化式などを含む再帰的な計算を行う場合には、『 option remember 』の一言を proc 関数で宣言するだけで、大幅な高速化を図ることができます。

閉じる