9

次のスニペットを参照してください。

    Long first_begin = System.currentTimeMillis();

    // first nested loops
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 1000000; j++) {
            // do some stuff
        }
    }
    System.out.println(System.currentTimeMillis() - first_begin);
    // second nested loops
    Long seconde_begin = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        for (int j = 0; j < 10; j++) {
            // do some stuff
        }
    }
    System.out.println(System.currentTimeMillis() - seconde_begin);

最初のネストされたループが2番目のループよりも遅く実行されているのはなぜですか？

よろしく！

重要な注意点！：この質問を最初に行ったときに、誤って1で始まる変数jを作成してしまったことをお詫び申し上げます。修正しました。

更新：ループ内に特定のロジックはありません。テストを行っているだけです。実際、これはインタビュー中に尋ねられた質問であり、インタビュアーは、パフォーマンスを向上させるためにループの順序を変更するように促します。ところで、私はJDK1.5を使用しています。いくつかのテストの後、プログラムの結果に一貫性がないため、今はもっと混乱しています---最初のループは2番目のループよりも速く実行されることもありますが、ほとんどの場合、2番目のループよりも遅く実行されます。

4

4 に答える 4

6

この回答は、更新された質問に対するものです。

  • などの 2 次元配列にアクセスしている場合int[][]、内側のループで値が大きい方が遅くなるはずです。それほどではありませんが、それでも。この問題をある程度理解するには、Joel のブログ投稿の 1 つで、ストリート ペインターの Shlemielについて読んでください。
  • 一貫性のない結果が得られる理由は、JVM ウォームアップを実行していないためです。JVM は、実行されるバイトコードを常に分析して最適化し、通常は 30 ～ 50 回の反復後にのみ最適な速度で実行されます。はい、これは、コードを最初に数十回実行してから、数回の実行が遅くなるガベージコレクターのために、さらに数十回の実行の平均からベンチマークする必要があることを意味します。
  • 一般的な注意として、プリミティブLongの代わりにオブジェクトを使用するのlongは馬鹿げているだけです.JVMは、可能な場合はプリミティブに置き換えることで最適化する可能性が高く、できない場合は、それを使用すると一定の速度低下が発生します.
于 2010-03-31T07:47:19.517 に答える
6

編集：元の回答は以下です。すべてのループ変数が 0 から始まるように例を修正したので、単純に十分な情報がない状態に戻りました。キャッシュの一貫性/参照の局所性の問題である可能性が高いようですが、推測にすぎません。問題を示す短いが完全なプログラムを提供できれば、それは役に立ちます...どの言語/プラットフォームから始めればよいかを教えてくれます!

最初のループには 10 * 999999 = 9999990 回の反復があります。2 番目のループには、1000000 * 9 = 9000000 回の反復があります。したがって、 (他のすべての条件が同じであれば) 最初のループに時間がかかると予想されます。

ただし、どのような作業を行っているか、またはこれがどのプラットフォーム上にあるかを示していません。物事に影響を与える可能性のある多くのことがあります：

  • 2 番目のループの方がキャッシュにヒットする可能性があります
  • JIT でコンパイルされたプラットフォームを使用している場合、JIT は 2 番目のループをより重点的に最適化することを選択した可能性があります。
  • 実行している操作自体にキャッシュなどがある場合があります
  • 少量の作業を実行しているが、最初に一連の型をロードして初期化する必要がある場合、最初のループが遅くなる可能性があります
于 2010-03-31T06:14:17.533 に答える
2

質問は変わりました。これらはあなたが求めるドロイドではありません...

最初の例では、最大1000000倍の作業を行っているためです。;-)

于 2010-03-31T06:07:41.623 に答える
2

生成されたバイト コードを見ると、2 つのループはほとんど同じです。ただし、10 ループの while 条件を実行すると、Java は命令内から即値として 10 を取得しますが、1000000 ループの while 条件を実行すると、Java は変数から 1000000 をロードします。各命令の実行にかかる時間に関する情報はありませんが、変数からのロードよりも即時のロードの方が高速になる可能性があります。

次に、最初のループでは 1000000 との比較を 1000 万回行う必要がありますが、2 番目のループでは 100 万回しか行わないことに注意してください。もちろん、10 との比較は 2 番目のループではるかに頻繁に行われますが、可変負荷が即時負荷よりもはるかに遅い場合は、表示されている結果を説明できます。

于 2010-03-31T07:36:18.283 に答える