スカラ：可変シーケンスの中で最も速い `remove（i：Int）`

Question

単一スレッド環境でremove(i: Int)のような索引削除をたくさん行うつもりならば、scala.collection.mutableパッケージの実装はどうすればいいですか？最も明白な選択肢、ListBufferは、バッファサイズに応じて線形時間がかかることがあると言います。 log(n)のコレクションがありますか？

Answer 1

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

Performance Characteristicsの最初の表を参照してください。私はbuf remove iは、インサートと同じ特性を持っていると推測しています。それはArrayBufferとListBufferの両方に対して線形です。 Array Buffersに記載されているように、それらは内部的に配列を使用し、Link Buffersはリンクされたリストを使用します（削除のためにはまだO（n）です）。

不変のVectorは、有効な一定時間を与える場合があります。

ベクトルは高い分岐係数を持つツリーとして表されます。すべてのツリーノードには、最大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) 

データサイズが非常に大きくなるまで注意は、しかし、オーバーヘッドの多くが付いている高い一定の時間が素早くリニアにアクセスを獲得しないことがあります。

Answer 2

正確な使用例に応じて、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))