Diferencia entre MutableList y ListBuffer

Question

¿Cuál es la diferencia entre las clases MutableList y ListBuffer de Scala en scala.collection.mutable? ¿Cuándo usarías uno frente al otro?

Mi caso de uso tiene una secuencia lineal en la que puedo eliminar eficientemente el primer elemento, anteponer y anexar. ¿Cuál es la mejor estructura para esto?

Answer 1

Una pequeña explicación sobre cómo funcionan.

ListBuffer utiliza internamente Nil y :: para construir un inmutable List y permite la eliminación constante de tiempo de la primera y la última elementos. Para hacerlo, mantiene un puntero en el primer y último elemento de la lista, y está permitido cambiar la cabeza y la cola de la clase :: (de lo contrario inmutable) (buen truco permitido por los miembros private[scala] var de ::). Su método toList devuelve la normalidad inmutable List en tiempo constante también, ya que puede devolver directamente la estructura mantenida internamente. También es el generador predeterminado para List s inmutables (y, por lo tanto, se puede esperar razonablemente que tenga un anexo de tiempo constante). Si llama al toList y vuelve a agregar un elemento al búfer, lleva tiempo lineal con respecto al número actual de elementos en el búfer para recrear una nueva estructura, ya que no debe mutar la lista exportada.

MutableList trabaja internamente con LinkedList lugar, un (abiertamente, no como ::) mutable aplicación lista enlazada, que sabe de su elemento y sucesor (como ::). MutableList también conserva los punteros al primer y último elemento, pero toList regresa en tiempo lineal, ya que el List resultante se construye a partir del LinkedList. Por lo tanto, no es necesario reiniciar el almacenamiento intermedio después de exportar List.

Dados sus requisitos, diría que ListBuffer y MutableList son equivalentes. Si desea exportar su lista interna en algún momento, pregúntese dónde desea la sobrecarga: cuando exporte la lista, y luego sin gastos generales si continúa mutando el búfer (luego vaya por MutableList), o solo si puede cambiar el buffer de nuevo, y ninguno en el tiempo de exportación (luego vaya por ListBuffer).

Supongo que en la revisión de la colección 2.8, MutableList precedió ListBuffer y todo el sistema Builder.En realidad, MutableList es principalmente útil desde el paquete collection.mutable: tiene un método private[mutable] def toLinkedList que regresa en tiempo constante y, por lo tanto, se puede usar de manera eficiente como constructor delegado para todas las estructuras que mantienen un LinkedList internamente.

Así que también recomendaría ListBuffer, ya que también puede llamar la atención y la optimización en el futuro que las estructuras "puramente mutables" como MutableList y LinkedList.

Answer 2

Esto le brinda una descripción general de las características de rendimiento: http://www.scala-lang.org/docu/files/collections-api/collections.html; Curiosamente, MutableList y ListBuffer no difieren allí. La documentación de MutableList dice que se usa internamente como clase base para Stack y Queue, por lo que quizás ListBuffer es más la clase oficial desde la perspectiva del usuario?

Answer 3

desea una lista (¿por qué una lista?) Que es growable y retráctil, y que desea anexar constante y anteponer. Bueno, Buffer, un rasgo, tiene append y prepend constante, con la mayoría de las otras operaciones lineales. Supongo que ListBuffer, una clase que implementa Buffer, tiene una eliminación de tiempo constante del primer elemento.

Por lo tanto, mi propia recomendación es para ListBuffer.

Answer 4

En primer lugar, vamos a repasar algunos de los tipos relevantes en Scala

List - Una colección inmutable. Una implementación recursiva, es decir. Es decir, una instancia de la lista tiene dos elementos principales, la cabeza y la cola, donde la cola hace referencia a otra List.

List[T] 
    head: T 
    tail: List[T] //recursive 

LinkedList - Una colección mutable definido como una serie de nodos vinculados, donde cada nodo contiene un valor y un puntero al siguiente nodo.

Node[T] 
    value: T 
    next: Node[T] //sequential 

LinkedList[T] 
    first: Node[T] 

lista es una estructura de datos funcional (inmutabilidad) en comparación con LinkedList que es más habitual en los lenguajes imperativos.

Ahora, veamos

ListBuffer - Una aplicación búfer mutable respaldado por una List.

MutableList - Una implementación basada en LinkedList (hubiera sido más explica por sí mismo si hubiera sido nombrado LinkedListBuffer lugar)

They both offer similar complexity bounds on most operations.

Sin embargo, si solicita una List de un MutableList, entonces tiene que convertir la representación lineal existente en la representación recursiva que toma O (n), que es lo que señala @ Jean-Philippe Pellet. Pero, si solicita un Seq de MutableList, la complejidad es O (1).

Por lo tanto, la elección de IMO se reduce a los detalles de su código y su preferencia. Sin embargo, sospecho que hay mucho más List y ListBuffer por ahí.

Answer 5

Tenga en cuenta que ListBuffer es final/sellado, mientras que puede extender MutableList. Dependiendo de su aplicación, la extensibilidad puede ser útil.