1

Java で反復的および再帰的な階乗手順の両方を計算する時間を比較しています。System.currentTimeMillisメソッドを使用して、各アルゴリズムの計算にかかる時間を比較しようとしていますが、違いを計算できないようです。このメソッドを使用する適切な方法が何であるかはわかりませんが、ここでのイベントはコードで達成しようとしているものです:

// ... more code above

System.out.print("Please enter an integer: ");
int integer = readInt();
System.out.println();

// demonstrate recursive factorial and calculate
// how long it took to complete the algorithm
long time1 = System.currentTimeMillis();
int fact1 = factRecursive(integer);
long time2 = System.currentTimeMillis();
System.out.format("Result of recursive factorial %s is %d\n", integer, fact1);
System.out.format("Algorithm took %d milliseconds\n\n", (time2 - time1));

// ... more code below

出力は次のとおりです。

Please enter an integer: 25

Result of recursive factorial 25 is 2076180480
Algorithm took 0 milliseconds

Result of iterative factorial 25 is 2076180480
Algorithm took 0 milliseconds

両方のケースの階乗を計算するのに予想される時間がゼロであってはならないため、明らかに私はここで何か間違ったことをしているに違いありません。

編集:誰かが興味を持っている場合、階乗の私のソリューションは次のとおりです(特にユニークではありませんが、とにかくここにあります):

// factRecursive uses a recursive algorithm for 
// caluclating factorials.
public static long factRecursive(long n)
{
    return n = (n == 1)? 1 : n * factRecursive(n - 1);
}

// factIterative uses an iterative algorithm for
// calculating factorials.
public static long factIterative(long n)
{
    long product = 1;

    if(n == 1) return n;

    for(int i = 1; i <= n; ++i)
        product *= i;

    return product;
}

そして、いくつかの出力です。驚くべきことに、再帰バージョンはうまく機能します。39くらいまでじゃない！反復バージョンのパフォーマンスが著しく向上し始めること。

Please enter an integer: 39

Result of recursive factorial 39 is 2304077777655037952
Algorithm took 5828 nanoseconds

Result of iterative factorial 39 is 2304077777655037952
Algorithm took 5504 nanoseconds
4

6 に答える 6

4

の解像度はSystem.currentTimeMillis()、システムによって異なります。アルゴリズムが速すぎて、このタイマーで測定できないようです。

System.nanoTime()代わりに使用してください。その精度もシステムに依存しますが、少なくとも高分解能の時間測定が可能です。

ジャストインタイム コンパイルはパフォーマンスに大きな影響を与える可能性がありますが、ほとんどの仮想マシンでは、再コンパイルする前にメソッドを何度も呼び出す必要があります。これにより、この種のマイクロベンチマークから正確な結果を得ることが難しくなります。

于 2012-04-11T01:19:53.227 に答える
3

適切に作成された階乗関数は、n = 25 の場合に非常に高速に実行されるはずなので、約 0 ミリ秒で実行されることはそれほど驚くべきことではありません。次の 3 つのオプションがあります。

  1. n を大きくしてください。これにより、階乗関数の実行時間が長くなり、測定対象が得られます。
  2. System.nanoTimeを使用して、ミリ秒ではなく、おおよそのナノ秒で時間を測定します。
  3. 1と2の両方を行うことをお勧めします。

他の回答者が指摘しているように、実際には開始から終了を差し引いていますが、これは逆です。明らかに、それも修正する必要があります。ただし、その変更は結果の符号にのみ影響し、絶対値には影響しません。

EDIT：25の階乗を見つけるのがどれだけ速いかを見るために、私はこのPython実装を書きました

>>> def fact(n):
...     def _fact(n, acc):
...             if n == 1:
...                     return acc
...             return _fact(n - 1, n * acc)
...     if n < 0:
...             return 0 # Or raise an exception
...     if n < 2:
...             return 1
...     return _fact(n, 1)
... 
>>> fact(25)
15511210043330985984000000L
>>> import timeit
>>> t = timeit.Timer("fact(25)", "from __main__ import fact")
>>> print t.timeit()
6.2074379921

fact(25)Python は、テール コールの最適化を行わないインタープリター型の動的型付け言語ですが、アキュムレータを使用した単純な再帰ソリューションを使用すると、私のマシンでは 6.2 秒で 100 万回を見つけることができます。したがって、平均実行時間は 6.2 マイクロ秒です。ミリ秒のクロック精度で 1 回の実行で反復ソリューションと再帰ソリューションの実質的な違いを測定する機会はありません。

于 2012-04-11T01:18:30.073 に答える
1

(終了時刻 - 開始時刻) を実行する必要があります。

これを試して：

System.out.format("Algorithm took %d milliseconds\n\n", (time2 - time1));
于 2012-04-11T01:16:43.557 に答える
1

よくある間違い。time2 から time1 を減算する必要があります。

変数に適切な名前を付けると役立ちます。たとえばstartTime、次のようにしendTimeなければならないことがわかるか、少なくとも気付くでしょう>endTime - startTimeendTimestartTime

于 2012-04-11T01:18:25.940 に答える
1

結局、高速再帰がそれほど重い処理を行っていないように見えます。

System.nanoTime()代わりに使用してください。ナノ秒を返す

http://docs.oracle.com/javase/7/docs/api/java/lang/System.html

nanoTime() 実行中の Java 仮想マシンの高解像度タイム ソースの現在の値をナノ秒単位で返します。

テストする別の方法は、階乗を 1000 回繰り返すことです。次に、時差を 1000.00 (2 倍) で割ります。

于 2012-04-11T01:20:12.460 に答える
0

意味のあるタイミングの結果を得るには、それを繰り返して無視する必要があります。少なくとも最初の10,000回はメソッドを呼び出し（コードがコンパイルされるため）、さらに2〜10秒間（繰り返し）実行する必要があります。

于 2012-04-11T06:02:50.427 に答える