Différence entre Array et List dans Scala

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

Structures immuables

La 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 réalité mutable – l’ analogue immuable d’ Array est IndexedSeq ).

Si vous venez d’un arrière-plan Java, 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ées (et dont la taille n’est pas connue au départ) alors que la seconde doit être utilisée pour les listes ayant soit une taille connue (ou une taille maximale), soit un access aléatoire rapide .

Structures Mutable

ListBuffer fournit une conversion en temps constant à une List qui est la seule raison d’utiliser ListBuffer si une telle conversion ultérieure est requirejse.

Un Array Scala doit être implémenté sur la machine virtuelle Java par un tableau Java, et un Array[Int] peut donc être beaucoup plus performant (en tant que int[] ) qu’une List[Int] (qui en encartera le 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 masortingce sera réellement soutenue par le type primitif requirejs, ou peut être encadré en tant que type wrapper.

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

Alors qu’un Array[A] est littéralement un tableau Java, une List[A] est une structure de données immuable qui est soit Nil (la liste vide) soit composée d’une paire (A, List[A]) .

Différences de performance

  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 θ(ni) θ(1) Insert an element at i θ(n) θ(i) Reverse θ(n) θ(n) Concatenate (length m,n) θ(n+m) θ(n) 

Donc, à moins que vous n’ayez besoin d’un access aléatoire rapide, que vous ayez besoin de compter des éléments ou que vous ayez besoin de mises à jour destructives, une List vaut mieux qu’un Array .

Un tableau est modifiable, ce qui signifie que vous pouvez modifier les valeurs de chaque index, tandis qu’une liste (par défaut) est immuable, ce qui signifie qu’une nouvelle liste est créée chaque fois que vous effectuez une modification. Dans la plupart des cas, il est plus fonctionnel de travailler avec des types de données immuables et vous devriez probablement essayer d’utiliser une liste avec des constructions telles que yield , foreach , match , etc.

Pour les caractéristiques de performances, un tableau est plus rapide avec un access aléatoire aux éléments, tandis qu’une liste est plus rapide lors de l’ajout (ajout) de nouveaux éléments. Itérer sur eux est comparable.