Разница между MutableList и ListBuffer
В чем разница между Скалой MutableList а также ListBuffer занятия в scala.collection.mutable? Когда бы вы использовали один против другого?
Мой сценарий использования имеет линейную последовательность, в которой я могу эффективно удалить первый элемент, добавить и добавить. Какова лучшая структура для этого?
5 ответов
Небольшое объяснение того, как они работают.
ListBuffer использует внутренне Nil а также :: построить неизменный List и позволяет удалять первый и последний элементы в постоянном времени. Для этого он сохраняет указатель на первый и последний элемент списка и фактически может изменять заголовок и хвост (в противном случае неизменяемый) :: класс (хороший трюк, разрешенный private[scala] var Члены ::). это toList метод возвращает обычный неизменяемый List в постоянное время, так как он может напрямую возвращать структуру, поддерживаемую внутри. Это также строитель по умолчанию для неизменяемого Lists (и, таким образом, можно ожидать, что он будет иметь постоянное добавление). Если вы позвоните toList и затем снова добавить элемент в буфер, требуется линейное время по отношению к текущему количеству элементов в буфере, чтобы воссоздать новую структуру, так как он больше не должен изменять экспортируемый список.
MutableList работает внутри с LinkedList вместо этого (открыто, не нравится ::Реализация изменяемого связанного списка, который знает о своем элементе и преемнике (например, ::). MutableList также сохраняет указатели на первый и последний элемент, но toList возвращается в линейное время, как результат List построен из LinkedList, Таким образом, не нужно повторно инициализировать буфер после List был экспортирован.
Учитывая ваши требования, я бы сказал, ListBuffer а также MutableList эквивалентны. Если вы хотите экспортировать их внутренний список в какой-то момент, спросите себя, где вы хотите использовать издержки: когда вы экспортируете список, а затем никаких накладных расходов, если вы используете мутирующий буфер (затем перейдите к MutableList), или только если вы изменяете буфер снова, и ни один во время экспорта (затем перейдите к ListBuffer).
Я думаю, что в капитальном ремонте коллекции 2.8, MutableList предшествовала ListBuffer и весь Builder система. На самом деле, MutableList преимущественно полезно изнутри collection.mutable пакет: у него есть private[mutable] def toLinkedList метод, который возвращается в постоянное время и, таким образом, может эффективно использоваться в качестве делегированного компоновщика для всех структур, которые поддерживают LinkedList внутренне.
Так что я бы также рекомендовал ListBufferтак как это может также привлечь внимание и оптимизировать в будущем, чем "чисто изменяемые" структуры, такие как MutableList а также LinkedList,
This gives you an overview of the performance characteristics: http://www.scala-lang.org/docu/files/collections-api/collections.html; что интересно, MutableList а также ListBuffer do not differ there. Документация MutableList says it is used internally as base class for Stack а также Queue, так что, может быть ListBuffer is more the official class from the user perspective?
Вам нужен список (почему список?), Который можно увеличивать и уменьшать, и вы хотите постоянно добавлять и дописывать. Что ж, Buffer, черта, имеет постоянное добавление и добавление, при этом большинство других операций являются линейными. Я предполагаю, что ListBuffer класс, который реализует Buffer, имеет постоянное время удаления первого элемента.
Итак, моя собственная рекомендация для ListBuffer,
Во-первых, давайте рассмотрим некоторые из соответствующих типов в Scala
List - Неизменная коллекция. Рекурсивная реализация т.е. т.е. экземпляр списка имеет два первичных элемента - голову и хвост, где хвост ссылается на другой List,
List[T]
head: T
tail: List[T] //recursive
LinkedList - Изменчивая коллекция, определенная как серия связанных узлов, где каждый узел содержит значение и указатель на следующий узел.
Node[T]
value: T
next: Node[T] //sequential
LinkedList[T]
first: Node[T]
Список - это функциональная структура данных (неизменность) по сравнению с LinkedList, который является более стандартным в императивных языках.
Теперь давайте посмотрим на
ListBuffer - Реализация изменяемого буфера, поддерживаемая List,
MutableList - Реализация, основанная на LinkedList (была бы более понятной, если бы она была названа LinkedListBuffer вместо)
Они оба предлагают одинаковые границы сложности для большинства операций.
Однако, если вы запрашиваете List из MutableList затем он должен преобразовать существующее линейное представление в рекурсивное представление, которое принимает O(n), на что указывает @Jean-Philippe Pellet. Но, если вы просите Seq от MutableList сложность O(1).
Итак, IMO выбор сужается до специфики вашего кода и ваших предпочтений. Хотя, я подозреваю, что есть намного больше List а также ListBuffer там
Обратите внимание, что ListBuffer является окончательным / запечатанным, в то время как вы можете расширить MutableList. В зависимости от вашего приложения может быть полезна расширяемость.