J'apprends Haskell et j'ai lu quelques articles concernant les différences de performances des listes Haskell et (insérez votre langue) les tableaux.

Étant un apprenant, j'utilise évidemment des listes sans même penser à la différence de performance. J'ai récemment commencé à enquêter et trouvé de nombreuses bibliothèques de structures de données disponibles dans Haskell.

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

En outre, existe-t-il des modèles courants dans lesquels vous utiliseriez une structure de données au lieu d'une autre?

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

Listes Rock

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

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

Les listes vous donnent ϴ (1) contre et la correspondance des motifs. La bibliothèque standard, et d'ailleurs le prélude, est plein de fonctions de liste utiles qui devraient litière votre code ( foldr, map, filter). Les listes sont persistantes , c'est-à-dire purement fonctionnelles, ce qui est très agréable. Les listes Haskell ne sont pas vraiment des "listes" car elles sont coinductives (d'autres langages appellent ces flux) donc des choses comme

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

fonctionne à merveille. Une infinité de structures de données rocheuses.

Les listes dans Haskell fournissent une interface un peu comme les itérateurs dans les langues impératives (à cause de la paresse). Il est donc 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 ennuyeux. De plus, les ajouts peuvent être lents ++, mais le modèle d'évaluation paresseux de Haskell signifie que ceux-ci peuvent être traités comme entièrement amortis, s'ils se produisent.

Le deuxième problème avec les listes est qu'elles ont une mauvaise localisation des données. Les vrais processeurs subissent des constantes élevées lorsque les objets en mémoire ne sont pas disposés côte à côte. Ainsi, en C ++ std::vectora un "snoc" plus rapide (mettant les objets à la fin) que toute structure de données de liste liée pure que je connais, bien que ce ne soit pas une structure de données persistante donc moins conviviale que les listes de Haskell.

Le troisième problème avec les listes est qu'elles ont une faible efficacité spatiale. Des tas de pointeurs supplémentaires augmentent votre stockage (par un facteur constant).

Les séquences sont fonctionnelles

Data.Sequenceest basé en interne sur des arbres à doigts (je sais, vous ne voulez pas le savoir) ce qui signifie qu'ils ont de belles propriétés

1. Purement fonctionnel. Data.Sequenceest une structure de données entièrement persistante.
2. Un 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 ajouter des arbres. Au niveau des listes de choses les plus rapides, Data.Sequencec'est tout au plus une constante plus lente.
3. Access (log n) accès au milieu de la séquence. Cela inclut l'insertion de valeurs pour créer de nouvelles séquences
4. API de haute qualité

En revanche, Data.Sequencene fait pas grand-chose pour le problème de localisation des données et ne fonctionne que pour les collections finies (c'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 de CS, mais ils ne correspondent pas très bien au monde fonctionnel pur et paresseux. Les tableaux fournissent ϴ (1) un accès au milieu de la collection et des facteurs constants de localisation des données exceptionnellement bons. Mais, comme ils ne s'intègrent pas très bien dans Haskell, ils sont difficiles à utiliser. Il existe en fait une multitude de types de tableaux différents dans la bibliothèque standard actuelle. Il s'agit notamment de tableaux entièrement persistants, de tableaux mutables pour la monade IO, de tableaux mutables pour la monade ST et de versions non encadrées de ce qui précède. Pour en savoir plus, consultez le wiki haskell

Le vecteur est un "meilleur" tableau

Le Data.Vectorpackage offre toutes les qualités du tableau, dans un niveau supérieur et une API plus propre. À moins que vous ne sachiez vraiment ce que vous faites, vous devez les utiliser si vous avez besoin de performances de type tableau. Bien sûr, certaines mises en garde s'appliquent toujours - les tableaux mutables comme les structures de données ne jouent tout simplement pas bien dans les langages paresseux purs. Pourtant, parfois vous voulez cette performance O (1), et vous la Data.Vectordonne dans un package utilisable.

Vous avez d'autres options

Si vous voulez juste des listes avec la capacité d'insérer efficacement à la fin, vous pouvez utiliser une liste de différences . Le meilleur exemple de listes qui bousillent les performances a tendance à provenir du [Char]prélude String. CharLes listes sont pratiques, mais ont tendance à fonctionner 20 fois plus lentement que les cordes C, alors n'hésitez pas à les utiliser Data.Textou à les utiliser très rapidement Data.ByteString. Je suis sûr qu'il y a 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 Haskell sont la bonne structure de données. Les listes sont comme des itérateurs, les fonctions qui consomment des listes peuvent facilement être utilisées avec n'importe laquelle de ces autres structures de données en utilisant les toListfonctions fournies . Dans un monde meilleur, le prélude serait entièrement paramétrique quant au type de conteneur qu'il utilise, mais []jette actuellement la bibliothèque standard. Donc, utiliser des listes (presque) partout est définitivement correct.
Vous pouvez obtenir des versions entièrement paramétriques de la plupart des fonctions de liste (et il est noble de 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.Traversabledéfinit une API qui est plus ou moins universelle sur tout ce qui "liste comme".

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

EDIT: D' après les commentaires que je réalise que je n'expliqué quand utiliser Data.Vectorvs 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 aiment Data.Sequenceet []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 n'a pas à la copier. Donc même si elle oldListest incroyablement longue, cette "modification" sera très rapide. De même

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

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

Vous ne pouvez pas facilement le faire avec Vectorset Arrays. Ils peuvent être modifiés, mais c'est une véritable modification impérative, et ne peut donc pas être fait dans le code Haskell normal. Cela signifie que les opérations dans le Vectorpackage qui apportent des modifications snocet consdoivent copier le vecteur entier prennent donc du O(n)temps. La seule exception à cela est que vous pouvez utiliser la version mutable ( Vector.Mutable) à l'intérieur de la STmonade (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 la structure immuable que vous souhaitez utiliser avec du code pur.

Mon sentiment est que vous devriez utiliser par défaut Data.Sequencesi une liste n'est pas appropriée. À utiliser Data.Vectoruniquement 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 sur la STmonade vous laisse perplexe: raison de plus pour rester pur et rapide et beau Data.Sequence.