CODEWITHSUNDEEP
scala
John Threepwood
John Threepwood

Reputation: 16143

How to remove multiple indices from a ListBuffer (in a fast way)?

Is there a nice way in Scala to delete multiple indices from a ListBuffer (in a fast way) ?

Example:

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

Result:

ListBuffer(b, c, e)

I could not find a pre-defined function that does the job.

One could sort the indices and remove the elements beginning with the highest index etc, so there will be no complication. But sorting requires O(n * log n). Is there a faster way (maybe something pre-defined I missed) ?

UPDATE 1: The elements should be removed in the existing ListBuffer object, no new ListBuffer object should be created.

Upvotes: 3

Views: 1796

Answers (4)

James Iry
James Iry

Reputation: 19367

Unlike others, I'm going to assume you want to do your work in-place because you mention a concern about index renumbering. If the sort is all you care about then

1) Stick the indices to be removed into a constant time lookup set instead of a list. A hash set or bit set would seem appropriate depending on the range of indices. 2) Walk the list buffer in reverse order removing indices that are in the to-delete set.

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)

Note that while this removes the n log n sort of indices, that doesn't make this a linear algorithm. In-place delete from an array-like structure isn't cheap. Higher indices have to be copied downward on each delete.

To get a linear delete of indices you need to do something much hairier, you need to 1) walk in the forward direction copying non-deleted elements downward based on the number that you've deleted so far. When you're done you 2) remove the top n elements where n is the number that you deleted.

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)

Upvotes: 5

Alex Wilson
Alex Wilson

Reputation: 6740

How about:

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

Which is O(NM) where N is the number in buffer, M the number of elements in indicesToDelete.

And if you're concerned about performance, you could always make indicesToDelete a Set. In which case the performance is O(N): assuming O(1) amortised lookup for a HashSet or O(NlogM) for a TreeSet.

And collating all the good ideas from the other posters:

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

To give you one pass over the data only.

Upvotes: 3

xiefei
xiefei

Reputation: 6599

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)

Upvotes: 0

drexin
drexin

Reputation: 24423

You have to use zipWithIndex, as the other posts already do, because otherwise the indices will shift and you could accidentally remove wrong items. But instead of foldLeft or filter + map I would use collect, what in this case does the same as filter + map, but in a single step.

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

this can also be written as

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

Upvotes: 6

Related Questions