Haskell: listes, tableaux, vecteurs, séquences

J’apprends Haskell et lis quelques articles concernant les différences de performances des listes Haskell et des tableaux (insérez votre langage).

En tant qu’apprenant, je n’utilise évidemment que des listes sans même penser à la différence de performance. J’ai récemment commencé à étudier et à trouver de nombreuses bibliothèques de structures de données disponibles dans Haskell.

Quelqu’un peut-il s’il vous plaît expliquer la différence entre les listes, tableaux, vecteurs, séquences sans aller très loin dans la théorie de l’informatique des structures de données?

En outre, existe-t-il des modèles courants dans lesquels vous utiliseriez une structure de données plutôt qu’une autre?

Existe-t-il d’autres formes de structures de données qui me manquent et qui pourraient être utiles?

Listes Rock

La structure de données de loin la plus conviviale pour les données séquentielles dans Haskell est la liste

data [a] = a:[a] | [] 

Les listes vous donnent cons (1) inconvénients et correspondance de modèle. La bibliothèque standard, et même le prélude, est remplie de fonctions de listes utiles qui devraient foldr votre code ( foldr , map , filter ). Les listes sont persistantes , alias purement fonctionnelles, ce qui est très bien. Les listes de Haskell ne sont pas vraiment des “listes” car elles sont coinductives (d’autres langages appellent ces stream)

 ones :: [Integer] ones = 1:ones twos = map (+1) ones tenTwos = take 10 twos 

travailler à merveille. Structures de données infinies

Les listes de Haskell fournissent une interface très proche des iterators dans les langages impératifs (à cause de la paresse). Donc, il est logique qu’ils soient largement utilisés.

D’autre part

Le premier problème avec les listes est que leur indexation (!!) prend du temps (k), ce qui est agaçant. En outre, les ajouts peuvent être lents ++ , mais le modèle d’évaluation paresseux de Haskell signifie que ceux-ci peuvent être traités comme complètement amortis s’ils se produisent.

Le deuxième problème avec les listes est qu’elles ont une mauvaise localisation des données. Les processeurs réels subissent des constantes élevées lorsque les objects en mémoire ne sont pas disposés les uns à côté des autres. Ainsi, en C ++, std::vector a plus rapidement “snoc” (en plaçant des objects à la fin) que toute structure de données en liste chaînée que je connaisse, bien qu’il ne s’agisse pas d’une structure de données persistante moins conviviale que les listes de Haskell.

Le troisième problème avec les listes est qu’elles ont une efficacité spatiale médiocre. Des grappes de pointeurs supplémentaires font monter votre stockage (par un facteur constant).

Les séquences sont fonctionnelles

Data.Sequence est basé en interne sur les arbres de doigt (je sais, vous ne voulez pas le savoir), ce qui signifie qu’ils ont de bonnes propriétés

  1. Purement fonctionnel. Data.Sequence est une structure de données entièrement persistante.
  2. Accès rapide au début et à la fin de l’arbre. ϴ (1) (amorti) pour obtenir le premier ou le dernier élément, ou pour append des arbres. À la chose, les listes sont les plus rapides à, Data.Sequence est tout au plus une constante plus lente.
  3. ϴ (log n) access au milieu de la séquence. Cela inclut l’insertion de valeurs pour créer de nouvelles séquences
  4. API de haute qualité

D’autre part, Data.Sequence ne fait pas grand chose pour le problème de la localité des données, et ne fonctionne que pour les collections finies (il est moins paresseux que les listes).

Les tableaux ne sont pas pour les faibles de cœur

Les tableaux sont l’une des structures de données les plus importantes dans CS, mais ils ne correspondent pas très bien au monde fonctionnel pur paresseux. Les tableaux fournissent un access ϴ (1) au milieu de la collection et une localisation des données / des facteurs constants exceptionnellement bons. Mais comme ils ne s’intègrent pas très bien dans Haskell, ils sont douloureux à utiliser. Il existe en réalité une multitude de types de tableaux différents dans la bibliothèque standard actuelle. Celles-ci incluent des tableaux entièrement persistants, des tableaux mutables pour la monade IO, des tableaux mutables pour la monade ST et des versions non encadrées de ce qui précède. Pour plus d’informations, consultez le wiki haskell

Le vecteur est un “meilleur” tableau

