Java 为什么 Collections.addAll 应该比 c.addAll 快

Why is Collections.addAll supposed to be faster than c.addAll

提问by dertoni

The Java API docs saythe following about Collections.addAll

在Java的API文档说以下有关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.

此便捷方法的行为与 c.addAll(Arrays.asList(elements)) 的行为相同，但在大多数实现中，此方法的运行速度可能会明显加快。

So if I understand correctly, a) is slower than b):

所以如果我理解正确的话，a) 比 b) 慢：

a)

一种）

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

b)

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);

Can anyone explain to me, why that is?

谁能给我解释一下，这是为什么？

edited: corrected code example. thx to polygenelubricants

编辑：更正的代码示例。感谢多基因润滑剂

采纳答案by polygenelubricants

Let's take a closer look at the two of them:

让我们仔细看看他们两个：

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

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

Here's what happens:

这是发生的事情：

1. varags + autoboxing creates Integer[]
2. Arrays.asListcreates a List<Integer>backed by the array
3. addAlliterates over a Collection<Integer>using Iterator<Integer>

1. varags + 自动装箱创建 Integer[]
2. Arrays.asList创建一个List<Integer>由数组支持的
3. addAll迭代Collection<Integer>使用Iterator<Integer>

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

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

Here's what happens:

这是发生的事情：

1. varargs + autoboxing creates Integer[]
2. addAlliterates over an array (instead of an Iterable<Integer>)

1. 可变参数 + 自动装箱创建 Integer[]
2. addAll迭代一个数组（而不是一个Iterable<Integer>）

We can see now that b)may be faster because:

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

• Arrays.asListcall is skipped, i.e. no intermediary Listis created.
• Since the elements are given in an array (thanks to varargs mechanism), iterating over them may be faster than using Iterator.

• Arrays.asList调用被跳过，即没有List创建中介。
• 由于元素在数组中给出（感谢 varargs 机制），迭代它们可能比使用Iterator.

That said, unless profiling shows otherwise, the difference isn't likely to be "significant". Do not optimize prematurely. While Java Collection Framework classes may be slower than arrays, they perform more than adequately for most applications.

也就是说，除非分析另有说明，否则差异不太可能“显着”。不要过早优化。虽然 Java Collection Framework 类可能比数组慢，但它们对于大多数应用程序来说已经足够了。

API links

接口链接

• Collections.addAll(Collection<? super T> c, T... elements)- varargs i.e. array-based
• Collection.addAll(Collection<? extends E> c)- Collection-based

• Collections.addAll(Collection<? super T> c, T... elements)- 可变参数，即基于数组
• Collection.addAll(Collection<? extends E> c)--Collection基于

See also

也可以看看

• Java Language Guide/Autoboxing
• Java Language Guide/Varargs
• Effective Java 2nd Edition, Item 25: Prefer lists to arrays

• Java 语言指南/自动装箱
• Java 语言指南/可变参数
• Effective Java 第 2 版，第 25 条：列表优先于数组

Related questions

相关问题

• Array or List in Java. Which is faster ?

• Java 中的数组或列表。哪个更快？

---

---

Summary

概括

• If you're adding elements from an array, you can use Collections.addAll(col, arr)
  • Remember that varargs are also done using arrays
• If you're adding elements from a Collection, use col.addAll(otherCol)
  • Do NOTe.g. Collections.addAll(col, otherCol.toArray())
    • Such roundabout way is likely to be slower!
• It's not that one is supremely faster than the other
  • It's about skipping unnecessary steps given the current situation

• 如果要从数组中添加元素，则可以使用 Collections.addAll(col, arr)
  • 请记住，可变参数也是使用数组完成的
• 如果要从 a 添加元素Collection，请使用col.addAll(otherCol)
  • 难道不是如Collections.addAll(col, otherCol.toArray())
    • 这种迂回的方式很可能会更慢！
• 并不是说一个比另一个快得多
  • 这是关于在当前情况下跳过不必要的步骤

回答by J?rn Horstmann

The only reason it might be faster is that it avoids the call to Arrays.asList which should be relatively cheap since it just wraps the array. Some Collection implementations, for example LinkedList convert the passed collection back to an array before adding the elements, causing additional overhead.

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

On the other hand, ArrayList.addAll allocates the needed space once before adding any elements and so should be much faster when Collections.addAll requires multiple resizing of the backing array.

另一方面，ArrayList.addAll 在添加任何元素之前分配一次所需的空间，因此当 Collections.addAll 需要多次调整支持数组的大小时应该更快。

In summary, Collections.addAll could be faster when repeatedly adding only a few elements to a collection, but I doubt that this case would ever be a performance bottleneck.

总而言之，Collections.addAll 在重复仅向集合添加几个元素时可能会更快，但我怀疑这种情况是否会成为性能瓶颈。

回答by adiosmsu

(Let's build on SE Platform 6)

（让我们在 SE Platform 6 上构建）

It all depends on actual collection implementation. In your example we have

这一切都取决于实际的集合实现。在你的例子中，我们有

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

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

and addAllmethod in ArrayListis overriden. No iterations whatsoever. Here's the source:

和addAll方法 inArrayList被覆盖。没有任何迭代。这是来源：

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;
}

As you might notice c.toArray()also depends on actual implementation. Again, in your case Arrays.asList()results in ArrayListwhich one's version of toArray()method looks like this:

正如您可能注意到的，c.toArray()还取决于实际实现。同样，你的情况Arrays.asList()的结果ArrayList，其中一个版的toArray()方法如下所示：

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

This static method is based on System.arraycopy

这种静态方法基于 System.arraycopy

So actually what we deal here with is two calls of System.arraycopywhich is not that bad actually because it's a native method, specifically optimized for current operation system.

所以实际上我们在这里处理的是两个调用，System.arraycopy实际上并没有那么糟糕，因为它是一个本地方法，专门针对当前操作系统进行了优化。

So, to sum it all up in Mr. polygenelubricants' style:

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

1. varags + autoboxing creates Integer[]
2. Arrays.asListcreates an ArrayList<Integer>
3. ArrayList.addAllcalls System.arraycopy(size)x2, size = 5

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

In your case of 5 objects in the array Collections.addAllis of cource faster. BUT irrelevant with such a small array size. On the other hand if it was, say, 100k elements in an array then col.addAll(Arrays.asList(...))is much more efficient 'cause with native method it is a single memcpy/memmove we dealing with as opposed to 100k iterations/copy operations.

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

And again, it all depends on collection's implementation. LinkedListfor example will iterate over it as was expected.

同样，这完全取决于集合的实现。LinkedList例如将按预期迭代它。

回答by tep

Here are the (approximate) associated time complexity cost functions for each of the steps mentioned by @polygenelubricants:

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

a) 3 iterations over arguments list ~= C(3N)

a) 对参数列表进行 3 次迭代 ~= C(3N)

b) 2 iterations over arguments list ~= C(2N)

b) 对参数列表进行 2 次迭代 ~= C(2N)

Clearly they are both O(N) but approach b) saves ~N comparisons over approach a). Hopefully this is helpful to anyone who was interested in a quantitative explanation.

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