Java Arraylist大小声明和性能

Question

考虑以下Java代码(完成,编译并运行正常).

代码创建一个包含5,000,000个整数(1到5百万)的数组,在其上循环,并创建一个找到的完美正方形的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的声明.这两行,其中一行被注释掉:

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

当我运行第一个声明(没有明确提供的大小)时,我看到的timediff是:

~96 milliseconds.

当我与所述第二声明运行(与大小显式提供),timeDiff测量增大到:

~105 milliseconds

---

题:

为什么会出现这种情况？第二种情况(提供的尺寸)不应该更快吗？

根据我的理解,在第一种情况下,当我们省略了ArrayList创建的size参数时,在幕后将初始化一个长度为10的数组.当超过此容量时,将分配具有更大容量(不确定更大)的新阵列,并且将复制先前的元素.

对于2236个元素并且没有指定初始大小,这个"超出限额 - 分配新 - 复制超过 - 附加更多直到上限"循环应该重复多次,减慢它.

因此,我期望提供的大小声明更快 - 因为分配将发生一次,并且没有容量超出/新阵列创建和复制发生.

或者这基本上是因为2236附加到ArrayList,即使所有的cap-over-copy-over周期,仍然比创建大小为5,000,000的ArrayList更快？

Answer 1

你创造了一个500万的arraylist,所以显然它更慢.你只需要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);

}

您会看到将一个arraylist初始化为500万左右需要大约10毫秒(在我的macbook上),而没有默认大小的arraylist几乎是瞬间完成的.这与您测试的订单无关.