Diferença entre Array e List em scala

142

Em quais casos eu devo usar Array (Buffer) e List (Buffer). Apenas uma diferença que eu sei é que as matrizes não são variantes e as listas são covariantes. Mas e o desempenho e algumas outras características?

Jeriho
fonte

Respostas:

155

Estruturas Imutáveis

O Scala Listé uma estrutura de dados recursivos imutáveis, que é uma estrutura tão fundamental no Scala, que você (provavelmente) deve usá-lo muito mais do que um Array(que é realmente mutável - o análogo imutável de Arrayé IndexedSeq).

Se você vem de um plano de fundo Java, o paralelo óbvio é quando usar LinkedListnovamente ArrayList. O primeiro é geralmente usado para listas que apenas são percorridas (e cujo tamanho não é conhecido antecipadamente), enquanto o último deve ser usado para listas que possuem um tamanho conhecido (ou tamanho máximo) ou para as quais o acesso aleatório rápido é importante.

Estruturas Mutáveis

ListBufferfornece uma conversão de tempo constante para uma Listque é apenas uma razão para usar ListBufferse essa conversão posterior for necessária.

Um scala Arraydeve ser implementado na JVM por uma matriz Java e, portanto, um Array[Int]pode ter muito mais desempenho (como um int[]) do que um List[Int](que exibirá seu conteúdo em caixa, a menos que você esteja usando as versões mais recentes do Scala que possuem o novo @specializedrecurso) .

No entanto, acho que o uso de Arrays no Scala deve ser reduzido ao mínimo, porque parece que você realmente precisa saber o que está acontecendo sob o capô para decidir se sua matriz será realmente apoiada pelo tipo primitivo necessário ou pode ser embalado como um tipo de invólucro.

oxbow_lakes
fonte
veja também stackoverflow.com/questions/3213368/... e stackoverflow.com/questions/2481149/... a definição de "iguais" para matrizes é que eles se referem à mesma matriz
oluies
130

Além das respostas já postadas, aqui estão alguns detalhes.

Enquanto an Array[A]é literalmente uma matriz Java, a List[A]é uma estrutura de dados imutável que é Nil(a lista vazia) ou consiste em um par (A, List[A]).

Diferenças de desempenho

                          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)

Diferenças de memória

                          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)

Portanto, a menos que você precise de acesso aleatório rápido, precise contar elementos ou, por algum motivo, precise de atualizações destrutivas, a Listé melhor que uma Array.

Apocalisp
fonte
Esses sistemas operacionais precisam considerar o tempo para copiar a lista? Eu suponho que você está fazendo o teste como este, por exemplo: list = list.drop(i). Ou ocorre alguma mágica por trás do capô?
2
Isso leva em consideração a cópia de listas e matrizes quando necessário. Observe que coisas como dropnunca precisam copiar a parte da lista que não foi descartada. Por exemplo, (x::xs).drop(1)é exatamente xs, não uma "cópia" de xs.
Apocalisp
6
Esses assintóticos não têm nada a ver com Scala. A mesma estrutura de dados em C será exatamente tão rápida quanto a fatores constantes.
Apocalisp
1
@Apocalisp Você tem uma referência ou sob quais condições você determinou essas informações?
Phil
1
@ Phil Estes são assintóticos, não medições. Eles se manterão verdadeiros em todas as condições.
Apocalisp
18

Uma matriz é mutável, o que significa que você pode alterar os valores de cada índice, enquanto uma lista (por padrão) é imutável, o que significa que uma nova lista é criada toda vez que você faz uma modificação. Na maioria dos casos, é um estilo mais "funcional" para trabalhar com tipos de dados imutáveis e você provavelmente deve tentar usar uma lista com construções como yield, foreach, matche assim por diante.

Para características de desempenho, uma matriz é mais rápida com acesso aleatório a elementos, enquanto uma lista é mais rápida ao adicionar (adicionar) novos elementos. A iteração sobre eles é comparável.

leonm
fonte
@leonm - desculpas, eu pensei que o OP estava perguntando exclusivamente sobre as classes * Buffer, percebo que eles também estavam perguntando sobre as "normais"!
precisa saber é o seguinte
2
Geralmente, é mais rápido anexar a um ArrayBuffer do que anexar a uma Lista (ou adicionar um elemento a um ListBuffer), pois as listas exigem a criação de um objeto wrapper, enquanto ArrayBuffer apenas precisa copiar o objeto (em média cerca de duas vezes) para uma nova matriz . Normalmente, duas cópias são mais rápidas que a criação de um objeto, portanto o ArrayBuffer append geralmente supera o da lista.
Rex Kerr
executa matriz muito mais rápido que lista quando iterate over, por causa de cache
Bin