Scala:在可变序列中最快`remove(i:Int)`

Question

scala.collection.mutable如果我打算remove(i: Int)在单线程环境中进行大量的索引删除操作,我应该从包中实现哪个实现？最明显的选择是,ListBuffer它可能需要线性时间,具体取决于缓冲区大小.log(n)此操作是否有一些收集甚至是恒定的时间？

Answer 1

移除运营商,包括buf remove i,不属于Seq,但它实际上是Buffer特征的一部分scala.mutable.(见缓冲区)

请参见第一个性能特征表.我猜测buf remove i具有相同的特性的插入,这对于线性ArrayBuffer和ListBuffer.正如Array Buffers中所记录的那样,它们在内部使用数组,而Link Buffers使用链表(它仍然是O(n)用于删除).

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

载体表示为具有高分支因子的树.每个树节点最多包含32个向量元素或最多包含32个其他树节点.[...]因此,对于所有合理大小的向量,元素选择涉及最多5个基本数组选择.当我们写出元素访问是"有效的恒定时间"时,这就是我们的意思.

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)

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