performance - ¿Por qué agregar a una lista es malo?
scala functional-programming (5)
El antepender es más rápido porque solo requiere dos operaciones:
- Crea el nuevo nodo de lista
- Haga que ese nuevo nodo apunte a la lista existente
Agregar requiere más operaciones porque debe atravesar hasta el final de la lista ya que solo tiene un puntero a la cabeza.
Nunca he programado en Scala antes, pero podrías probar un Buffer de Lista
Recientemente comencé a aprender scala, y me encontré con la función :: (cons), que es anterior a una lista.
En el libro "Programación en Scala" indica que no hay función de adición porque agregar a una lista tiene un rendimiento o (n) mientras que anteponer tiene un rendimiento de o (1)
Algo simplemente me parece erróneo sobre esa afirmació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, es ¿qué se supone que debo hacer cuando tengo una lista, digamos 1,2,3 y quiero agregar 4 al final?
La clave es que x :: somelist no muta a 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 usaran listas doblemente vinculadas, x también tendría que establecerse como el predecesor de la somelist de somelist , lo que modificaría somelist . Entonces, si queremos poder hacer :: en O (1) sin modificar la lista original, solo podemos usar listas unidas individualmente.
Respecto a la segunda pregunta: puede usar ::: para concatenar una lista de elementos únicos al final de su lista. Esta es una operación O (n).
List(1,2,3) ::: List(4)
La mayoría de los lenguajes funcionales figuran de manera prominente en una estructura de datos de lista única, ya que es un tipo de colección útil inmutable. 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).
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 agregando elementos, una expresión funcional es construir la lista en orden inverso, consiguiendo los elementos en el frente de la lista, luego revertirlo al final. Esto le da un rendimiento O (n) en lugar de O (n²).
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 anexar un elemento al final de cualquier colección secuencial. (También hay x +: xs para anteponer. La mnemónica para muchas de las operaciones de recopilación de 2.8+ de Scala es que la columna va al lado de la columna ).
Esto será O ( n ) con la implementación vinculada por defecto 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 del Vector de Java, que en la Vector es inútil.
Si está trabajando en Scala 2.8 o superior, la introducción de las colecciones es una lectura absoluta.