¿Por qué es malo agregar a una lista?

Question

Recientemente comencé a aprender scala, y me encontré con la función :: (contras), que es anterior a una lista.
En el libro "Programación en Scala" que indica que no hay ninguna función de agregación debido a anexar a una lista tiene o rendimiento (n) mientras que anteponiendo tiene un rendimiento de O (1)

Algo simplemente me parece equivocado esa declaración.

¿El rendimiento no depende de la implementación? ¿No es posible simplemente implementar la lista con enlaces hacia adelante y hacia atrás y almacenar el primer y último elemento en el contenedor?

La segunda pregunta, ¿supongo que es lo que se supone que debo hacer cuando tengo una lista, digamos 1,2,3 y quiero agregar 4 al final?

Answer 1

La clave es que x :: somelist no muta somelist, sino que crea una nueva lista, que contiene x seguido de todos los elementos de somelist. Esto se puede hacer en O (1) tiempo porque solo necesita establecer somelist como el sucesor de x en la lista recién creada y vinculada individualmente.

Si en su lugar se usaron listas doblemente vinculadas, x también tendría que establecerse como el predecesor del encabezado somelist, que modificaría somelist. Entonces, si queremos poder hacer :: en O (1) sin modificar la lista original, solo podemos usar listas unidas individualmente.

Sobre la segunda pregunta: Puede usar ::: para concatenar una lista de elementos individuales al final de su lista. Esta es una operación O (n).

List(1,2,3) ::: List(4) 

Answer 2

Prepending es más rápido ya que sólo requiere dos operaciones:

1. Cree el nuevo nodo de la lista
2. tener ese nuevo punto de nodo a la lista existente

Anexión requiere más operaciones porque tiene para recorrer hasta el final de la lista ya que solo tiene un puntero a la cabeza.

nunca he programado en Scala antes, pero usted podría intentar un List Buffer

Answer 3

mayoría de los lenguajes funcionales prominente figura una estructura de datos en la lista simplemente enlazada, ya que es un tipo de colección inmutable práctico. Cuando dices "lista" en un lenguaje funcional, eso es lo que quieres decir (una lista de enlace único, generalmente inmutable). Para tal tipo, append es O (n) mientras que cons es O (1).

Answer 4

Otras respuestas han dado buenas explicaciones para este fenómeno. Si está agregando muchos elementos a una lista en una subrutina, o si está creando una lista añadiendo elementos, una expresión funcional es crear la lista en orden inverso, cons'ing los elementos en el frente de la lista , luego inviértala al final. Esto le da un rendimiento O (n) en lugar de O (n²).

Answer 5

Dado que la pregunta se acaba de actualizar, vale la pena señalar que las cosas han cambiado aquí.

En Scala de hoy, simplemente puede usar xs :+ x para agregar un elemento al final de cualquier colección secuencial. (Hay también x +: xs anteponer. El nemotécnico para muchos de 2.8+ operaciones de recogida de Scala es que el col en va junto a la col lection.)

esto será O (n) con el implementación vinculada predeterminada de List o Seq, pero si usa Vector o IndexedSeq, esto será efectivamente tiempo constante. El Vector de Scala es probablemente la colección de listas más útil de Scala, a diferencia de la Vector de Java, que en la actualidad es inútil.

Si está trabajando en Scala 2.8 o superior, el collections introduction es una lectura absoluta.