java为什么是集合。addAll应该比c.addAll快

Question

下面的Java API docs say是关于Collections.addAll

The behavior of this convenience method is identical to that of c.addAll(Arrays.asList(elements)), but this method is likely to run significantly faster under most implementations.

因此，如果我理解正确，a）比b）慢：

（a）

Collection<Integer> col = new ArrayList<Integer>();
col.addAll(Arrays.asList(1, 2, 3, 4, 5));

b）

Collection<Integer> col = new ArrayList<Integer>();
// Collections.addAll(col, Arrays.asList(1, 2, 3, 4, 5)); <-- won't compile
Collections.addAll(col, 1, 2, 3, 4, 5);

谁能解释一下为什么会这样

编辑： 更正了代码示例。thx到polygenelubricants

Answer 1

以下是@Polygene所述每个步骤的（近似）相关时间复杂度成本函数：

a）参数列表上的3次迭代~=C（3N）

b）参数列表上的2次迭代~=C（2N）

显然，它们都是O（N），但方法b）比方法a）节省了~N个比较。希望这对任何对定量解释感兴趣的人都有帮助

Answer 2

让我们仔细看看它们中的两个：

// a)
col.addAll(Arrays.asList(1, 2, 3, 4, 5));

下面是发生的情况：

1. varags+autoboxing创建Integer[]
2. Arrays.asList创建由数组支持的List<Integer>
3. addAll使用Iterator<Integer>在Collection<Integer>上迭代

// b)
Collections.addAll(col, 1, 2, 3, 4, 5);

下面是发生的情况：

1. varargs+autoboxing创建Integer[]
2. addAll迭代数组（而不是Iterable<Integer>）

我们现在可以看到b)可能更快，因为：

• ^跳过{}调用，即不创建中介{}
• 由于元素是在一个数组中给出的（多亏了varargs机制），因此对它们进行迭代可能比使用^{}更快

这就是说，除非分析结果另有说明，否则这种差异不太可能“显著”。不要过早优化。虽然Java集合框架类可能比数组慢，但对于大多数应用程序来说，它们的性能远远不够

API链接

• ^{}-varargs即基于数组的
• ^基于{a3}-Collection

另见

• Java Language Guide/Autoboxing
• Java Language Guide/Varargs
• 有效Java第二版，第25项：更喜欢列表而不是数组

相关问题

• Array or List in Java. Which is faster ?

---

总结

• 如果要从数组中添加元素，可以使用Collections.addAll(col, arr)
  • 请记住，vararg也是使用数组完成的
• 如果要从Collection添加元素，请使用col.addAll(otherCol)
  • 不要这样做，例如Collections.addAll(col, otherCol.toArray())
    • 这种迂回的方式可能会更慢
• 这并不是说一个比另一个快得多
  • 考虑到目前的情况，这是关于跳过不必要的步骤

Answer 3

它可能更快的唯一原因是它避免了对数组的调用。asList应该相对便宜，因为它只是包装数组。一些集合实现，例如LinkedList，在添加元素之前将传递的集合转换回数组，从而导致额外的开销

另一方面，ArrayList。addAll在添加任何元素之前分配所需的空间一次，因此在收集时应该更快。addAll需要多次调整备份阵列的大小

总之，收藏。如果只向集合中重复添加几个元素，addAll可能会更快，但我怀疑这种情况是否会成为性能瓶颈

Answer 4

（让我们以SE平台6为基础）

这完全取决于实际的收集实现。在你的例子中，我们有

Collection<Integer> col = new ArrayList<Integer>();

并且ArrayList中的addAll方法被重写。没有迭代。 以下是消息来源：

public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
    int numNew = a.length;
ensureCapacity(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
return numNew != 0;
}

正如您可能注意到的c.toArray()也取决于实际的实现。同样，在您的例子中Arrays.asList()会导致ArrayList哪个版本的toArray()方法是这样的：

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

这种静态方法基于System.arraycopy

所以实际上我们在这里处理的是System.arraycopy的两个调用，这其实并不坏，因为它是一个本机方法，专门针对当前的操作系统进行了优化

所以，用Polygene先生的风格总结一下：

1. varags+autoboxing创建Integer[]
2. Arrays.asList创建一个ArrayList<Integer>
3. ArrayList.addAll调用System.arraycopy(size)x2，大小=5

在数组中有5个对象的情况下Collections.addAll会更快。但与如此小的数组大小无关。另一方面，如果它是一个数组中的100k元素，那么col.addAll(Arrays.asList(...))效率要高得多，因为对于本机方法，它是我们处理的单个memcpy/memmove，而不是100k迭代/复制操作

同样，这一切都取决于集合的实现^例如，{}将按预期对其进行迭代