函数ArrayList.add()运行非常快。我检查了源代码，发现工具是Arrays.copyOf()
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
但是，当我在代码中使用方法
Arrays.copyOf()时，它变得非常慢。您可以运行下面的代码以查看它：public class TestArrayCopy {
public static void main(String[] args) {
long t = System.currentTimeMillis();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list.add(i, i);
}
System.out.println(System.currentTimeMillis() - t);
t = System.currentTimeMillis();
Integer[] array = new Integer[0];
for (int i = 0; i < 100000; i++) {
array = Arrays.copyOf(array, array.length +1);
array[i] = i;
}
System.out.println(System.currentTimeMillis() - t);
}
}
有任何想法吗？
最佳答案
每次添加新元素时，您的代码都会调用copyOf()：
第一次，不需要复制任何元素，因为原始数组的长度为0。
第二次，必须复制一个元素。
第三次，两个要素。
第四次，三个要素。
...等等。
因此，对于添加的每个元素，您都必须花费越来越多的工作来复制先前的元素。因此，如果要添加n元素，则必须对单个元素执行总计1 + 2 + 3 + ... + (n - 1) = n * (n - 1) / 2 = n^2 / 2 - n / 2复制。因此，您的运行时与所添加元素数量的平方成正比。
将此与适当的方法进行对比，该方法具有的阵列要比您需要的大（这使您有足够的空间添加更多元素而无需始终复制），并且每次需要扩展时将大小乘以固定因子。这要求您分别跟踪已添加的元素数，并向用户撒谎以了解您的真实尺寸。该因子通常小于2（Java代码使用1.5：int newCapacity = oldCapacity + (oldCapacity >> 1);），但是如果使用2，则数学更简单：
初始数组大小是一些小但非零的数字，例如4，因此您可以免费添加4个元素（嗯，分配和初始化数组的成本实际上是4）
对于第五个元素，将大小翻倍至8，然后复制4个旧元素；您现在可以再添加4个
对于第九个元素，将大小翻倍至16，然后复制8个旧元素；您现在可以再添加8个
依此类推：对于第n + 1个元素，将大小加倍为2 * n并复制旧的n个元素，这将为您提供更多n个元素的空间。
即使不评估复制的总和，我们也可以看到，每批n个新元素都已经被前n个元素的复制“支付”了，因此复制工作是线性的，而不是二次的。实际上，4 + 4 + 8 + 16 + ... + n / 2 + n = 2 * n（如果n是2的幂）。
关于java - 为什么Arrays.copyOf这么慢？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53945602/