Ensemble général

Une application a souvent besoin de manipuler des ensembles d'objets. Il est tentant de créer un type abstrait ensemble pour satisfaire ce type de besoin. Mais il y a une très bonne raison pour laquelle on ne trouve jamais de type abstrait ensemble dans la littérature sur l'algorithmique et les structures de données : c'est qu'il n'est pas possible d'en créer un avec des opérations efficaces.

Un ensemble général doit au moins accepter les opérations suivantes :

• création d'un ensemble vide et éventuellement d'un singleton (ensemble à un seul élément) à partir d'un élément du domaine ;
• test pour vérifier si un élément appartient à un ensemble ;
• union de deux ensembles (et insertion d'un élément dans un ensemble si la création d'un singleton n'est pas possible) ;
• intersection de deux ensembles ;
• différence entre deux ensembles et suppression d'un élément d'un ensemble si la création d'un singleton n'est pas possible ;
• itération sur les éléments d'un ensemble ou au moins récupération d'un élément arbitraire d'un ensemble.

Un tel type doit accepter n'importe quel domaine disposant d'une opération pour tester l'égalité de deux éléments du domaine. Des structures efficaces comme des arbres sont exclues puisque elles nécessitent un domaine ordonné.

Le candidat le plus prometteur est une table de hachage. L'insertion d'un élément dans une table de hachage est une opération rapide à condition que la table soit modifiée (implémentée de manière impérative). Seule une interface impérative sera donc présentée. Si l'on accepte que les opérations d'insertion, de suppression et de test d'appartenance dans une table de hachage aient une complexité de $O(1)$, il est alors possible d'implémenter les opérations de l'ensemble comme ceci :

• la création (vide ou singleton), le test d'appartenance, l'insertion et la suppression d'un élément sont des opérations trivialement possibles en temps constant ;
• l'itération sur les éléments de l'ensemble est trivialement possible en temps linéaire ;
• l'union peut être implémentée par une boucle sur l'un des deux ensembles (celui dont les éléments seront insérés dans l'autre) en temps linéaire ;
• l'intersection et la différence peuvent également être implémentées par une boucle sur les éléments d'un des ensembles en temps linéaire.

Mais le problème est la fonction de hachage. Dans une implémentation en Common Lisp il est raisonnable d'imaginer une fonction key pour déterminer une clé à utiliser pour le test d'égalité entre deux éléments. Le test d'égalité doit être fourni par le programmeur consommateur par exemple pendant la création de l'ensemble. C'est aussi à cette clé que doit être appliquée la fonction de hachage. Si la valeur de la clé est un élément de type simple comme un nombre ou un symbole, il n'y a pas de problème, car les tables de hachage Common Lisp sont capables de s'en servir directement.

Par contre, si la clé est une valeur structurée (par exemple une liste, un vecteur, une instance de classe, etc), il y a un problème : il est impossible pour une implémentation de déterminer automatiquement la fonction de hachage de même qu'il est impossible de déterminer la fonction de test d'égalité. Il va donc falloir que le programmeur consommateur fournisse cette fonction. Mais cette nécessité implique de divulguer le fait que le type abstrait ensemble est implémenté par des tables de hachage. Ce sera donc un type pas tout à fait abstrait!

Mise à part une table de hachage, nous ne connaissons pas de structure de données permettant une implémentation efficace de toutes les ci-dessus sur les ensembles opérations décrites.

C'est pourquoi dans la littérature sur l'algorithmique et les structures de données, la discussion est centrée sur des ensembles ayant l'une des caractéristiques suivantes :

• le domaine est totalement ordonné, ce qui fournit une fonction de comparaison entre deux éléments ;
• le jeu d'opérations est restreint par rapport à celui d'un ensemble général ;
• l'ensemble a une organisation plus structurée que celle d'un ensemble général (pile, file, etc).

Si le domaine est totalement ordonné, il est possible d'utiliser un arbre équilibré pour représenter un ensemble. Les opérations simples sont alors possibles en $O(\texttt{log} n)$ et l'union, l'intersection et la différence sont possibles en $O(n \texttt{log} n)$.

L'utilisation d'une liste ou d'un vecteur pour représenter un ensemble général peut être acceptable pour des ensembles de petite taille, mais inacceptable en général, car les opérations simples coûtent alors $O(n)$ et les opérations complexes coûtent $O(n^2)$.

Nous allons décrire ici une implémentation d'un type ensemble général dont les clés peuvent être comparées avec la fonction eql. Dans ce cas, une table de hachage avec le test par défaut peut être utilisée.