Android的斐波納契基準/深度遞歸

Question

我在我的Android手機上運行斐波那契基準測試，我得到了一些奇怪的結果。因爲我並不在乎UI線程是否被鎖定，所以我在應用程序的UI線程內部運行下面的代碼（這可能會影響性能btw？）。

public void startBenchmark(View view) { 
     results = ""; 

     results += String.format("Begin test"); 
     for (int i = 45; i < 46; i++) { 
      startTime = System.currentTimeMillis(); 
      fib(i); 
      results += String.format("%d\n", System.currentTimeMillis() - startTime); 
     } 
     results += String.format("End test"); 
     Log.d("Results", results); 


    Log.d("Status", "Finished"); 
} 

private static int fib(int n) { 
    return n <= 1 ? n : fib(n - 1) + fib(n - 2); 
} 

我也在JavaScript中實現了相應的代碼;

function performBenchmark() { 

    for (var i = 45; i < 46; i++) { 
     benchmark(i) 
    } 

} 

function benchmark(n){ 
    var start= Date.now(); 
    document.getElementById("disp").innerHTML += "fib(" + n + "): " + fib(n) + " <br />"; 
    document.getElementById("results").innerHTML += (Date.now() - start) + "<br />"; 

} 

function fib(n) { 
    return n <= 1 ? n : fib(n - 1) + fib(n - 2); 
} 

我的問題是，FIB（45）我得到的東西像本地平臺420秒使用Java和瀏覽器使用Javascript 120秒對我的三星GALAXY Nexus兩者都運行。

是否有一些明顯的錯誤與我的Java實現Android可能會放緩基準？

注意; 我並不是主要希望切換到更快的算法，但我想了解爲什麼Javascript（以及我爲iOS創建的實現）比爲Android實現的Java快得多。

在我的筆記本電腦上運行，我得到了比Java更快的Java結果。

Answer 1

Java代碼被執行5次，JavaScript只有一次。

Answer 2

比較非常非常低效的代碼沒有意義。當你這樣做的時候，你正在比較語言所做的非常具體的優化，這些語言會讓你很少指出一個不同的程序可能會做什麼。

---

您的解決方案在Java和JavaScript中速度非常慢。有些語言足夠智能，可以更高效地重寫代碼（例如，函數式語言），但Java和JavaScript都不會重新組織代碼以提高效率。

private static int fib(int n) { 
    return n <= 1 ? n : fib(n - 1) + fib(n - 2); 
} 

想想這一點，得到的1134903170的解決方案，你需要調用這個方法比這許多倍（踏踏實實爲1，所有的呼叫到這些值）

注意：每個解決方案的指數時間更長，並且與解決方案成正比。

我建議你在Java和JavaScript中使用更快的迭代。

private static long fib(int n) { 
    long a = 1, b = 1; 
    while (--n > 1) { 
     long c = a + b; 
     a = b; 
     b = c; 
    } 
    return b; 
} 

注：本採取的是成正比的n的價值，在這種情況下，時間45

注2：該解決方案是如此短暫，代碼甚至不熱身，並得到由編譯JIT。

public static void main(String... ignore) { 
    for (int j = 0; j < 5; j++) { 
     long fib = 0, start = System.nanoTime(); 

     int repeats = 2000; 
     for (int i = 0; i < repeats; i++) 
      fib = fib(45); 
     long avgTime = (System.nanoTime() - start)/repeats; 

     System.out.println(fib + " took an average of " + avgTime + " nano-seconds"); 
    } 
} 

打印

1134903170 took an average of 2695 nano-seconds 
1134903170 took an average of 995 nano-seconds 
1134903170 took an average of 90 nano-seconds 
1134903170 took an average of 89 nano-seconds 
1134903170 took an average of 89 nano-seconds 

注3：89毫微秒更快〜4個十億倍，這無法通過使用更快的機器進行說明。