Diferencia entre matriz y lista en scala

142

En qué casos debo usar Array (Buffer) y List (Buffer). Solo una diferencia que sé es que las matrices no son variables y las listas son covariantes. Pero, ¿qué pasa con el rendimiento y algunas otras características?

Jeriho
fuente

Respuestas:

155

Estructuras inmutables

El Scala Listes una estructura de datos recursiva inmutable que es una estructura tan fundamental en Scala, que (probablemente) debería usarla mucho más que un Array(que en realidad es mutable , el análogo inmutable de Arrayes IndexedSeq).

Si viene de un fondo Java, entonces el paralelo obvio es cuándo usar LinkedListmás ArrayList. El primero se usa generalmente para listas que solo se recorren (y cuyo tamaño no se conoce por adelantado), mientras que el segundo se debe usar para listas que tienen un tamaño conocido (o tamaño máximo) o para las cuales es importante el acceso aleatorio rápido .

Estructuras mutables

ListBufferproporciona una conversión de tiempo constante a una Listrazón por la cual se debe usar solo ListBuffersi se requiere dicha conversión posterior.

Una Arraymatriz Java debe implementar una escala en la JVM y, por lo tanto, una Array[Int]puede ser mucho más eficaz (como un int[]) que una List[Int](que encapsulará su contenido, a menos que esté utilizando las últimas versiones de Scala que tienen la nueva @specializedcaracterística) .

Sin embargo, creo que el uso de Arrays en Scala debe mantenerse al mínimo porque parece que realmente necesita saber qué sucede debajo del capó para decidir si su matriz realmente estará respaldada por el tipo primitivo requerido, o puede ser en caja como un tipo de envoltura.

oxbow_lakes
fuente
vea también stackoverflow.com/questions/3213368/… y stackoverflow.com/questions/2481149/… la definición de "igual" para matrices es que se refieren a la misma matriz
oluies
130

Además de las respuestas publicadas ya, aquí hay algunos detalles.

Mientras que an Array[A]es literalmente una matriz de Java, a List[A]es una estructura de datos inmutable que es Nil(la lista vacía) o consiste en un par (A, List[A]).

Diferencias de rendimiento

                          Array  List
Access the ith element    θ(1)   θ(i)
Delete the ith element    θ(n)   θ(i)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)
Count the elements        θ(1)   θ(n)

Diferencias de memoria

                          Array  List
Get the first i elements  θ(i)   θ(i)
Drop the first i elements θ(n-i) θ(1)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)

Entonces, a menos que necesite acceso aleatorio rápido, necesite contar elementos, o por alguna razón necesite actualizaciones destructivas, a Listes mejor que an Array.

Apocalipsis
fuente
¿Estos Os tienen que considerar el tiempo para copiar la Lista? Asumo que está haciendo la prueba de este tipo, por ejemplo: list = list.drop(i). O, ¿ocurre algo de magia detrás del capó?
2
Esto tiene en cuenta la copia de listas y matrices cuando sea necesario. Tenga en cuenta que cosas como dropnunca necesitan copiar la parte de la lista que no se descartó. Por ejemplo, (x::xs).drop(1)es exactamente xs, no una "copia" de xs.
Apocalisp
66
Estas asintóticas no tienen nada que ver con Scala. La misma estructura de datos en C será exactamente igual de rápida hasta factores constantes.
Apocalisp
1
@Apocalisp ¿Tiene una referencia o bajo qué condiciones determinó esta información?
Phil
1
@ Phil Estas son asintóticas, no medidas. Serán válidas en todas las condiciones.
Apocalisp
18

Una matriz es mutable, lo que significa que puede cambiar los valores de cada índice, mientras que una lista (por defecto) es inmutable, lo que significa que se crea una nueva lista cada vez que realiza una modificación. En la mayoría de los casos se trata de un estilo más "funcional" para trabajar con tipos de datos inmutables y probablemente debería tratar de utilizar una lista con construcciones como yield, foreach, matchy así sucesivamente.

Para las características de rendimiento, una matriz es más rápida con acceso aleatorio a los elementos, mientras que una lista es más rápida al anteponer (agregar) nuevos elementos. Iterar sobre ellos es comparable.

leonm
fuente
@leonm - apols, pensé que el OP estaba preguntando exclusivamente sobre las clases * Buffer, ¡me di cuenta de que también estaban preguntando sobre las "normales"!
oxbow_lakes
2
Por lo general, es más rápido agregar a un ArrayBuffer que anteponer a una Lista (o agregar un elemento a un ListBuffer) ya que las listas requieren la creación de un objeto contenedor, mientras que ArrayBuffer simplemente necesita copiar el objeto (en promedio aproximadamente dos veces) a una nueva matriz . Por lo general, dos copias son más rápidas que la creación de un objeto, por lo que ArrayBuffer append generalmente supera a List prepend.
Rex Kerr
matriz funciona mucho más rápido que la lista cuando iterate over, debido a la caché
Bin