java - 在巨大的ArrayList中添加元素会暂时停止

Question

当我调试具有巨大计算任务的程序的性能时，我发现向大ArrayList添加元素的大部分时间都是通过添加1个元素来占用的。谁能解释一下为什么会发生这样的事情？

import java.util.ArrayList;

public class MainArr {
    ArrayList<Integer> normalList = new ArrayList<Integer>();

    public static void main(String[] args) {
        MainArr m = new MainArr();
        m.addElements();
    }

    public void addElements() {
        long startTime = System.currentTimeMillis();
        for (int j = 0; j < 20000000; j++) {
            long addTime = System.currentTimeMillis();
            this.normalList.add(j);
            if (System.currentTimeMillis() - addTime > 50) {
                System.out.println("slow index-" + j + " - time:" + (System.currentTimeMillis() - addTime));
            }
        }
        System.out.println("End after:" + (System.currentTimeMillis() - startTime));
    }
}

输出(始终相同的索引和时间):

slow index-4102267 - time:1184
slow index-6758091 - time:1444
slow index-12459620 - time:3124
slow index-14738741 - time:166
End after:6651

Answer 1

From the documentation :

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

因此，在底层，ArrayList 是一个固定大小的数组，当它变满时，它会被复制和替换。因此，慢速索引标记处发生的情况是 ArrayList 必须重新分配一个新的内部数组并将旧数组复制到新数组中。

如果您想要加速，并且您大致知道 ArrayList 将有多大(如您的示例中所示)，请使用 ArrayList constructor它允许您指定初始数组大小。

ArrayList<Integer> normalList = new ArrayList<>(20000000);

编辑 - 新答案:

通过上述答案，我得到了与@MichalLis相同的性能，所以我做了一些研究，然后发现了不同的答案。

如果您采用示例代码并将 ArrayList 替换为普通的旧 int[] 数组，则程序会输出:

End after:2263

然后我用 Integer[] 数组替换了 int[] 数组，得到了这个:

slow index-4022087 - time:2012
slow index-8150728 - time:948
slow index-14442110 - time:4886
End after:10309

事实证明，由于 ArrayList 实际上不能使用 int 而必须使用 Integer，因此创建新的数组会对性能产生影响对象。 int 比 Integer 快得多，因为前者是基本类型，而后者是包装对象。

如果您希望获得 int[] 的性能优势以及 ArrayList 的调整大小功能，您始终可以实现自己的 ArrayList专门用于 int 的类。

public class IntArrayList {

    int[] array = new int[10];
    int size = 0;

    public int get(int index){
        return array[index];
    }

    public void add(int value){
        if(size == array.length){
            resizeArray();
        }
        array[size] = value;
        size++;
    }

    private void resizeArray(){
        int[] newArray = new int[array.length * 2];
        for(int i=0; i<array.length; i++){
            newArray[i] = array[i];
        }
        array = newArray;
    }

    public void set(int index, int value){
        array[index] = value;
    }

    public int size(){
        return size;
    }

    public void remove(int index){
        for(int i=index; i<size-2; i++){
            array[i] = array[i+1];
        }
        size--;
    }
}

这不是一个非常强大的实现，但它是一个起点。

使用上述IntArrayList实现的OP代码的输出:

End after:2315