3

Scala 中是否有一种从 ListBuffer 中删除多个索引的好方法（以快速的方式）？

例子：

val indicesToDelete = List(4, 1)
val buffer = ListBuffer(a, b, c, d, e)

结果：

ListBuffer(b, c, e)

我找不到可以完成这项工作的预定义函数。

可以对索引进行排序并删除以最高索引等开头的元素，因此不会有任何复杂性。但排序需要O(n * log n). 有没有更快的方法（也许我错过了一些预定义的东西）？

更新 1：应删除现有 ListBuffer 对象中的元素，不应创建新的 ListBuffer 对象。

4

4 回答 4

6

您必须使用zipWithIndex，就像其他帖子已经使用的那样，因为否则索引会发生变化，您可能会意外删除错误的项目。但是我会使用foldLeftor而不是filter+ ，在这种情况下，它的作用与+相同，但只需一步。mapcollectfiltermap

buffer.zipWithIndex.collect { case (x,i) if !indicesToDelete.contains(i) => x }

这也可以写成

for {
  (x,i) <- buffer.zipWithIndex
  if !indicesToDelete.contains(i)
} yield x
于 2012-07-12T10:03:15.447 回答
5

与其他人不同，我将假设您想就地完成工作，因为您提到了对索引重新编号的担忧。如果排序是你所关心的那么

1）将要删除的索引粘贴到恒定时间查找集而不是列表中。根据索引的范围，散列集或位集似乎是合适的。2) 以相反的顺序遍历列表缓冲区，删除待删除集中的索引。

scala> val buffer = ListBuffer("a", "b", "c", "d", "e")
buffer: scala.collection.mutable.ListBuffer[java.lang.String] = ListBuffer(a, b, c, d, e)

scala> val indicesToDelete = BitSet(4, 1)
indicesToDelete: scala.collection.mutable.BitSet = BitSet(1, 4)

scala> for (i <- (buffer.size -1) to 0 by -1) if (indicesToDelete contains i) buffer remove i

scala> buffer
res19: scala.collection.mutable.ListBuffer[java.lang.String] = ListBuffer(a, c, d)

请注意，虽然这会删除 n log n 类型的索引，但这并不能使其成为线性算法。从类似数组的结构中就地删除并不便宜。每次删除都必须向下复制更高的索引。

要获得索引的线性删除，您需要做一些更复杂的事情，您需要 1) 向前走，根据您迄今为止删除的数字向下复制未删除的元素。完成后 2) 删除前 n 个元素，其中 n 是您删除的数字。

scala> val buffer = ListBuffer("a", "b", "c", "d", "e")  
buffer: scala.collection.mutable.ListBuffer[java.lang.String] = ListBuffer(a, b, c, d, e)

scala> val indicesToDelete = BitSet(4, 1)
indicesToDelete: scala.collection.mutable.BitSet = BitSet(1, 4)

scala> var deleted = 0
deleted: Int = 0

scala> for (i <- 0 until buffer.size)
     |    if (indicesToDelete contains i) {
     |       deleted += 1
     |    } else if (deleted > 0) {
     |        buffer(i - deleted) = buffer(i)
     |    }

scala> }

scala> buffer trimEnd deleted

scala> buffer
res0: scala.collection.mutable.ListBuffer[java.lang.String] = ListBuffer(a, c, d)
于 2012-07-12T15:01:22.790 回答
3

怎么样：

buffer.zipWithIndex.filter( p => !(indicesToDelete contains p._2) ).map( _._1 )

里面的数字在O(NM)哪里，里面的元素个数。NbufferMindicesToDelete

如果你关心性能，你总是可以制作indicesToDelete一个Set. 在这种情况下，性能是O(N)：假设O(1)为 HashSet 或O(NlogM)为TreeSet.

并整理其他海报中的所有好主意：

buffer.view.zipWithIndex.collect { case (x,i) if !indicesToDelete.contains(i) => x }

只为您提供一次数据。

于 2012-07-12T09:38:19.917 回答
0 
import collection.mutable.ListBuffer

val indicesToDelete = List(4, 1)
val buffer = ListBuffer('a', 'b', 'c', 'd', 'e')

def exclude[T](l:ListBuffer[T], indice: List[Int]) = {
  val set = indice.toSet
  l.zipWithIndex.foldLeft(ListBuffer.empty[T]){ case (c, next) =>
    if(set(next._2+1)) c else c :+ next._1
  } 

}

exclude(buffer, indicesToDelete)
于 2012-07-12T09:46:26.567 回答