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个十亿倍，这无法通过使用更快的机器进行说明。