7 
f[0] = 0;
f[1] = 1;
f[x_] := f[x-1] + f[x-2]

この関数は Mathematica での実行が遅く、速度を上げる必要があります。関数型プログラミングと再帰を使用する必要があります。なぜこれがこんなに遅いのかわからないので、これを改善する方法が少しでもあれば助かります。

4

3 に答える 3

9

より高速な再帰関数を作成する良い方法は、以前の値を記憶させることです。もちろん、これはメモリを犠牲にしますが、このような場合に役立ちます。を計算するf[x]には、計算f[x-1]しf[x-2]て、そして を計算するには、もう一度f[x-1]計算します。f[x-2]多くの値を何度も再計算することになります。（私の不正確さを許してください！）

物を保存するには、次のイディオムを使用できます。

f[x_] := ( f[x] = (* calculation of f[x] goes here *)  )

編集: このマシンには mathematica がありませんが、間違った値を計算する方法はないと確信しています。

f[0] = 0;
f[1] = 1;
f[x_] := ( f[x] = f[x-1] + f[x-2] );

f[256]

以下のコメントで述べたように、 の他の定義がある場合はf、最初に でそれらを一掃することをお勧めしますClear[f]。

rcollyer に感謝: 注意してください$RecursionLimit! デフォルトは 256 です (もちろん、これには正当な理由があります。通常、本当に深い再帰は悪い考えです。)

于 2010-11-09T03:14:40.783 に答える
3

Jefromiは正しいです。ウィキペディアでメモ化を見てください。彼らは階乗の例とメモ化でそれをスピードアップする方法を使用します。

于 2010-11-09T03:20:13.610 に答える
2

メモ化 は、より高速な再帰関数を作成するための優れた方法です。ただし、この場合、メモ化を必要とせずに、元の関数よりもはるかに高速に実行される再帰的な代替手段があります。

重要な観察は、元の定義が多くの冗長な計算を実行していることを確認することです。を計算するとどうなるか考えてみましょうfib[4]:

fib[4] = fib[3] + fib[2]
  fib[3] = fib[2] + fib[1]
    fib[2] = fib[1] + fib[0]
      fib[1] = 1
      fib[0] = 1
    ∴ fib[2] = 1 + 1 = 2
    fib[1] = 1
  ∴ fib[3] = 2 + 1 = 3
  fib[2] = fib[1] + fib[0]
    fib[1] = 1
    fib[0] = 1
  ∴ fib[2] = 1 + 1 = 2
∴ fib[4] = 2 + 1 = 3

このプロセスでは、fib[2]とfib[0]がそれぞれ 2 回fib[1]計算され、3 回計算されました。大規模な計算では、無駄が劇的に増加します。実際には指数関数的に増加します。

同じフィボナッチ数を手で計算する場合は、次のように進めます。

0: given   0
1: given   1
2: 0 + 1 = 1
3: 1 + 1 = 2
4: 1 + 2 = 3

冗長な計算はありません。任意の時点で、前の 2 つの結果を考慮するだけで済みます。この後者のアプローチは、次のように再帰的に表現できます。

fib2[0] = 0;
fib2[n_] :=
  Module[{f},
    f[n, p1_, _] := p1;
    f[x_, p1_, p2_] := f[x + 1, p1 + p2, p1];
    f[1, 1, 0]
  ]

Block[{$IterationLimit = Infinity}, fib2[100000]]

間違いなく、このフォームはオリジナルほど読みにくいものです。一方、元の関数はfib[35]私のマシンで計算するのに 35 秒かかりましたが、修正された関数の実行時間はゼロと報告されました。さらに、改訂された関数fib2[100000]は 0.281 秒で計算され、メモ化の余分なストレージは必要ありません。 fib[100000]は元の関数の手の届かないところにあり、メモ化されたバージョン は私の Mathematica 7.01 カーネルをクラッシュさせました.メモ化されたルールが多すぎるのでしょうか?

デフォルトでは，Mathematica は関数を4096回まで繰り返すことに注意してください．その制限を上げるに$IterationLimitは、上記の例に示すように、より高い値を に割り当てる必要があります。

もちろん、Mathematica には組み込みFibonacci関数を含め、フィボナッチ数を計算する非再帰的な方法がたくさんあります。しかし、それはこの演習のポイントではありません。

テールコールの最適化?

末尾呼び出しを使用して再帰関数を表現することは常に望ましいことです。これにより、スタックに中間結果を保持するオーバーヘッドなしで、再帰を単純な反復で実行できます。 fib2末尾再帰です。Scheme などの一部の言語では、末尾呼び出しの最適化が義務付けられています。Javaなどの他の言語はそれをサポートできますが、サポートしません (または、Pythonの場合のようにサポートしません)。

Mathematica の場合、末尾呼び出しの最適化がどの程度行われるかは明確ではありません。この点の詳細については、別の SO の質問を参照してください。

于 2010-12-19T01:51:07.250 に答える