La différence entre le Tableau et de Liste en scala

Question

Dans ce cas, je devrais utiliser Array(Tampon) et la Liste(Tampon). Une seule différence que je sais, c'est que les tableaux sont nonvariant et les listes sont covariants. Mais ce sujet de la performance et de certaines autres caractéristiques?

Answer 1

Immuable Structures

La Scala List est immuable structure de données récursive qui est une structure fondamentale de la Scala, qu'il vous faut (probablement) être de l'utiliser beaucoup plus qu'un Array (qui est en fait mutable - l' immuable analogique de Array est IndexedSeq).

Si vous venez d'un Java arrière-plan, puis le parallèle est évident quand utiliser LinkedList sur ArrayList. Le premier est généralement utilisé pour les listes qui ne sont jamais traversé (et dont la taille n'est pas connue d'avance) alors que cette dernière devrait être utilisée pour les listes qui ont une taille connue (ou de taille maximale) ou pour lesquels un accès aléatoire rapide est important.

Mutable Structures

ListBuffer fournit une constante de temps de la conversion à une List qui est la seule raison d'utiliser ListBuffer si une conversion est nécessaire.

Un scala Array devrait être mis en œuvre sur la JVM en Java tableau, et, par conséquent, Array[Int] peut être beaucoup plus performant ( int[]) de plus qu'un List[Int] (qui va de la boîte de son contenu, sauf si vous utilisez les dernières versions de la Scala qui ont le nouveau @specialized ).

Cependant, je pense que l'utilisation de l' Arrays en Scala devrait être maintenue à un minimum, car il se sent comme vous avez vraiment besoin de savoir ce qui se passe sous le capot de décider si votre tableau sera vraiment soutenu par le type de primitive, ou peut-être encadrées, comme une couverture de type.

Answer 2

Outre les réponses postées déjà, voici quelques précisions.

Alors qu'une Matrice[A] est littéralement un Java tableau, une Liste[A] est immuable la structure de données qui est soit Nil (la liste vide) ou se compose d'une paire en (A, List[A]).

Les différences de rendement

                          Array  List
Access the ith element    O(1)   O(i)
Discard the ith element   O(n)   O(i)
Insert an element at i    O(n)   O(i)
Reverse                   O(n)   O(n)
Concatenate (length m,n)  O(n+m) O(n)
Calculate the length      O(1)   O(n)

La mémoire des différences

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

Answer 3

Un Tableau est mutable, ce qui signifie que vous pouvez modifier les valeurs de chaque indice, alors qu'une Liste (par défaut) est immuable, ce qui signifie qu'une nouvelle liste est créée chaque fois que vous faites une modification. Dans la plupart des cas, il est plus "fonctionnelle" style de travail avec immuables types de données et vous devriez probablement essayer et utiliser une Liste avec des constructions comme yield, foreach, match et ainsi de suite.

Pour les caractéristiques de performance, un Tableau est plus rapide avec un accès aléatoire à des éléments, tandis qu'une Liste est plus rapide lorsque l'ajoutant (ajout) de nouveaux éléments. Itération sur eux est comparable.