在巨大的 ArrayList 中添加元素会停止一段时间

debugcn 发表于 Dev

米哈尔·利斯

当我调试具有巨大计算任务的程序性能时，我发现向大 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

jpyams

从文档：

每个 ArrayList 实例都有一个容量。容量是用于存储列表中元素的数组的大小。它始终至少与列表大小一样大。当元素被添加到 ArrayList 时，它的容量会自动增加。除了添加元素具有恒定的摊销时间成本之外，没有指定增长政策的细节。

因此，在引擎盖下， anArrayList是一个固定大小的数组，当它变满时会被复制和替换。所以在你的slow index标记上发生的事情ArrayList是必须重新分配一个新的内部数组并将旧数组复制到新数组中。

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

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

编辑 - 新答案：

通过上述答案，我获得了与 @MichalLis 相同的性能，因此我做了一些研究，并找到了不同的答案。

如果您使用示例代码并将替换为ArrayList一个普通的旧int[]数组，程序会吐出：

End after:2263

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

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

事实证明，由于 anArrayList实际上不能使用ints 而必须使用Integers，因此创建新对象会对性能产生影响。ints 比Integers快得多，因为前者是原始类型，而后者是包装对象。

如果您希望 an 的性能优势和 anint[]的大小调整能力ArrayList，您始终可以ArrayList专门为ints实现自己的类。

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 代码输出：