Scala: самое быстрое `remove (i: Int)` в изменяемой последовательности - PullRequest
Новая
       7

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

5 голосов
/ 14 декабря 2010

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

Ответы [ 2 ]

7 голосов
/ 14 декабря 2010

Операторы удаления, включая buf remove i, не являются частью Seq, но на самом деле они являются частью черты Buffer в scala.mutable.(См. Буферы )

См. Первую таблицу в Характеристики производительности .Я предполагаю, что buf remove i имеет те же характеристики, что и вставка, которые являются линейными как для ArrayBuffer, так и для ListBuffer.Как описано в Буферы массивов , они используют массивы внутри, а Буферы ссылок используют связанные списки (для удаления это все еще O (n)).

В качестве альтернативы,неизменный Вектор может дать вам эффективное постоянное время.

Векторы представлены в виде деревьев с высоким коэффициентом ветвления.Каждый узел дерева содержит до 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)

Обратите внимание, однако, что высокое постоянное время с большим количеством накладных расходов может не дать быстрого линейного доступа, пока размер данных не станет значительно большим.

1 голос
/ 19 декабря 2010

В зависимости от вашего конкретного случая использования вы можете использовать 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))
...