Donc, parfois, j’ai besoin d’écrire une structure de données que je ne trouve pas sur Hackage, ou ce que je trouve n’est pas testé ou de qualité suffisante pour que je puisse avoir confiance, ou bien c’est quelque chose que je ne veux pas être une dépendance. Je suis en train de lire le livre d’Okasaki en ce moment, et c’est plutôt bien d’expliquer comment concevoir des structures de données asymptotiquement rapides.
Cependant, je travaille spécifiquement avec GHC. Des facteurs constants sont un gros problème pour mes applications. L’utilisation de la mémoire est aussi un gros problème pour moi. J’ai donc des questions spécifiques sur le GHC.
En particulier
J’ai parcouru différents endroits sur le Web et j’ai une vague idée de la façon de travailler avec GHC, par exemple, en examinant les principaux résultats, en utilisant les UNPACK
UNPACK, etc. Mais je ne suis pas sûr de l’avoir.
J’ai donc ouvert ma bibliothèque de structures de données préférée, mes conteneurs, et j’ai regardé le module Data.Sequence. Je ne peux pas dire que je comprends beaucoup de ce qu’ils font pour rendre Seq rapide.
La première chose qui attire mon attention est la définition de FingerTree a
. Je suppose que c’est juste que je ne suis pas familier avec les arbres de doigt cependant. La deuxième chose qui attire mon attention est tous les pragmas SPECIALIZE
. Je n’ai aucune idée de ce qui se passe ici, et je suis très curieux, car ils sont éparpillés dans tout le code.
De nombreuses fonctions sont également associées à un pragma INLINE
. Je peux deviner ce que cela signifie, mais comment puis-je porter un jugement sur les fonctions INLINE
?
Les choses deviennent vraiment intéressantes autour de la ligne 475, une section intitulée «Construction Applicative». Ils définissent un wrapper newtype pour représenter la monade d’identité, ils écrivent leur propre copie de la monade à état ssortingct, et ils ont une fonction définie par l’ applicativeTree
Je n’ai aucune idée de ce qui se passe ici. Quelle sorcellerie est utilisée pour augmenter le partage?
Quoi qu’il en soit, je ne suis pas sûr qu’il y ait beaucoup à apprendre de Data.Sequence. Existe-t-il d’autres «programmes modèles» que je peux lire pour acquérir de la sagesse? J’aimerais vraiment savoir comment faire évoluer mes structures de données lorsque j’aurais vraiment besoin d’eux pour aller plus vite. Une chose en particulier consiste à écrire des structures de données qui facilitent la fusion et à rédiger de bonnes règles de fusion.
C’est un gros sujet! La plupart ont été expliquées ailleurs, alors je n’essaierai pas d’écrire un chapitre de livre ici. Au lieu:
Johan Tibell écrit beaucoup sur ce sujet:
Et quelques choses d’ici:
Et d’autres choses:
applicativeTree
est assez sophistiqué, mais surtout en ce qui concerne les FingerTrees en particulier, qui sont eux-mêmes une structure de données très sophistiquée. Nous avons discuté des subtilités de la théorie . Notez que applicativeTree
est écrit pour fonctionner sur n’importe quel applicatif. Il se trouve que lorsqu’il est spécialisé dans les Id
il peut partager des nœuds d’une manière qui ne le serait pas autrement. Vous pouvez travailler vous-même sur la spécialisation en insérant les méthodes d’ Id
et en observant ce qui se passe. Notez que cette spécialisation est utilisée dans un seul endroit – la fonction de replicate
O (log n). Le fait que la fonction plus générale se spécialise clairement dans le cas constant est une réutilisation de code très intelligente, mais c’est vraiment tout.
En général, Sequence
enseigne plus sur la conception de structures de données persistantes que sur toutes les astuces pour améliorer les performances, je pense. Les suggestions de Dons sont bien sûr excellentes. Je voudrais aussi parcourir la source des IntMap
vraiment canoniques et optimisées – Map
, IntMap
, Set
et IntSet
en particulier. Parallèlement à ceux-ci, il convient de jeter un coup d’œil sur l’ article de Milan sur ses améliorations apscopes aux conteneurs .