如何從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