Différence entre le tableau et la liste dans scala

Dans quels cas je devrais utiliser Array (Buffer) et List (Buffer). Une seule différence que je connais est que les tableaux ne sont pas variables et que les listes sont covariantes. Mais qu'en est-il de la performance et d'autres caractéristiques?

107
demandé sur Eugene Yokota 2010-04-26 15:03:24

3 réponses

Structures Immuables

Le Scala List est une structure de données récursive immuable qui est une structure si fondamentale dans Scala, que vous devriez (probablement) l'utiliser beaucoup plus qu'un Array (qui est en fait mutable - le analogue immuable de Array est IndexedSeq).

Si vous venez D'un arrière-plan Java, alors le parallèle évident est 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 à l'avance) alors que cette dernière devrait être utilisée pour les listes qui ont soit une taille connue (ou une taille maximale) ou pour lesquelles un accès aléatoire rapide est important.

Structures Mutables

ListBuffer fournit une conversion à temps constant en List qui est la seule raison d'utiliser ListBuffer Si une telle conversion ultérieure est requise.

Un scala Array devrait être implémenté sur la JVM par un tableau Java, et donc un Array[Int] peut être beaucoup plus performant (comme un int[]) qu'un List[Int] (qui boxera son contenu, sauf si vous utilisez les toutes dernières versions de Scala qui ont la nouvelle fonctionnalité @specialized).

Cependant, je pense que l'utilisation de Array S dans Scala devrait être réduite au minimum car il semble que vous ayez vraiment besoin de savoir ce qui se passe sous le capot pour décider si votre tableau sera vraiment soutenu par le type primitif requis, ou peut être encadré comme un type de wrapper.

127
répondu oxbow_lakes 2010-04-26 11:26:54

En plus des réponses déjà affichées, voici quelques détails.

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

Les différences de Performances entre

                          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)

Différences de mémoire

                          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)

Donc, sauf si vous avez besoin d'un accès aléatoire rapide, besoin de compter des éléments, ou pour une raison quelconque, vous avez besoin de mises à jour destructrices, un List est meilleur qu'un Array.

113
répondu Apocalisp 2018-08-22 13:54:19

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, c'est un style plus "fonctionnel" de travailler avec des types de données immuables et vous devriez probablement essayer d'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 aux éléments, alors qu'une liste est plus rapide lorsque ajoutant (ajout) de nouveaux éléments. Itérer sur eux est comparable.

15
répondu leonm 2010-04-26 11:19:55