Comment choisir une structure de données de dictionnaire fonctionnelle?

10

J'ai lu un peu sur les structures de données suivantes:

  • Essais de hachage idéaux de Bagwell
  • Tables de hachage dynamiques de Larson
  • Arbres rouges-noirs
  • Arbres Patricia

... et je suis sûr qu'il y en a beaucoup d'autres. J'ai vu très peu de choses sur ce que chacun est le mieux adapté, ou pourquoi je choisirais l'un plutôt que l'autre. Voici donc quelques questions dans ce sens:

  1. Quelles structures de données de dictionnaire fonctionnelles sont importantes à connaître?
  2. Quels sont les avantages et les inconvénients de ces approches?
  3. Quand est-il judicieux d'utiliser une structure de données plus impérative?

Les numéros 2 et 3 sont cependant les plus importants. :-)

ds.data-structures functional-programming tree hash-function Jason
la source
Connexes: Quoi de neuf dans les structures de données purement fonctionnelles depuis Okasaki? (Cette question n'est pas limitée aux dictionnaires.)
Tsuyoshi Ito
Cette question (autre que l'article numéroté 3) a le sentiment d'une [grande liste].
Kaveh
2
il serait utile de savoir si la question liée ci-dessus répond à vos préoccupations, et sinon pourquoi?
Suresh Venkat
@Suresh - Cela répond # 1, mais 2 et 3 étaient les plus importants. Je recherche principalement une vue d'ensemble afin de pouvoir déterminer celles qui méritent d'être étudiées plus en profondeur.
Jason
2
D'accord. il peut donc être utile de modifier la question.
Suresh Venkat

Réponses:

16

Je ne peux pas vraiment répondre # 2 sans me perdre (il y a trop de dimensions le long desquelles vous pouvez comparer ces structures), mais pour # 3 la réponse est assez simple.

Utilisez une structure de données impérative si: (a) il n'y a absolument aucun alias, ou (b) vous avez vraiment besoin d'utiliser l'alias pour une diffusion efficace.

S'il n'y a aucun alias de votre structure de données, vous ne profitez pas du fait que les structures de données fonctionnelles sont persistantes. Il n'y a donc aucune raison de payer leur coût. Il y a deux mises en garde à ce conseil. Tout d'abord, vous préférerez peut-être la simplicité de mise en œuvre d'une structure de données fonctionnelle: la mise en œuvre de la suppression pour un arbre rouge-noir fonctionnel vous fera malédire, mais la mise en œuvre de la suppression dans un arbre rouge-noir impératif avec des pointeurs parent vous laissera envisager le suicide. Deuxièmement, l'affectation peut être plus coûteuse que ce à quoi vous vous attendez dans un langage gc'd, car les écritures peuvent faire sortir les structures de données de la jeune génération. Nous n'avons vraiment pas une bonne théorie des effets de cache et de gc, vous n'avez donc pas d'autre choix que de faire un benchmarking.

Deuxièmement, si vous avez besoin d'un canal de diffusion, une structure de données partagée est un excellent moyen de le faire. Avec une mise à jour à temps constant, vous pouvez indiquer arbitrairement à de nombreuses autres personnes qu'une valeur a changé. (C'est pourquoi union-find est une excellente structure de données.) Avec une configuration purement fonctionnelle, vous devez soit modifier toutes ces autres personnes, soit leur donner des pointeurs abstraits dans un état que vous codez manuellement (ce qui est une sorte d'obus chose à faire).

Si vous ne voulez pas raisonner sur l'alias et la propriété des objets, ou si vous avez besoin de plusieurs versions de la même structure de données (vous avez besoin d'une nouvelle et d'une ancienne version, par exemple), alors utilisez simplement une structure de données fonctionnelle.

L'endroit où je trouve le plus difficile à suivre ces conseils est avec les algorithmes de graphes. Il existe de nombreux algorithmes de graphes impératifs vraiment élégants, mais il arrive souvent (par exemple, lors de l'écriture de compilateurs) que vous souhaitiez également la persistance. Les gens essaient généralement de diviser la différence et utilisent l'algorithme impératif cool mais essaient de boulonner le versioning sur le côté pour obtenir la persistance. C'est généralement assez horrible, plein de bugs, et enclin à perdre l'avantage de performance de l'algorithme impératif.

Neel Krishnaswami
la source
2
qu'est-ce que l'aliasing dans ce contexte?
Suresh Venkat
6
L'aliasing est lorsque vous avez plusieurs références à la même donnée. Si ces données sont modifiables, le raisonnement sur un programme qui les utilise doit explicitement prendre en compte tous les autres sous-programmes qui peuvent y accéder et les modifier. Si cette donnée est immuable, vous pouvez raisonner localement sur un programme qui l'utilise, en ignorant l'aliasing, car vous ne savez personne qui peut accéder aux données ne peut la modifier.
Neel Krishnaswami
"mais la mise en œuvre de la suppression dans un arbre rouge-noir impératif avec des pointeurs parent vous laissera envisager le suicide" Découvrez les arbres rouge-noir inclinés à gauche de Sedgewick. Le cas général de suppression est réduit à delete-min par une astuce standard, et delete-min lui-même est très simple pour les arbres LLRB. Aucun pointeur parent nécessaire.
Per Vognsen
1
"C'est généralement assez horrible, plein de bugs, et enclin à perdre l'avantage de performance de l'algorithme impératif." L'article de Norman Ramsey sur l'utilisation des fermetures à glissière pour les graphiques de flux de contrôle dans un compilateur d'optimisation fournit un exemple d'un compromis convaincant. Vous disposez effectivement d'un tas local pour prendre en charge un recâblage en place simple et efficace des références entre les blocs de base dans un CFG, mais la manipulation du contenu des blocs de base est fonctionnelle (ou semi-fonctionnelle, selon votre vision philosophique des fermetures à glissière).
Per Vognsen
1

Quelles structures de données de dictionnaire fonctionnelles sont importantes à connaître?

Les arbres binaires équilibrés en hauteur et leurs essais sont un bon compromis tous azimuts. Aussi:

  • Arbres Patricia.
  • Hash essaie.

Quels sont les avantages et les inconvénients de ces approches?

Les arbres binaires à hauteur équilibrée et leurs essais sont un bon compromis global pour les clés atomiques. Les essais sont les mêmes pour les clés qui sont des séquences, par exemple les clés de chaîne.

Les arbres Patricia peuvent être plusieurs fois plus rapides mais ne permettent que des clés entières.

Les tentatives de hachage peuvent être plusieurs fois plus rapides que les arbres binaires équilibrés, en particulier si le hachage est moins cher que la comparaison et que le polymorphisme a un surcoût (par exemple des chaînes sur .NET) et que l'écriture de pointeurs dans le tas est rapide (par exemple, les machines virtuelles comme la JVM et le CLR qui ont été optimisé pour les langages impératifs plutôt que les langages fonctionnels). Les tentatives de hachage permettent également l'utilisation interne de la mutation comme optimisation.

Les arbres rouge-noir sont moins importants car ils ne présentent pas d'avantages significatifs par rapport aux arbres à hauteur équilibrée mais présentent l'inconvénient majeur de ne pas permettre une union, une intersection et une différence efficaces.

De même, les arbres à doigts ne sont pas beaucoup mieux en pratique.

Quand est-il judicieux d'utiliser une structure de données plus impérative?

Lorsque votre dictionnaire est rempli une fois, puis utilisé uniquement pour les recherches, c'est-à-dire gelé.

Lorsque vous avez besoin de performances (une table de hachage décente comme le .NET Dictionaryest généralement 10 à 40 × plus rapide que tout dictionnaire générique purement fonctionnel).

Lorsque vous avez besoin d'un dictionnaire faible car il n'existe pas de dictionnaire faible purement fonctionnel connu.

Jon Harrop
la source