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 秒のような時間がかかり、どちらも Samsung Galaxy Nexus で実行されていることです。

Android 用の Java での私の実装に、ベンチマークを遅くしている可能性のある明らかな問題がありますか?

ノート; 私は主に高速なアルゴリズムに切り替えるつもりはありませんが、Javascript (および iOS 用に作成した実装) が Android 用の Java での実装よりもはるかに高速である理由を理解しようとしています。

ラップトップで実行すると、Javascript よりも Java の方がはるかに高速に結果が得られます。

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 コードは 5 回実行され、JavaScript は 1 回だけ実行されます。

于 2013-05-10T17:00:09.513 に答える