5

このコードは、Chromeでは3秒、Firefoxでは6秒かかります。Javaでコードを記述し、Java 7.0で実行すると、10ミリ秒しかかかりません。ChromeのJSエンジンは通常非常に高速です。なんでこんなに遅いの？ところで。このコードはテスト用です。フィボナッチ関数を書くのはあまり実用的な方法ではないことを私は知っています

fib = function(n) {
  if (n < 2) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
};

console.log(fib(32));
4

5 に答える 5

6

これは JavaScript のせいではなく、アルゴリズムの問​​題です。同じサブ問題を何度も再計算していますが、N が大きくなるとさらに悪化します。これは、単一の呼び出しの呼び出しグラフです。

                  F(32)
               /         \
            F(31)            F(30)
          /     \           /      \
      F(30)     F(29)     F(29)    F(28)
    /  \      /     \     /   \     |    \
F(29) F(28) F(28) F(27) F(28) F(27) F(27) F(26)

... deeper and deeper

このツリーからわかるように、いくつかのフィボナッチ数を数回計算しています。たとえば、F(28) は 4 回計算されています。「アルゴリズム設計マニュアル」本から：

このアルゴリズムが F(n) を計算するのにかかる時間は? F(n+1) /F(n) ≈ φ = (1 + sqrt(5))/2 ≈ 1.61803 なので、これは F(n) > 1.6^n を意味します。再帰ツリーには葉として 0 と 1 しかないため、これほど多くの数を合計すると、少なくとも 1.6^n の葉またはプロシージャ コールが必要になります。この控えめな小さなプログラムの実行には指数関数的な時間がかかります!

メモ化を使用するか、ソリューションをボトムアップで構築する必要があります (つまり、最初に小さなサブ問題)。

このソリューションはメモ化を使用します (したがって、各フィボナッチ数を 1 回だけ計算します)。

var cache = {};
function fib(n) {
  if (!cache[n]) {
    cache[n] = (n < 2) ? n : fib(n - 1) + fib(n - 2);
  }
  return cache[n];
}

これはそれをボトムアップで解決します：

function fib(n) {
  if (n < 2) return n;
  var a = 0, b = 1;
  while (--n) {
    var t = a + b;
    a = b;
    b = t;
  }
  return b;
}
于 2012-07-02T03:39:58.823 に答える
3

よく知られているように、質問で指定したフィボナッチ関数の実装には、単純に実装すると多くの手順が必要になります。特に、7,049,155 回の呼び出しが必要です。

ただし、これらの種類のアルゴリズムは、メモ化と呼ばれる手法で大幅に高速化できます。関数呼び出しfib(32)に数秒かかる場合は、関数が単純に実装されています。すぐに戻る場合は、実装がメモ化を使用している可能性が高いです。

于 2012-07-02T03:24:31.037 に答える
2

すでに提供された証拠に基づいて、私が引き出す結論は次のとおりです。

コードがコンソールから実行されていない場合（私のマシンであるSandy Bridge Macbook Airが55msでコードを計算するjsFiddleのように）、JSエンジンはJITを実行でき、場合によってはアルゴリズムを自動的にメモ化します。

jsコンソールから実行すると、これは発生しません。私のマシンでは、それは10倍未満の速度でした：460ms。

次に、コードを編集してF（38）を探しました。これにより、967msと9414msまで時間が増加し、同様のスピードアップ係数が維持されました。これは、メモ化が実行されておらず、スピードアップがおそらくJITtingによるものであることを示しています。

于 2012-07-02T06:27:42.683 に答える
1

ただのコメント...

関数呼び出しは比較的高価であり、再帰は非常に高価であり、効率的なループを使用する同等のものよりも常に遅くなります。たとえば、以下は IE の再帰的な代替手段よりも何千倍も高速です。

function fib2(n) {
  var arr = [0, 1];
  var len = 2;

  while (len <= n) {
    arr[len] = arr[len-1] + arr[len-2];
    ++len;
  }
  return arr[n];
}

また、他の回答で述べたように、OP アルゴリズムも本質的に遅いようですが、それは実際の問題ではないと思います。

于 2012-07-02T04:17:12.513 に答える