Java迭代與遞歸

任何人都可以解釋爲什麼下面的遞歸方法比迭代更快（兩者都在做字符串連接）嗎？這種迭代方法是否設想剔除遞歸方法？加上每次遞歸調用都會在堆棧頂部添加一個新層，這可能會非常節省空間。Java迭代與遞歸

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倍。那裏導致迭代速度較慢的主要原因是什麼？

來源

2012-09-05 peter

確保您瞭解如何正確使用microbenchmark。你應該爲這兩個時間進行多次迭代計時，並對你的時間進行平均。除此之外，你應該確保虛擬機不會因爲沒有編譯第一個而給第二個不公平的優勢。 – oldrinb

另外，改變它們的順序，在循環中重複整個測試至少5次（丟棄前兩次用於預熱）並使用System.nanoTime – Thilo

實際上，默認的HotSpot編譯閾值（可通過「-XX：CompileThreshold」配置）是10,000次調用，這可能解釋您在這裏看到的reuslts。 HotSpot並沒有真正進行任何尾部優化，所以遞歸解決方案更快，這很奇怪。 – oldrinb

請參閱my comments。

請確保您瞭解如何正確使用microbenchmark。你應該爲這兩個時間進行多次迭代計時，並對你的時間進行平均。除此之外，你應該確保虛擬機不會因爲沒有編譯第一個而給第二個不公平的優勢。

實際上，默認的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次試驗。

基本上，您的基準測試的問題是它在許多測試（law of large numbers）上並不是平均值，並且它高度依賴於各個基準的排序。最初的結果我得到了你的：

C:\dev\scrap>java StringBuilderBenchmark 
80 
41

這讓很少了意義。在HotSpot虛擬機上進行遞歸很可能不會像迭代一樣快，因爲它尚未實現任何可能用於功能語言的尾部優化。

現在，這裏發生的有趣事情是默認的HotSpot JIT編譯閾值爲10000次調用。在編譯append之前，您的迭代基準測試大部分可能會執行大部分。另一方面，您的遞歸方法應該相對較快，因爲在編譯之後，它將更有可能享受append。從影響的結果消除此，我通過-XX:CompileThreshold=0，發現...

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

所以，當它發生的時候，他們都在速度大致相等。但請注意，如果您的平均精確度更高，迭代似乎會更快。順序也可能在我的基準測試中發揮重要作用，因爲後者的基準測試將爲虛擬機收集更多的動態優化統計信息。

來源

2012-09-05 03:34:48 oldrinb

第二段是什麼意思？在熱身之後，遞歸有時可能會更快，甚至會與迭代方法結合？ – peter

@ user1389813您觀察到遞歸解決方案速度更快，因爲默認情況下HotSpot會在10,000次調用後將方法編譯爲本機代碼。如果你交換訂單，你很可能會觀察到相反的情況。 – oldrinb

Java迭代與遞歸

回答

相關問題