4

これを理解しようとしているときに出会った このリンクから取得しました。

関数は次のとおりです（自分で理解できるように少し変更しました）：

(function(){

    fibonacci = (function () {

        var cache = {};
        return function (n) {
            var cached = cache[n];
            if (cached) {
                console.log('already in the ', cache);
                return cached;
            }
            if (n <= 1) {
                console.log('no 0s or 1s, ', n);
                return n;
            }
            console.log('a brand new ', n, 'consider yourself cached');
            cache[n] = fibonacci(n - 2) + fibonacci(n - 1);
            console.log('current cache: ', cache);
            return cache[n];
        };
    }());

    fibonacci(20);

})();

理解しやすいように少し修正しましたが、出力が 0 に向かっていき、その後 0 から増加するため、迷ってしまいます。

cache[n] = fibonacci(n - 2) + fibonacci(n - 1);

fibonacci(n - 2)評価され、そのfibonacci(n - 1)直後。
しかし、そうであったとしても、JavaScript がこれら 2 つの機能をどのように一緒に追加するのか理解できません。

誰かがこれがどのように機能するかを少し理解するのを手伝ってくれますか、または少なくとも、もう少し理解しやすい方法で再構築するのを手伝ってくれませんか?

出力は次のとおりです。

a brand new  20 consider yourself cached 
a brand new  18 consider yourself cached 
a brand new  16 consider yourself cached 
a brand new  14 consider yourself cached 
a brand new  12 consider yourself cached 
a brand new  10 consider yourself cached 
a brand new  8 consider yourself cached 
a brand new  6 consider yourself cached 
a brand new  4 consider yourself cached 
a brand new  2 consider yourself cached 
no 0s or 1s,  0 
no 0s or 1s,  1 
current cache:  Object {2: 1} 
a brand new  3 consider yourself cached 
no 0s or 1s,  1 
already in the  Object {2: 1} 
current cache:  Object {2: 1, 3: 2} 
current cache:  Object {2: 1, 3: 2, 4: 3} 
a brand new  5 consider yourself cached 
already in the  Object {2: 1, 3: 2, 4: 3} 
already in the  Object {2: 1, 3: 2, 4: 3} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8} 
a brand new  7 consider yourself cached 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8} 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21} 
a brand new  9 consider yourself cached 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21} 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55} 
a brand new  11 consider yourself cached 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55} 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144} 
a brand new  13 consider yourself cached 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144} 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377} 
a brand new  15 consider yourself cached 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377} 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987} 
a brand new  17 consider yourself cached 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987} 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584} 
a brand new  19 consider yourself cached 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584} 
already in the  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181} 
current cache:  Object {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765}

ありがとう、再帰はおそらく大きな初歩的な質問であることを知っており、何度か使用しましたが、それがどのように機能するかを理解すると頭が回転します。

4

2 に答える 2

3

「JavaScript がこれら 2 つの機能を一緒に追加する方法がわかりません。」

JS は関数を追加しません。これらの関数呼び出しから返される値を追加します。f(n-2) が計算されたとします。f(n-1) が呼び出されると、次のように計算されます。

f(n-1) = f(n-2) + f(n-3)

ここまでで、式の右辺で両方の値を計算したので、両方の値がキャッシュから取得されます。

f(5) を計算したいとします。

f(5) = f(4) + f(3)

f(3) による再帰呼び出し:

f(3) = f(2) + f(1)

再帰呼び出し:

f(1) = 1 and f(2) = cached(f(1)) + f(0) = 1 + 0 = 1

ここで、calc f(3) に戻ります。値 f(2) と f(1) の両方がキャッシュされているため、次のようになります。

f(3) = 1 + 1 = 2

calc f(4) に戻ります

f(4) = f(3) + f(2) = 2 + 1 = 3

もう一度終了:

f(5) = f(4) + f(3) = 3 + 2 = 5

再帰の最も深いポイント (f(1)) に到達すると、キャッシュが使用され、値がまったく計算されないという事実に細心の注意を払ってください。これにより、この実装は非常に効率的になります!

于 2013-04-23T05:16:23.783 に答える
1

コードが単純化され、4 などの小さい数字から始めると、より簡単になる場合があります。以下は、最初に投稿したものと同じ機能です。

var cache = {};

function fibonacci(n) {   // assume n = 4
   var cached = cache[n];

最初は cache[4] が定義されていないため、次のテストは false と評価されます。

    if (cached) {
        console.log('already in the ', cache);
        return cached;
    }

n = 4 なので、次も偽です。

    if (n <= 1) {
        console.log('no 0s or 1s, ', n);
        return n;
    }

次に、次の行が実行されます。

    console.log('a brand new ', n, 'consider yourself cached');  // 4
    cache[n] = fibonacci(n - 2) + fibonacci(n - 1);

つまり:

    cache[4] = fibonacci(2) + fibonacci(3);

上記の行では、左側が最初に評価され、 の '4' プロパティの作成が開始されますcache。ステートメントが完成していないため、実際にはまだ作成されていないため、次のようになります。

cache = {4:undefined};

次に、何が割り当てられるかを確認するために右側が評価されます。演算子があるため+、両方の式を評価して、加算または連結として扱われるかどうかを確認する必要があります。

Nextfibonacci(2)が評価されます (+加算か連結かに関係なく、評価は左から右に進みます)。したがって、上記のプロセスが繰り返され、以下が作成されます。

    cache[2] = fibonacci(0) + fibonacci(1);

そして、あなたはほとんど持っています：

cache = {4:undefined, 2:undefined};

プロパティは実際にはまだ作成されていないことに注意してください。

今fibonacci(0)評価されます。今回は秒にifなり、0 が返されるため、nocache['0']が作成され、次のようになります。

cache[2] = 0 + fibonacci(1);

繰り返しますがfibonacci(1)、2 番目のifステートメントを評価すると が実行され、 が返さ1れるため、割り当てる値があるため、プロパティが作成され、値が割り当てられます。

    cache[2] = 0 + 1; // cache = {2:1, 4:undefined};

次の行に進みます。

    console.log('current cache: ', cache);
    return cache[n]; // returns 1;
}

したがって、前の呼び出しが続行されます。

    cache[4] = 1 + fibonacci(3);

再び次のようになります。

    cache[3] = fibonacci(1) + fibonacci(2);

最初の式は1最初から返されるため、次のifようになります。

    cache[3] = 1 + fibonacci(2);

2 番目の式は、cache[2] が存在する最初の if に到達するため、1 (つまり、cache[2] の値) が返されます。

    cache[3] = 1 + 1; // cache = {3:1, 3:2, 4:undefined};

そして cache[3] (これは 2) を返すので、次の場所に戻ります。

    cache[4] = 1 + 2;

キャッシュが {2:1, 3:2, 3:3} になりました

上記は順次操作として記述できます (すべての再帰関数は順次操作として記述できます)。これは、順次操作が常に高速であるため、速度が重要な場合に一般的です。この場合、シーケンシャル関数は非常に単純です。

function fibonacci2(n) {
  var fibs = {0:0, 1:1};
  var i = 1;
  while (i < n) {
    fibs[++i] = fibs[i-1] + fibs[i-2];
  }
  return fibs;
}

console.log(fibonacci2(4));
于 2013-04-23T23:05:42.023 に答える