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があります。そうしないと、インデックスがシフトし、間違ったアイテムを誤って削除する可能性があるためです。foldLeftただし、 or filter+の代わりにmapを使用します。この場合は+collectと同じですが、1 つのステップで実行されます。filtermap

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. その場合のパフォーマンスは): HashSet または の償却されたルックアップをO(N想定しています。O(1)O(NlogM)TreeSet

そして、他のポスターからのすべての良いアイデアを照合します。

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

データのみを 1 回渡すため。

于 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 に答える