3

次の再帰的方法が反復的方法よりも速い理由を誰かが説明できますか（両方とも文字列連結を行っています）？反復的なアプローチは、再帰的なアプローチを打ち負かすことを想定していませんか？さらに、再帰呼び出しごとに、スタックの上に新しいレイヤーが追加されます。これは、スペース効率が非常に低くなる可能性があります。

    private static void string_concat(StringBuilder sb, int count){
        if(count >= 9999) return;
        string_concat(sb.append(count), count+1);
    }
    public static void main(String [] arg){

        long s = System.currentTimeMillis();
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 9999; i++){
            sb.append(i);
        }
        System.out.println(System.currentTimeMillis()-s);
        s = System.currentTimeMillis();
        string_concat(new StringBuilder(),0);
        System.out.println(System.currentTimeMillis()-s);

    }

プログラムを複数回実行しましたが、再帰的なプログラムは、反復的なプログラムよりも常に3〜4倍速くなります。反復を遅くしている主な理由は何でしょうか？

4

1 に答える 1

8

私のコメントを参照してください。

マイクロベンチマークを適切に行う方法を必ず学んでください。あなたは両方の多くの反復のタイミングをとり、あなたの時間のためにこれらを平均するべきです。それとは別に、最初のコンパイルを行わないことで、VMが2番目の利点を不当に与えていないことを確認する必要があります。

実際、デフォルトのHotSpotコンパイルしきい値（を介して構成可能-XX:CompileThreshold）は10,000回の呼び出しであり、ここに表示される結果を説明している可能性があります。HotSpotは実際にはテールの最適化を行わないため、再帰的なソリューションの方が高速であるのは非常に奇妙です。StringBuilder.append主に再帰的ソリューションのためにネイティブコードにコンパイルされることは非常に妥当です。

ベンチマークを書き直して、自分で結果を確認することにしました。

public final class AppendMicrobenchmark {

  static void recursive(final StringBuilder builder, final int n) {
    if (n > 0) {
      recursive(builder.append(n), n - 1);
    }
  }

  static void iterative(final StringBuilder builder) {
    for (int i = 10000; i >= 0; --i) {
      builder.append(i);
    }
  }

  public static void main(final String[] argv) {
    /* warm-up */
    for (int i = 200000; i >= 0; --i) {
      new StringBuilder().append(i);
    }

    /* recursive benchmark */
    long start = System.nanoTime();
    for (int i = 1000; i >= 0; --i) {
      recursive(new StringBuilder(), 10000);
    }
    System.out.printf("recursive: %.2fus\n", (System.nanoTime() - start) / 1000000D);

    /* iterative benchmark */
    start = System.nanoTime();
    for (int i = 1000; i >= 0; --i) {
      iterative(new StringBuilder());
    }
    System.out.printf("iterative: %.2fus\n", (System.nanoTime() - start) / 1000000D);
  }
}

これが私の結果です...

C:\dev\scrap>java AppendMicrobenchmark
recursive: 405.41us
iterative: 313.20us

C:\dev\scrap>java -server AppendMicrobenchmark
recursive: 397.43us
iterative: 312.14us

これらは、1000回の試行で平均した各アプローチの時間です。

基本的に、ベンチマークの問題は、多くの試行（大数の法則）で平均化されないことと、個々のベンチマークの順序に大きく依存することです。私があなたのために与えた元の結果：

C:\dev\scrap>java StringBuilderBenchmark
80
41

これは私にはほとんど意味がありませんでした。HotSpot VMでの再帰は、関数型言語で使用されるようなテール最適化をまだ実装していないため、反復ほど高速ではない可能性があります。

ここで発生する面白いことは、デフォルトのHotSpotJITコンパイルしきい値が10,000回の呼び出しであるということです。反復ベンチマークは、コンパイルされる前にほとんどの部分で実行される可能性が高くなります。 append一方、再帰的アプローチは、コンパイルappend 後に楽しむ可能性が高いため、比較的高速である必要があります。これが結果に影響を与えないようにするために、私は合格-XX:CompileThreshold=0して見つけました...

C:\dev\scrap>java -XX:CompileThreshold=0 StringBuilderBenchmark
8
8

つまり、どちらも速度はほぼ同じです。ただし、より高い精度で平均化すると、反復が少し速くなるように見えることに注意してください。後者のベンチマークには、動的最適化のためにより多くの統計を収集したVMの利点があるため、順序によってベンチマークにも違いが生じる可能性があります。

于 2012-09-05T03:34:48.657 に答える