5

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

4

3 回答 3

8

删除运算符，包括buf remove i，不是 的一部分Seq，但它实际上是Buffertrait的一部分scala.mutable。（见缓冲区）

请参阅关于性能特征的第一个表。我猜想具有与 insert 相同的特性，对于和buf remove i都是线性的。如Array Buffers中所述，它们在内部使用数组，而Link Buffers使用链表（删除仍然是 O(n)）。ArrayBufferListBuffer

作为替代方案，不可变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)

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

于 2010-12-14T17:29:15.407 回答
1

根据您的具体用例，您可以使用LinkedHashMapfrom scala.collection.mutable。

虽然不能按索引删除，但可以在恒定时间内按唯一键删除，并且在迭代时保持确定性排序。

scala> val foo = new scala.collection.mutable.LinkedHashMap[String,String]
foo: scala.collection.mutable.LinkedHashMap[String,String] = Map()

scala> foo += "A" -> "A"
res0: foo.type = Map((A,A))

scala> foo += "B" -> "B"
res1: foo.type = Map((A,A), (B,B))

scala> foo += "C" -> "C"
res2: foo.type = Map((A,A), (B,B), (C,C))

scala> foo -= "B"
res3: foo.type = Map((A,A), (C,C))
于 2010-12-18T23:36:37.077 回答
1

ArrayList如果最后一个元素是要删除的元素，Java 的有效时间复杂度是恒定的。查看从其源代码复制的以下片段，

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

如您所见，如果numMoved等于 0，remove则根本不会移动和复制数组。这在某些情况下可能非常有用。例如，如果您不太关心顺序，要删除一个元素，您可以随时将其与最后一个元素交换，然后从 中删除最后一个元素ArrayList，这有效地使remove操作一直保持恒定时间。我希望ArrayBuffer能做同样的事情，不幸的是事实并非如此。

于 2019-08-28T15:13:57.350 回答