如何从ListBuffer中删除多个索引（以快速方式）？

Question

有Scala中的一个很好的方式来删除从ListBuffer多个索引（在一个快速的方式）？

例子：

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

结果：

ListBuffer(b, c, e) 

我无法找到一个预先定义的功能，没有工作。

一个可以在指数排序和删除元素具有最高指数等开始，所以不会有并发症。但排序需要O(n * log n)。有没有更快的方法（可能是我错过的预定义）？

UPDATE 1：这些元素应该在现有的ListBuffer对象中删除，不应该创建新的ListBuffer对象。

Answer 1

不像其他人，我会假设你想，因为你提一个关于指数重新编号关注做你的就地工作。如果排序是所有你关心的则

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) 

Answer 2

如何：

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

这是O(NM)其中N为buffer的数量，M中indicesToDelete元素的个数。

如果你关心性能，你总是可以让indicesToDelete一个Set。在这种情况下，性能是O(N）：假定O(1)用于为TreeSet一个HashSet或O(NlogM)摊销查找。

和整理从其他海报所有的好想法：

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

给你一个传过来只有数据。

Answer 3

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) 

Answer 4

你必须使用zipWithIndex，因为其他职位已经这样做，否则指数将转移，你可能会不小心删除错误的项目。但不是foldLeft或filter + map我会用collect，在这种情况下，什么是一样filter + map，但在一个单一的步骤。

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

这也可以写成

for { 
    (x,i) <- buffer.zipWithIndex 
    if !indicesToDelete.contains(i) 
} yield x