Performance statistique de cartes et d’ensembles purement fonctionnels

Étant donné une spécification de structure de données telle qu’une carte purement fonctionnelle avec des limites de complexité connues, il faut choisir entre plusieurs implémentations. Il y a un peu de folklore sur la façon de choisir le bon, par exemple les arbres rouge-noir sont considérés comme étant généralement plus rapides, mais les arbres AVL ont de meilleures performances sur les charges de travail avec beaucoup de recherches.

  1. Existe-t-il une présentation systématique (article publié) de ces connaissances (en ce qui concerne les ensembles / cartes)? Idéalement, je souhaiterais que l’parsing statistique soit effectuée sur un logiciel réel. On peut en conclure, par exemple, qu’il existe N types d’utilisation de la carte et répertorier la dissortingbution des probabilités en entrée pour chacun.

  2. Existe-t-il des points de référence systématiques pour tester la carte et définir les performances sur différentes dissortingbutions d’entrées?

  3. Existe-t-il des implémentations utilisant des algorithmes adaptatifs pour modifier la représentation en fonction de l’utilisation réelle?

    Ce sont essentiellement des thèmes de recherche et les résultats sont généralement présentés sous forme de conclusions, tandis que les données statistiques sont masquées. On peut cependant avoir une parsing statistique sur leurs propres données.

    Pour les benchmarks, mieux vaut parcourir les détails de la mise en œuvre.

    La troisième partie de la question est très subjective et les intentions réelles ne seront peut-être jamais connues au moment de la mise en œuvre. Cependant, les langages comme perl font de leur mieux pour mettre en œuvre des solutions hautement optimisées pour chaque opération.

    Ce qui suit pourrait être utile: Structures de données purement fonctionnelles par Chris Okasaki http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf