ListBuffer에서 여러 인덱스를 빠르게 제거하는 방법은 무엇입니까?

Question

(빠른 방법으로) 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 개체를 만들어야합니다.

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

방법에 대해 :

N이 buffer의 숫자, indicesToDelete의 요소 M 수입니다 O(NM)입니다

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

.

성능에 대한 우려가있는 경우 항상 indicesToDelete을 Set으로 만들 수 있습니다. 이 경우 성능은 O(N입니다. O(1)은 HashSet에 대한 상각 된 조회 또는 TreeSet에 대한 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