189 votes

Quand dois-je choisir Vector in Scala?

Il semble que Vector soit en retard à la soirée des collections Scala et que tous les articles de blog influents étaient déjà partis.

En Java, ArrayList est la collection par défaut - je pourrais utiliser LinkedList mais uniquement lorsque je réfléchis à un algorithme et que je m'intéresse suffisamment à l'optimisation. En Scala, devrais-je utiliser Vector comme Seq par défaut ou essayer de déterminer quand List est plus approprié?

266voto

Daniel Spiewak Points 30706

En règle générale, par défaut à l'aide d' Vector. Il est plus rapide que d' List pour presque tout et plus efficace de la mémoire pour plus-que-trivial de la taille des séquences. Voir cette documentation de la performance relative du Vecteur par rapport à d'autres collections. Il y a quelques inconvénients à aller avec Vector. Plus précisément:

  • Les mises à jour à la tête sont plus lents que d' List (mais pas autant que vous pourriez le penser)

Un autre inconvénient avant Scala 2.10 était que la correspondance de modèle de soutien a été meilleure pour List, mais cela a été rectifié dans la version 2.10 généralisée +: et :+ extracteurs.

Il est également l'un des plus abstraits algébriques façon d'aborder cette question: quelle sorte de séquence ne vous conceptuellement ? Aussi, ce que vous êtes sur le plan conceptuel faire avec elle? Si je vois une fonction qui renvoie un Option[A], je sais que la fonction a quelques trous dans son domaine (et est donc partielle). On peut appliquer cette même logique pour les collections.

Si j'ai une séquence de type List[A], je suis effectivement d'affirmer deux choses. Tout d'abord, mon algorithme (et les données) est entièrement pile-structuré. Deuxièmement, je suis d'affirmer que les seules choses que je vais faire avec cette collection sont pleins, O(n) traversals. Ces deux vraiment aller de pair. A l'inverse, si j'ai quelque chose de type Vector[A], la seule chose dont je suis affirmer, c'est que mes données a un ordre bien défini et une longueur finie. Ainsi, les assertions sont plus faibles avec Vector, ce qui conduit à sa grande souplesse.

91voto

Daniel C. Sobral Points 159554

Eh bien, un List peut être très rapide si l'algorithme peut être mise en œuvre uniquement avec ::, head et tail. J'ai eu une leçon de choses de que très récemment, quand j'ai battu Java split en générant un List au lieu d'un Array, et ne pouvait pas être avec autre chose.

Toutefois, List a un problème de fond: il ne fonctionne pas avec des algorithmes parallèles. Je ne peut pas diviser un List en plusieurs segments, ou concaténer en arrière, de manière efficace.

Il existe d'autres types de collections qui peut gérer le parallélisme beaucoup mieux, et Vector est l'un d'entre eux. Vector a également une grande localité -- List n'est pas, de ce qui peut être un réel plus pour certains algorithmes.

Donc, toutes choses considérées, Vector est le meilleur choix , sauf si vous avez des considérations spécifiques qui en font l'un des autres collections préférable, par exemple, vous pouvez choisir Stream si vous voulez paresseux de l'évaluation et de la mise en cache (Iterator est plus rapide, mais ne met pas en cache), ou List de l'algorithme est naturellement mis en œuvre avec les opérations que j'ai mentionnés.

Par ailleurs, il est préférable d'utiliser Seq ou IndexedSeq sauf si vous voulez un élément spécifique de l'API (comme Lists' ::), ou même GenSeq ou GenIndexedSeq si votre algorithme peuvent être exécutées en parallèle.

24voto

Luigi Plinge Points 23552

Pour immuable collections, si vous voulez une séquence, votre décision est de savoir si l'utilisation d'un IndexedSeq ou LinearSeq, ce qui donne différentes garanties pour la performance. Un IndexedSeq rapide d'accès aléatoire d'éléments et rapide de la longueur de l'opération. Un LinearSeq fournit un accès rapide uniquement pour le premier élément via head, mais a également un fast - tail de l'opération. (Extrait de la Seq documentation.)

Pour un IndexedSeq vous le feriez normalement choisir un Vector. Ranges et WrappedStrings sont aussi IndexedSeqs.

Pour un LinearSeq vous le feriez normalement choisir un List ou de ses paresseux équivalent Stream. D'autres exemples sont Queues et Stacks.

Donc en Java termes, ArrayList utilisé de la même façon à la Scala en Vector, et LinkedList de même à la Scala en List. Mais en Scala, j'aurais tendance à utiliser la Liste le plus souvent Vecteur de, en raison de la Scala a beaucoup plus de soutien pour les fonctions qui comprennent la traversée de la séquence, comme la cartographie, le pliage, le parcours etc. On a tendance à utiliser ces fonctions pour manipuler la liste dans son ensemble, plutôt qu'au hasard d'accéder à différents éléments.

2voto

Debilski Points 28586

Dans les situations qui impliquent un grand nombre d'accès aléatoire et une mutation aléatoire, Vector (ou – comme les docs disent – Seq) semble être un bon compromis. C'est aussi ce que les caractéristiques de performance suggèrent.

Aussi, l' Vector classe semble jouer bien dans les environnements distribués, sans beaucoup de duplication des données, car il n'y a pas besoin de faire un copy-on-write de l'objet complet. (Voir: http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures)

0voto

Joshua Hartman Points 535

Si vous programmez immuablement et avez besoin d'un accès aléatoire, Seq est la solution (à moins que vous ne souhaitiez un Set, ce que vous faites souvent). Sinon, la liste fonctionne bien, sauf que ses opérations ne peuvent pas être parallélisées.

Si vous n'avez pas besoin de structures de données immuables, restez fidèle à ArrayBuffer, car c'est l'équivalent de Scala à ArrayList.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by: