Java的ArrayList的尺寸申报和性能 [英] Java Arraylist size declaration and performance

问题描述

考虑下面的Java code（完整，编译并运行良好）。

Consider the following Java code (complete, compiles and runs fine).

在code创建了一个包含500万整数（1 500万）的阵列，循环遍历它，并创建它找到了完美的正方形的ArrayList。用天真的技术检测完美的正方形，而不是位操作，而不是眼前的问题的焦点。

The code creates an array containing 5,000,000 integers (1 to 5 million), loops over it, and creates an ArrayList of the perfect squares it finds. Perfect squares are detected using a naive technique, and not bit manipulation, but that is not the focus of the issue at hand.

在数学上，1和5M之间，有2236完美的正方形。这样完美的正方形被放进ArrayList的将有2236最终尺寸。

Mathematically, between 1 and 5M, there are 2236 perfect squares. So the ArrayList that the perfect squares are being put into will have a final size of 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的声明。这两条线，其中一个被注释掉：

---

I'd like to focus on the declaration of the ArrayList. These two lines, one of which is commented out:

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

当我第一次申报运行（无明确提供的大小），我看到了timeDiff的是：结果

When I run with the first declaration (without the size explicitly supplied), the timediff I see is:

~96 milliseconds.

在我的第二个声明（与的尺寸显式提供），在timeDiff的增加运行：

When I run with the second declaration (with the size explicitly supplied), the timediff increases to:

~105 milliseconds

---

问：

为什么这种行为呢？不应该第二种情况（大小提供）更快？

按我的理解，在第一种情况下，当我们省略该参数到ArrayList创作，幕后长度为10的数组将被初始化。而超过此容量时，容量更大的新数组（不知道有多少大）将被分配和previous元素将被复制。

As per my understanding, in the first case, when we omit the size parameter to the ArrayList creation, behind the scenes an array of length 10 will be initialized. And when this capacity is exceeded, a new array with a larger capacity (not sure how much larger) will be allocated, and the previous elements will be copied over.

有关规定正在2236元，无初始大小，这种超出上限 - 分配新的 - 拷贝过来 - 追加更多直到帽。周期应该重复很​​多次，减缓下来。

For 2236 elements and no initial size being specified, this "cap exceeded - allocate new - copy over - append more till cap" cycle should repeat many times, slowing it down.

因此​​，我期待所提供的尺寸申报要快 - 由于分配将发生一次，而且也不会有能力超过了发生的事情/新阵列的创建和复制

Consequently, I was expecting the size supplied declaration to be faster - Since the allocation will happen once, and there will be no capacity exceeding / new array creation and copying over happening.

还是这主要是因为2236年追加到一个ArrayList，即使所有的帽超出复制悬停周期，仍然会比创建大小5,000,000一个ArrayList快？

Or is this basically so because 2236 appends to an ArrayList, even with all the cap-exceeds-copy-over cycles, will still be faster than creating an ArrayList of size 5,000,000?

推荐答案

您正在创建的500万的ArrayList，那么清楚它的速度较慢。你只需要2236这是很多的浪费。

You're creating an arraylist of 5 million, so clearly it's slower. You only need 2236. That's alot of waste.

如果你改变你的数组列表的大小为10k比如你会看到时间差收缩。

If you change the size of your array list to 10k for example you'll see the time difference shrink.

要更简单，只是尝试这个测试，多次在不同的顺序 -

To make it simpler, just try this test, multiple times, in different orders -

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），而一个没有默认大小为pretty很多瞬间。这是相同的，其母校命令你测试。

You'll see that initialising an arraylist to 5 million takes around 10ms (on my macbook), while the one with no default size is pretty much instantaneous. This is the same no mater which order you test.

这篇关于Java的ArrayList的尺寸申报和性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！