问题添加元素到向量的末尾

Scaladocs 解释如何向Vector添加元素。

def :+(elem: A): Vector[A]
[use case] A copy of this vector with an element appended.

例：

scala> Vector(1,2) :+ 3
res12: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3)

对于大型集合，复制整个Vector，然后向其添加元素似乎很昂贵。

将元素添加到Vector的最佳（最快）方法是什么？

6521

2017-09-10 16:24

起源

与不可变向量的连接是O（logN）。看看这篇论文，看看它是如何完成的。

2017-09-10 16:29

这不可能是正确的。看到这个 docs.scala-lang.org/overviews/collections/...。附加是“eC” - Programmer

@Programmer你读过这篇论文吗？ 6.结论“基于RRB树的向量为Clojure和Scala中使用的现有32向不可变向量提供了可行的扩展，以提供O（logN）级联和分裂，同时保持与其他操作相关的基本成本。出于实际目的，它们可以算是不变的时间。“ - David Holbrook

与不可变向量的连接是O（logN）。看看这篇论文，看看它是如何完成的。

2017-09-10 16:29

这不可能是正确的。看到这个 docs.scala-lang.org/overviews/collections/...。附加是“eC” - Programmer

如果你要做很多追加，你应该使用一个队列，因为它保证了恒定的时间追加。有关集合的时间复杂性的信息，您可以参考此备忘单。

2017-09-10 16:36

在Scala中附加到向量需要有效的恒定时间。在复制许多数据结构的意义上复制向量，而不是将所有元素复制到新向量中。有关集合的时间复杂性的更多信息，请参阅coltfred提供的链接：

2017-09-11 17:23

问题 添加元素到向量的末尾