Scala: más rápido `remove (i: Int)` en la secuencia mutable

Question

¿Qué implementación del paquete scala.collection.mutable debo tomar si tengo la intención de hacer muchas eliminaciones by-index, como remove(i: Int), en un entorno de subproceso único? La opción más obvia, ListBuffer, dice que puede tomar tiempo lineal dependiendo del tamaño del búfer. ¿Hay alguna colección con log(n) o incluso tiempo constante para esta operación?

Answer 1

operadores de mudanzas, incluyendo buf remove i, no son parte de Seq, pero es en realidad parte de Buffer rasgos en scala.mutable. (Consulte Buffers)

Consulte la primera tabla en Performance Characteristics. Supongo que buf remove i tiene la misma característica que inserción, que son lineales para ambos ArrayBuffer y ListBuffer. Como se documenta en Array Buffers, utilizan matrices de forma interna, y Link Buffers usan listas vinculadas (que todavía es O (n) para eliminar).

Como alternativa, el Vector inmutable le puede dar un tiempo constante efectivo.

Los vectores se representan como árboles con un alto factor de ramificación. Cada nodo de árbol contiene hasta 32 elementos del vector o contiene hasta 32 otros nodos de árbol. [...] Entonces, para todos los vectores de tamaño razonable, una selección de elementos implica hasta 5 selecciones de matriz primitiva. Esto es lo que queríamos decir cuando escribimos que el acceso a los elementos es "efectivamente tiempo constante".

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) 

Nótese, sin embargo, una alta constante de tiempo con una gran cantidad de gastos indirectos no pueden ganar un acceso rápido lineal hasta que el tamaño de los datos es significativamente grande.

Answer 2

Dependiendo de su caso de uso exacto, es posible que pueda usar LinkedHashMap desde scala.collection.mutable.

Aunque no se puede eliminar por índice, puede eliminar mediante una clave única en tiempo constante, y mantiene un orden determinista cuando itera.

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