1

C++ でメモ化がどのように機能するかを理解しようとしていたので、Fib で使用されているメモ化の例を調べました。順序。

std::map<int, int> fibHash;

int memoized_fib (int n)
{
    std::map<int, int>::iterator fibIter = fibHash.find(n);
    if( fibIter != fibHash.end() ) return *fibIter;

    int fib_val;
    if( n <=1 )    fib_val = 1;
    else           fib_val = memoized_fib ( n-1 ) + memoized_fib ( n-2 );

    fibHash[ n ] = fib_val;
    return fib_val;
}

fibHash[n] の仕組みに少し混乱しました。各 fib(#) の個々の値を保持するだけですか? また、イテレータはインデックスをトラバースしてテーブル内の正しい値を探し、それを返しますか? たとえば、fib(6) = 既に保存されている fib(5) と fib(4) を見つけて、それらを追加するだけですか?

4

3 に答える 3

4

あなたの言ってることは基本的に正しいです。

「[fibHash] は各 fib(#) の個々の値を保持するだけですか?」

はい、正確に。値は、計算されたとおりに入力されます ( を使用fibHash[ n ] = fib_val;)。低い fib 値は、高い値を計算するために使用されます。

fibHashマップは、X を fib(X) に単純明快にマップします。

この方法の利点は、fib(20) に続いて fib(21) と fib(23) を計算し、おそらく fib(15) を計算する場合、中間値を 1 回だけ計算する必要があることです。

この高速化のコストは、値を に格納するためのメモリですfibHash。

于 2012-10-05T21:10:10.203 に答える
2

fib_valコードは実際にそれぞれをfibHashマップに保存します。で呼び出されるfindメソッドfibHashは、マップを検索して、値が以前に計算されたかどうかを確認します。その場合、findこの値の反復子を返し、関数はそれを返します ( return *fibIter)。

fibHash[ n ] = fib_val;マップに新しい値を追加します。

于 2012-10-05T21:10:39.920 に答える
1

各 fib(#) の個々の値を保持するだけですか?

はい。

また、イテレータはインデックスをトラバースしてテーブル内の正しい値を探し、それを返しますか?

はい。

たとえば、fib(6) = 既に保存されている fib(5) と fib(4) を見つけて、それらを追加するだけですか?

依存します。最初の fib(6) は、fib(6) が以前に呼び出されたかどうかを確認するために検索します。保存されている場合は、保存された回答が返されます。一度も呼び出されていない場合は、fib(5) と fib(4) が呼び出されます。興味深いことに、fib(5) を計算する必要がある場合、fib(6) が実行する前に fib(4) を呼び出します*。その後、fib(6) も fib(4) を呼び出すと、結果は fibHash で見つかることが保証されます。 fib(5) はすでに fib(4) を呼び出しています。これが、 fib(n) が指数時間からより線形に近いものに崩壊する原因です。

フィボナッチの単純な再帰的実装は、1 を何度も加算することになります。

fib(5) =
fib(4)                                     + fib(3) =
fib(3)                   + fib(2)          + fib(2)          + fib(1) =
fib(2)          + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) =
fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) = 
1      + 1      + 1      + 1      + 1      + 1      + 1      + 1 =
8

実際、fib(n) を計算するには、fib(n)-1 の加算を行うことになります。しかし、fib(n) を計算する過程で、以前に計算されたフィボナッチ数を保存して使用する場合、それほど多くの追加を実行する必要はなくなります。この方法で fib(n) を計算するには、n 回の加算のみが必要です。

fib(5) =
fib(4)                            + fib(3) =
fib(3)                   + fib(2) + fib(3) =
fib(2)          + fib(1) + fib(2) + fib(3) =
fib(1) + fib(0) + fib(1) + fib(2) + fib(3) = 
1      + 1      + 1      + 2      + 3 =
8

* 順序は保証されませんが。fib(6) は最初に fib(4) を呼び出し、次に fib(6) が fib(5) を呼び出すと、fib(5) が fib(4) を呼び出し、格納された値を返すことが保証されます。

于 2012-10-05T21:40:20.687 に答える