0

再帰関数と非再帰関数を比較して、クラスプロジェクトでどちらが速いかを確認することになっています。教授はまた、イテレータが10,100,1000などに等しい場合、ミリ秒単位で反復の時間を計測することを望んでいます。すべてが機能するようになりましたが、C ++でタイマーを取得するのに多くの問題があったため、Javaに切り替えました。ミリ秒の出力を取得する方が簡単です。

しかし、8,000を超える数値を使用しようとすると、再帰アルゴリズムから大きなファットスタックオーバーフローエラーが発生します。誰かが私に洞察を与えることができますか？ボーナス：Non-Recursiveで行ったように、Recursive関数でタイマーを実行する方法もわかりません。これにどのようにアプローチしますか？

public class comparingTimes {
    public static void main(String[] args) {

        double num = 10000;
        double result;
        nonRec(num); 
        result = rec(num);      
        System.out.printf("Rec %.0f",(result));
    }
    public static void nonRec(double num)
    {
    double resultNum = 1;
    double total = 0;
    long startTime = System.currentTimeMillis();
    long endTime;
    for (double i = 1; i < num; i++)
     {
        total += i * (i+1);
        if (i == resultNum)
        {
            endTime = System.currentTimeMillis();
            System.out.printf("Total execution time: %f seconds - num = %.0f%n", (endTime - startTime)/1000.0, i);
            resultNum *= 10;
        }           
     }      
    System.out.printf("NonRec: %.0f%n", total); 
}
public static double rec(double num)
{
    if (num == 0)
        return 0;
    else            
        return num * (num-1) + rec(num-1);      
}
}
4

2 に答える 2

5

再帰の理想的な使用例は、各再帰レベルで「検索スペース」を大幅に削減する場合です。たとえば、再帰レベルごとに残りの検索スペースが半分になるバイナリ検索を考えてみましょう。

あなたの特定の問題は、各レベルが単純に値を減らすため、8000 レベルの再帰を実行しようとしていることです。これには、かなり大きなスタック スペースが必要になります。

-ssまたはオプションを使用して、JVMのスタックサイズを増やすことを検討でき-ossます（もちろん、実装によって異なります）。しかし、それはあなたを大いに買うだけです。

再帰操作全体のタイミングに関しては、最上位呼び出しの前の時間を に保存し、それを最上位呼び出しが返された後main()の時間と比較します。次のようになります。

long startTime = System.currentTimeMillis();
result = rec(num);
long endTime = System.currentTimeMillis();
// Now calculate the elapsed time.

再帰呼び出し自体の中でそれを試みる必要はありません。

再帰呼び出し内の特定のポイントでそれを実行したい場合は、「グローバル」カウンター変数 (クラスレベルの静的変数など、再帰自体の外部にある変数) を 0 に初期化し、再帰関数にそれを毎回インクリメントさせることができます。再帰レベル。

次に、変数が 10、100、1000 などに設定されている場合など、関心のあるポイントで時間デルタを出力します。

于 2013-01-30T04:37:38.823 に答える
0

スタック サイズを増やしてみてください。

時間計測に関しては

public static void main(String[] args) {

    double num = 10000;
    double result;
    long start = System.currentTimeMillis();
    nonRec(num); 
    long finish = System.currentTimeMillis();
    System.out.println("Time taken (non-recursive): " + (finish -start));
    start = System.currentTimeMillis();
    result = rec(num);      
    finish = System.currentTimeMillis();
    System.out.println("Time taken (recursive): " + (finish -start));
    System.out.printf("Rec %.0f",(result));
}
于 2013-01-30T05:31:37.507 に答える