8

次の Java コードを検討してください (完全、コンパイル、および正常に実行されます)。

このコードは、5,000,000 個の整数 (100 万から 500 万) を含む配列を作成し、それをループして、検出した完全平方の ArrayList を作成します。完全な正方形は、ビット操作ではなく単純な手法を使用して検出されますが、それは当面の問題の焦点では​​ありません。

数学的には、1 ～ 5M の間に 2236 個の完全な正方形があります。したがって、完全な正方形が配置される ArrayList の最終的なサイズは 2236 になります。

import java.util.ArrayList;

public class PerfSquares {

    public static ArrayList<Integer> perfectSquares(int[] arr) {
        ArrayList<Integer> al = new ArrayList<Integer>();
    //  ArrayList<Integer> al = new ArrayList<Integer>(arr.length);

        for (int i = 0; i < arr.length; i++) {
            double root = Math.sqrt(arr[i]);
            int irt = (int) Math.floor(root);
            if (irt * irt == arr[i]) {
                al.add(arr[i]);
            }
        }
        return al;
    }

    public static void main(String[] args) {
        int[] arr = new int[5000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i + 1;
        }

        long s = System.currentTimeMillis();
        perfectSquares(arr);
        long e = System.currentTimeMillis();
        System.out.println(e - s);
    }
}

ArrayList の宣言に注目したいと思います。次の 2 行。そのうちの 1 行はコメント アウトされています。

  ArrayList<Integer> al = new ArrayList<Integer>();
//ArrayList<Integer> al = new ArrayList<Integer>(arr.length);

最初の宣言 (明示的に指定されたサイズなし) で実行すると、表示される timediff は次のようになります。

~96 milliseconds.

2 番目の宣言 (明示的に指定されたサイズ) で実行すると、 timediff は次のように増加します。

~105 milliseconds

質問：

なぜこのような振る舞いになるのでしょうか? 2 番目のケース (指定されたサイズ) の方が速いのではないでしょうか?

私の理解によると、最初のケースでは、ArrayList の作成で size パラメータを省略すると、バックグラウンドで長さ 10 の配列が初期化されます。そして、この容量を超えると、より大きな容量 (どれだけ大きいかは不明) の新しい配列が割り当てられ、以前の要素がコピーされます。

2236 要素で初期サイズが指定されていない場合、この「上限を超えた - 新しい割り当て - コピーオーバー - 上限までさらに追加」のサイクルが何度も繰り返され、速度が低下します。

その結果、指定されたサイズの宣言がより高速になることを期待していました-割り当てが1回行われ、容量を超える/新しい配列の作成とコピーオーバーが発生しないためです。

それとも、2236 が ArrayList に追加されるため、cap-exceeds-copy-over サイクルがすべて発生しても、サイズ 5,000,000 の ArrayList を作成するよりも高速になるため、これは基本的にそうですか?

4

4 に答える 4

6

500 万の配列リストを作成しているので、明らかに遅くなります。必要なのは 2236 だけです。これはかなりの無駄です。

たとえば、配列リストのサイズを 10k に変更すると、時間差が縮小することがわかります。

簡単にするために、このテストをさまざまな順序で複数回試してみてください -

public static void main(String[] args) {

   long timea = System.currentTimeMillis();

   // ArrayList<Integer> al = new ArrayList<Integer>();
   ArrayList<Integer> al = new ArrayList<Integer>(5000000);


    System.out.println(System.currentTimeMillis() - timea);

}

配列リストを 500 万に初期化するのに (私の macbook では) 約 10 ミリ秒かかりますが、デフォルト サイズのない配列リストはほぼ瞬時に完了します。これは、どの順序でテストしても同じです。

于 2013-10-28T12:35:45.890 に答える
2

まず第一に、あなたの測定方法には欠陥があります。ただし、このような状況下では、測定は容易ではありません。なぜなら、このような大きな配列割り当てがあると、後続の new が遅くなる可能性があるためです。

あなたの問題に関しては、メモリの割り当て（さらには割り当て解除）は高価な操作です。使用するときではありませんnew-最近のvmは、多くの小さな短命のオブジェクトに対して非常に最適化されています-しかし、ほとんどの場合、JVMがmalloc()下位のシステムレベルでメモリを予約/割り当て(別名)する必要があります。さらに、メモリ割り当て時間は、割り当てられたメモリの量にも依存します。必要なメモリが多いほど、時間がかかります。

あなたの場合：完全な正方形の量は、AFAIRで簡単に計算できます。を使用(Math.sqrt(arr.length) + 1)して初期ArrayListサイズを決定し、すぐに正確なサイズを取得します。

于 2013-10-28T13:16:25.410 に答える
1

メモリ割り当ては一般に低速な操作であるためです。どちらの場合も、割り当て数と新しい要素を数えました。

この場合

ArrayList<Integer> al = new ArrayList<Integer>();

合計で 8317 個の要素に対して 15 個の割り当てしかありません。そしてこの場合

ArrayList<Integer> al = new ArrayList<Integer>(arr.length);

5000000 要素の単一の割り当てがあります。

于 2013-10-28T12:46:01.227 に答える