Scala: En hızlı `(i: Int) kaldırmak` değişken dizide

Question

ben remove(i: Int) gibi yan endeks-silme sürü yapmak niyetinde eğer tek iş parçacıklı ortamda, almalı scala.collection.mutable paketinden uygulanması

? En belirgin seçim, ListBuffer, arabellek boyutuna bağlı olarak doğrusal zaman alabileceğini söylüyor. Bu işlem için log(n) ile bazı koleksiyonlar veya hatta sabit zaman var mı? buf remove i dahil

Answer 1

Kaldırma operatörleri, Seq parçası değildir, ama aslında scala.mutable altında Buffer özelliği parçası. (Bkz. Buffers)

Performance Characteristics numaralı ilk tabloya bakın. buf remove i'un, hem ArrayBuffer hem de ListBuffer için doğrusal olan ekleme ile aynı özelliğe sahip olduğunu tahmin ediyorum. Array Buffers belgesinde belirtildiği gibi, dizileri dahili olarak kullanırlar ve Link Buffers bağlantılı listeler kullanırlar (bu hala kaldırılmak üzere O (n)).

Bir alternatif olarak, değişmez Vector size etkili bir sabit zaman verebilir.

vektörler yüksek dallanma faktörü ile ağaç olarak temsil edilir. Her ağaç düğümü, vektörün 32 öğesine kadar içerir veya 32'ye kadar diğer ağaç düğümleri içerir. [...] Bu nedenle, makul boyuttaki tüm vektörler için, bir eleman seçimi 5 ilkel dizi seçimini içerir. Öğe erişiminin "etkili bir şekilde sabit zaman" olduğunu yazdığımızda kastettiğimiz şey buydu.

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) 

Ancak, veri boyutu kadar hızlı lineer erişim kazanmak olmayabilir yükü dolu bir yüksek sabit zaman önemli ölçüde büyüktür.

Answer 2

Tam kullanım durumunuza bağlı olarak, scala.collection.mutable numaralı telefondan LinkedHashMap'u kullanabilirsiniz.

Dizine göre kaldıramasanız da, sabit bir zamanda benzersiz bir anahtarla kaldırabilirsiniz ve yinelediğinizde deterministik bir sıralamayı korur.

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))