1

PHPは私にとってより単純なので、楽しみのためにPHPのベンチマークを実行したかったので、階乗を使用することにしました。

再帰関数は、反復法と比較して、立ち上がったときに速度が完全に低下し80!、反復が安定した線を持っている間に徐々に上向きに急上昇しました。実際には、次のようになります（x =階乗、y =秒）：

http://i52.tinypic.com/2a9s7z4.png

しかし、C / Java（私がテストを実装したばかり）では、同じ結果が互いにわずか1〜5％オフであり、ほぼ同じ速度であることが示されています。

スクリプト言語でこの方法でアルゴリズムをベンチマークするのは役に立たないのでしょうか。

編集：NullUserExceptionの場合：

function factrec($x) {
    if($x <= 1) {
        return $x;
    } else {
        return $x * factrec($x - 1);
    }
}
4

7 に答える 7

4

スクリプト言語でアルゴリズムをベンチマークすることは絶対に無意味ではありません。ベンチマークを実行した後、PHPで階乗のどの実装を使用しますか？（何らかの理由で組み込みのものを使用できなかったと仮定します。）

ただし、アルゴリズムを実装する言語とは大幅に異なる機能を備えた言語でベンチマークを行うことは、かなり無意味です。ここで、PHPでの関数呼び出しとifステートメントの相対的なコストは、結果を大幅に歪めています（または、これはとにかく私の最善の推測です）。なぜこれが起こっているのかを注意深く理解し、それを避ければ、それでも実り多いものになる可能性があります。気づいたように、違いはより誇張されます。目標言語で書くのが簡単なのか、違いを回避するのが簡単なのかということになります。

アルゴリズムの複雑さを簡単に計算するだけで、どちらを使用するかを決定するか、少なくとも選択を絞り込むことができます。

Mike Axiakがコメントで指摘しているように、ここでは異なるアルゴリズムをテストしていません。同じアルゴリズムの2つの異なる実装をテストしています。実行中の製品をiからnに維持し1ます。ターゲットとは異なる言語でこれを行うことは、ほとんどの場合無意味です。

于 2010-09-27T23:11:06.057 に答える
1

私の意見では、アルゴリズム自体をテストする場合は、C / C ++を使用して、最適な条件で提供できる「生のパワー」を取得します。

一方、特定の条件でどのアルゴリズムが最適に機能するかを選択する必要がある場合は、そのような条件を最大限に再現しようとします。PHPアプリケーションに入れる必要がありますか？PHPが提供する構造を使用して、PHPでテストしてみましょう。STLコンテナで動作する必要がありますか？アレイだけでなく、この条件でテストします。実際の条件でのIMHOテストは、意味のある結果を得るための鍵です。そのような結果を得た後、別の良いことは、そのような条件を微調整し（プロジェクトでそれらを変更できる限り）、どのような効果が得られるかを確認して、最良の条件-アルゴリズムのカップルを見つけることです。

于 2010-09-27T23:09:49.820 に答える
1

再帰的実装と反復的実装は、特定のアルゴリズムの漸近的動作に実際の影響を与えるべきではありません。一部の言語（scala、Scheme、Lua、Standard ML、Mozart / Oz、erlang）では、2つは実際にはまったく同じように動作するように記述できます。つまり、次のスキームコードです。

(define factorial
  (lambda (n acc)
    (if (= n 0) acc
        (factorial (- n 1) (* n acc)))))
(factorial 5 1)
-> 120

スタックを使用しないため、反復アプローチと同じように実行されます。（これは末尾呼び出しの最適化と呼ばれ、末尾再帰を実行するときにそのような言語で呼び出されます。）

于 2010-09-27T23:11:23.760 に答える
1

演習のポイントが楽しかったことを考えると、それは無意味ではありません！しかし、PHPに再帰計算を実行させようとすることは、関数型プログラミング言語を試す準備ができていることを示している可能性があります。Haskellを見たことがありますか？末尾呼び出しの最適化、誰か？

さあ、ダークサイドに加わってください。

于 2010-09-27T23:21:52.687 に答える
1

JavaとCは、PHPよりも桁違いに高速です。
結果を表示するには、入力サイズを大幅に増やす必要があります。

その上、Aaron McSmoothが言ったように、それを使用することを計画している言語以外の言語でアルゴリズムをベンチマークすることは無意味です。

よくわかりませんが、PHPが末尾呼び出しの最適化を行うとは思えません。とにかく、末尾再帰関数を使用すると、再帰関数のパフォーマンスが大幅に向上するはずです。

function factorial($n, $product) {
    if ($n < 1)
        return $product;
    else
        return factorial($n-1, $product*$n);
}

print(factorial(80, 1));
于 2010-09-27T23:25:30.927 に答える
1

ベンチマークは決して無意味ではありません。どの言語で書かれたコードでもアプリケーションにとって遅すぎる場合は、ボトルネックを突き止めます。それらのボトルネックを見て、解決策を探します。解決策の 1 つは、アルゴリズムの別の定式化を使用するか、別の言語で書き直すことです。

私はPHPについて何も知らないので、その環境で再帰が適切に処理されるかどうかはわかりませんが、負荷の高い反復的な数学の実装には適していないという印象があります...

于 2010-09-27T23:12:36.553 に答える
1

再帰が苦手なPHPの問題に直面しています。これは通常、人々が PHP を選択して実行するようなものではありません。常に仕事に最適なツールを選択してください。

于 2010-09-27T23:13:50.920 に答える