Разница между MutableList и ListBuffer

Question

В чем разница между MutableList и ListBuffer классами Scala в scala.collection.mutable?Когда бы вы использовали один против другого?

Мой вариант использования имеет линейную последовательность, в которой я могу эффективно удалить первый элемент, добавить и добавить.Какова лучшая структура для этого?

Answer 1

Небольшое объяснение того, как они работают.

ListBuffer использует внутренне Nil и :: для построения неизменяемого List и позволяет в постоянное время удалять первый и последний элементов.Для этого он сохраняет указатель на первый и последний элемент списка и фактически может изменять заголовок и хвост (* в противном случае неизменяемый) класса :: (хороший прием, допускаемый членами private[scala] var ::).Его метод toList возвращает также обычный неизменный List в постоянное время, поскольку он может напрямую возвращать структуру, поддерживаемую внутри.Он также является компоновщиком по умолчанию для неизменных List с (и, следовательно, действительно можно ожидать, что он будет добавляться в постоянное время).Если вы вызываете 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.

Answer 2

Это дает обзор характеристик производительности: http://www.scala -lang.org / documents / files / collection-api / collection.html ; Интересно, что MutableList и ListBuffer там не отличаются. Документация MutableList говорит, что он используется внутри как базовый класс для Stack и Queue, так что, возможно, ListBuffer является более официальным классом с точки зрения пользователя?

Answer 3

Вам нужен список (почему список?), Который расширяется и сокращается , и вы хотите постоянное добавление и добавление.Хорошо, Buffer, черта, имеет постоянное добавление и добавление, с большинством других операций линейными.Я предполагаю, что ListBuffer, класс, реализующий Buffer, имеет постоянное время удаления первого элемента.

Итак, моя собственная рекомендация для ListBuffer.

Answer 4

Во-первых, давайте рассмотрим некоторые соответствующие типы в 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.

Answer 5

Обратите внимание, что ListBuffer является окончательным / запечатанным, в то время как вы можете расширить MutableList. В зависимости от вашего приложения может быть полезна расширяемость.