Scala: fastest `remove (i: Int)` в изменяемой последовательности

Question

Какую реализацию из пакета scala.collection.mutable следует принять, если я намерен делать много исключений by-index, например remove(i: Int), в однопоточной среде? Самый очевидный выбор, ListBuffer, говорит, что он может занять линейное время в зависимости от размера буфера. Есть ли какая-нибудь коллекция с log(n) или даже постоянное время для этой операции?

Answer 1

операторов удаления, в том числе buf remove i, не являются частью Seq, но это на самом деле часть Buffer черты под scala.mutable. (См. 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))