Le package Data.Vector fournit toutes les Data.Vector du tableau, dans une API de niveau supérieur et plus propre. À moins que vous ne sachiez vraiment ce que vous faites, vous devriez les utiliser si vous avez besoin de performances similaires à celles d’un tableau. Bien sûr, certaines mises en garde s’appliquent toujours – un tableau mutable comme les structures de données ne jouent pas bien dans les langages paresseux purs. Pourtant, parfois vous voulez que la performance O (1), et Data.Vector donne dans un paquet utilisable.

Vous avez d’autres options

Si vous voulez simplement des listes capables d’insérer efficacement à la fin, vous pouvez utiliser une liste de différences . Le meilleur exemple de perte de performances des listes a tendance à provenir de [Char] que le prélude a aliasé en tant que Ssortingng . Char listes de caractères sont pratiques, mais ont tendance à être de l’ordre de 20 fois plus lentes que les chaînes C, donc n’hésitez pas à utiliser Data.Text ou le très rapide Data.ByteSsortingng . Je suis sûr qu’il existe d’autres bibliothèques orientées séquences auxquelles je ne pense pas en ce moment.

Conclusion

90 +% du temps, j’ai besoin d’une collection séquentielle dans les listes de Haskell sont la bonne structure de données. Les listes sont comme les iterators, les fonctions qui consumnt des listes peuvent facilement être utilisées avec n’importe laquelle de ces structures de données en utilisant les fonctions toList qu’elles toList . Dans un monde meilleur, le prélude serait entièrement paramésortingque en ce qui concerne le type de conteneur qu’il utilise, mais actuellement [] la bibliothèque standard est utilisée. Donc, utiliser des listes (presque) partout est certainement correct.
Vous pouvez obtenir des versions entièrement paramésortingques de la plupart des fonctions de liste (et sont nobles pour les utiliser)

 Prelude.map ---> Prelude.fmap (works for every Functor) Prelude.foldr/foldl/etc ---> Data.Foldable.foldr/foldl/etc Prelude.sequence ---> Data.Traversable.sequence etc 

En fait, Data.Traversable définit une API qui est plus ou moins universelle sur tout élément “list like”.

Cependant, bien que vous puissiez être bon et écrire uniquement du code entièrement paramésortingque, la plupart d’entre nous ne le sont pas et utilisons la liste partout. Si vous apprenez, je vous suggère fortement de faire aussi.


EDIT: Basé sur des commentaires, je réalise que je n’ai jamais expliqué quand utiliser Data.Vector vs Data.Sequence . Les tableaux et les vecteurs fournissent des opérations d’indexation et de découpage extrêmement rapides, mais sont des structures de données fondamentalement transitoires (impératives). Les structures de données fonctionnelles pures telles que Data.Sequence et [] permettent de produire efficacement de nouvelles valeurs à partir d’anciennes valeurs, comme si vous aviez modifié les anciennes valeurs.

  newList oldList = 7 : drop 5 oldList 

ne modifie pas l’ancienne liste, et il n’est pas nécessaire de la copier. Donc, même si oldList est incroyablement long, cette “modification” sera très rapide. De même

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

produira une nouvelle séquence avec une nouvelle newValue à la place de son élément 3000. Encore une fois, cela ne détruit pas l’ancienne séquence, elle en crée simplement une nouvelle. Mais, cela se fait très efficacement, en prenant O (log (min (k, kn))) où n est la longueur de la séquence, et k est l’index que vous modifiez.

Vous ne pouvez pas facilement faire cela avec les Vectors et les Arrays . Ils peuvent être modifiés, mais il s’agit d’une modification impérative et ne peuvent donc pas être exécutés dans le code Haskell habituel. Cela signifie que les opérations dans le package Vector qui apportent des modifications comme snoc et cons doivent copier le vecteur entier, donc prenez le temps O(n) . La seule exception à cela est que vous pouvez utiliser la version mutable ( Vector.Mutable ) dans le ST monad (ou IO ) et faire toutes vos modifications comme vous le feriez dans un langage impératif. Lorsque vous avez terminé, vous “gelez” votre vecteur pour le transformer en structure immuable à utiliser avec du code pur.

Mon sentiment est que vous devriez utiliser par défaut Data.Sequence si une liste n’est pas appropriée. Utilisez Data.Vector uniquement si votre modèle d’utilisation n’implique pas de nombreuses modifications ou si vous avez besoin de performances extrêmement élevées dans les monades ST / IO.

Si tout ce discours de la monade ST vous laisse perplexe: autant de raisons de vous en tenir à pure et rapide Data.Sequence .