性能 – Scala：可变序列中最快的`remove(i：Int)`

如果我打算在单线程环境中执行大量的by-index-deletions(如remove(i：Int)),我应该从 scala.collection.mutable包中执行哪个实现？最明显的选择 ListBuffer表示根据缓冲区大小可能需要线性时间.是否有一些带有log(n)或甚至是该操作的恒定时间的集合？ 删除运算符,包括buf remove i,不是Seq的一部分,但它实际上是scala.mutable下Buffer属性的一部分. (见 Buffers)

请参阅Performance Characteristics的第一个表.我猜buf remove我具有与insert相同的特性,它对于ArrayBuffer和ListBuffer都是线性的.
如Array Buffers中所述,它们在内部使用数组,而Link Buffers使用链接列表(仍然是O(n)用于删除).

作为替代方案,不可变的Vector可以为您提供有效的恒定时间.

Vectors are represented as trees with a high branching factor. Every tree node contains up to 32 elements of the vector or contains up to 32 other tree nodes. […] So for all vectors of reasonable size, an element selection involves up to 5 primitive array selections. This is what we meant when we wrote that element access is “effectively constant time”.

scala> import scala.collection.immutable._
import scala.collection.immutable._

scala> def remove[A](xs: Vector[A], i: Int) = (xs take i) ++ (xs drop (i + 1))
remove: [A](xs: scala.collection.immutable.Vector[A],i: Int)scala.collection.immutable.Vector[A]

scala> val foo = Vector(1, 2, 3, 4, 5)
foo: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5)

scala> remove(foo, 2)
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4, 5)

但请注意,在数据量非常大之前,具有大量开销的高常量时间可能无法获得快速线性访问.