5

シングルスレッド環境でのscala.collection.mutableように、インデックスによる削除をたくさん行う場合は、パッケージからどの実装を採用する必要がありますか？remove(i: Int)最も明白な選択はListBuffer、バッファサイズによっては線形時間がかかる可能性があることを示しています。この操作のためのコレクション、log(n)または一定の時間さえありますか？

4

3 に答える 3

8

を含む削除演算子は、buf remove iの一部ではありませんがSeq、実際にはのBuffer特性の一部ですscala.mutable。（バッファを参照）

パフォーマンス特性に関する最初の表を参照してください。との両方でbuf remove i線形である挿入と同じ特性を持っていると思います。配列バッファーに記載されているように、それらは内部で配列を使用し、リンクバッファーはリンクリストを使用します（削除にはO（n）のままです）。ArrayBufferListBuffer

別の方法として、不変のベクトルは効果的な一定時間を与える可能性があります。

ベクトルは、分岐係数の高いツリーとして表されます。すべてのツリーノードには、ベクトルの最大32個の要素が含まれるか、最大32個の他のツリーノードが含まれます。[...]したがって、妥当なサイズのすべてのベクトルの場合、要素の選択には最大5つのプリミティブ配列の選択が含まれます。これは、要素アクセスが「事実上一定の時間」であると書いたときに意味したことです。

scala> import scala.collection.immutable._
import scala.collection.immutable._

scala> def remove[A](xs: Vector[A], i: Int) = (xs take i) ++ (xs drop (i + 1))
remove: [A](xs: scala.collection.immutable.Vector[A],i: Int)scala.collection.immutable.Vector[A]

scala> val foo = Vector(1, 2, 3, 4, 5)
foo: scala.collection.immutable.Vector[Int] = Vector(1, 2, 3, 4, 5)

scala> remove(foo, 2)
res0: scala.collection.immutable.Vector[Int] = Vector(1, 2, 4, 5)

ただし、多くのオーバーヘッドを伴う高い一定時間は、データサイズが大幅に大きくなるまで、迅速な線形アクセスに勝てない場合があることに注意してください。

于 2010-12-14T17:29:15.407 に答える
1

LinkedHashMap正確な使用例によっては、から使用できる場合がありますscala.collection.mutable。

インデックスで削除することはできませんが、一定時間で一意のキーで削除することができ、反復するときに決定論的な順序が維持されます。

scala> val foo = new scala.collection.mutable.LinkedHashMap[String,String]
foo: scala.collection.mutable.LinkedHashMap[String,String] = Map()

scala> foo += "A" -> "A"
res0: foo.type = Map((A,A))

scala> foo += "B" -> "B"
res1: foo.type = Map((A,A), (B,B))

scala> foo += "C" -> "C"
res2: foo.type = Map((A,A), (B,B), (C,C))

scala> foo -= "B"
res3: foo.type = Map((A,A), (C,C))
于 2010-12-18T23:36:37.077 に答える
1

ArrayList最後の要素が削除される要素である場合、Javaは事実上一定の時間計算量を持ちます。ソースコードからコピーされた次のスニペットを見てください。

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

ご覧のとおり、がnumMoved0に等しい場合remove、配列はシフトおよびコピーされません。これは、一部のシナリオでは非常に便利です。たとえば、順序をあまり気にしない場合は、要素を削除するために、いつでも最後の要素と交換してから、から最後の要素を削除できますArrayList。これにより、remove操作が常に一定になります。私はArrayBuffer同じことをしたいと思っていましたが、残念ながらそうではありませんでした。

于 2019-08-28T15:13:57.350 に答える