为什么collections.addall应该比c.addall快

让我们仔细看看其中两个:

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

以下是发生的事情:

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

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

以下是发生的事情:

1. varargs+自动氧化创建 整数[ ]
2. 阿达尔 迭代数组(而不是 Iterable<Integer> )

我们现在可以看到 b) 可能更快,因为:

• 阿拉斯 跳过呼叫,即没有中间人 List 创建。
• 由于元素是在数组中给定的(这要归功于varargs机制),因此对它们的迭代可能比使用 Iterator .

这就是说,除非分析显示出其他情况,否则差异不大可能是“显著的”。不要过早优化。虽然Java集合框架类可能比数组慢,但它们对大多数应用程序执行得远远不够。

API链接

• Collections.addAll(Collection<? super T> c, T... elements) -varargs,即基于数组的
• Collection.addAll(Collection<? extends E> c) - Collection 基于

也见

• Java Language Guide/Autoboxing
• Java Language Guide/Varargs
• 有效Java第二版,项目25:喜欢列表到数组

相关问题

• Array or List in Java. Which is faster ?

总结

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

它可能更快的唯一原因是,它避免了对array.aslist的调用,因为它只是包装了数组,所以调用成本相对较低。一些集合实现(例如LinkedList)在添加元素之前将传递的集合转换回数组,从而导致额外的开销。

另一方面,arraylist.addall在添加任何元素之前只分配一次所需的空间,因此当collections.addall需要对支持数组进行多次调整时,应该更快。

总之,当只向集合中重复添加几个元素时,collections.addall可能更快,但我怀疑这种情况是否会成为性能瓶颈。

(让我们在SE平台6上构建)

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

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

和 addAll 方法在 ArrayList 被推翻。没有任何迭代。 资料来源如下:

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() 结果在 数组列表 哪个版本的 toArray() 方法如下:

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

此静态方法基于 System.arraycopy

所以实际上我们这里要处理的是两个电话 系统.arraycopy 这并没有那么糟糕,因为它是一种本机方法,专门针对当前操作系统进行了优化。

所以,总结一下Polygene润滑剂先生的风格:

1. varags+自动氧化创建 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迭代/复制操作。

而且,这一切都取决于集合的实现。 LinkedList 例如,将按预期对其进行迭代。

以下是@polygeneulates提到的每个步骤的(近似)相关时间复杂度成本函数:

a)参数列表上3次迭代~=c(3n)

b)参数列表上2次迭代~=c(2n)

很明显,它们都是O(N),但是方法B比方法A节省了~n个比较。希望这对任何对定量解释感兴趣的人都有帮助。