2

我正在我的 Android 手机上运行斐波那契基准测试，我得到了一些奇怪的结果。因为我并不关心 UI 线程是否被锁定，所以我在我的应用程序的 UI 线程内运行下面的代码（这会影响性能吗？）。

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)，我在本机平台上使用 Java 得到了 420 秒，在 Chrome 中使用 Javascript 得到了 120 秒，两者都在我的三星 Galaxy Nexus 上运行。

我在 Java for Android 中的实现是否存在明显的错误，可能会减慢基准测试速度？

笔记; 我主要不是希望切换到更快的算法，而是试图理解为什么 Javascript（以及我为 iOS 制作的实现）比 Java 中的 Android 实现要快得多。

在我的笔记本电脑上运行时，Java 的结果比 Javascript 快得多。

4

2 回答 2

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 纳秒快了约 40 亿倍，这无法用更快的机器来解释。

于 2013-05-10T19:07:52.030 回答
0

Java-Code 执行 5 次，JavaScript 仅执行一次。

于 2013-05-10T17:00:09.513 回答