java - 为什么 Arrays.copyOf 这么慢？

Question

函数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);
  }
}

有什么想法吗？

Answer 1

每次添加新元素时，您的代码都会调用 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 个
• 对于第9个元素，将大小加倍为16，并复制8个旧元素；您现在可以再添加 8 个
• 依此类推:对于第 n + 1 个元素，将大小加倍为 2 * n 并复制旧的 n 元素，这为您提供了容纳 n 个元素的空间。

即使不评估复制的总和，我们也可以看到每批 n 个新元素都已经通过复制前一个 n 元素“付出了代价”元素，因此复制工作是线性的而不是二次的。事实上，4 + 4 + 8 + 16 + ... + n/2 + n = 2 * n(如果n是2的幂)。 p>