Ensemble (type de données abstrait)

En informatique , un ensemble est un type de données abstrait qui peut stocker des valeurs uniques, sans ordre particulier . Il s'agit d'une implémentation informatique du concept mathématique d' ensemble fini . Contrairement à la plupart des autres types de collections , plutôt que de récupérer un élément spécifique d'un ensemble, on teste généralement une valeur pour déterminer son appartenance à un ensemble.

Certaines structures de données d'ensemble sont conçues pour des ensembles statiques ou figés qui ne changent pas après leur construction. Les ensembles statiques autorisent uniquement les opérations de requête sur leurs éléments, comme vérifier si une valeur donnée est présente dans l'ensemble ou énumérer les valeurs dans un ordre arbitraire. D'autres variantes, appelées ensembles dynamiques ou mutables , autorisent également l'insertion et la suppression d'éléments de l'ensemble.

Un multi-ensemble est un type particulier d'ensemble dans lequel un élément peut apparaître plusieurs fois dans l'ensemble.

En théorie des types , les ensembles sont généralement identifiés par leur fonction indicatrice (fonction caractéristique) : en conséquence, un ensemble de valeurs de type peut être désigné par ou . (Les sous-types et les sous-ensembles peuvent être modélisés par des types de raffinement , et les ensembles quotients peuvent être remplacés par des sétéoïdes .) La fonction caractéristique d'un ensemble est définie comme suit :

En théorie, de nombreuses autres structures de données abstraites peuvent être considérées comme des structures d'ensemble avec des opérations supplémentaires et/ou des axiomes supplémentaires imposés aux opérations standard. Par exemple, un tas abstrait peut être considéré comme une structure d'ensemble avec une opération qui renvoie l'élément de plus petite valeur. min(S)

On peut définir les opérations de l' algèbre des ensembles :

• union(S,T): renvoie l' union des ensembles S et T .
• intersection(S,T): renvoie l' intersection des ensembles S et T .
• difference(S,T): renvoie la différence des ensembles S et T .
• subset(S,T):un prédicat qui teste si l'ensemble S est un sous-ensemble de l' ensemble T.

Les opérations typiques qui peuvent être fournies par une structure d’ensemble statique S sont :

• is_element_of(x,S): vérifie si la valeur x est dans l'ensemble S .
• is_empty(S): vérifie si l'ensemble S est vide.
• size(S)ou : renvoie le nombre d'éléments dans S .cardinality(S)
• iterate(S): renvoie une fonction qui renvoie une valeur supplémentaire de S à chaque appel, dans un ordre arbitraire.
• enumerate(S): renvoie une liste contenant les éléments de S dans un ordre arbitraire.
• build(x1,x2,…,xn,): crée une structure d'ensemble avec les valeurs x ₁ , x ₂ ,..., x _n .
• create_from(collection): crée une nouvelle structure d'ensemble contenant tous les éléments de la collection donnée ou tous les éléments renvoyés par l' itérateur donné .

Les structures d’ensemble dynamiques ajoutent généralement :

• create(): crée une nouvelle structure d'ensemble initialement vide.
  • create_with_capacity(n): crée une nouvelle structure d'ensemble, initialement vide mais capable de contenir jusqu'à n éléments.
• add(S,x): ajoute l'élément x à S , s'il n'est pas déjà présent.
• remove(S, x): supprime l'élément x de S , s'il est présent.
• capacity(S): renvoie le nombre maximal de valeurs que S peut contenir.

Certaines structures d'ensembles peuvent n'autoriser que certaines de ces opérations. Le coût de chaque opération dépendra de l'implémentation, et éventuellement aussi des valeurs particulières stockées dans l'ensemble, et de l'ordre dans lequel elles sont insérées.

Il existe de nombreuses autres opérations qui peuvent (en principe) être définies en fonction de ce qui précède, telles que :

• pop(S): renvoie un élément arbitraire de S , le supprimant de S .
• pick(S): renvoie un élément arbitraire de S . Fonctionnellement, le mutateur poppeut être interprété comme la paire de sélecteurs (pick, rest),où restrenvoie l'ensemble constitué de tous les éléments à l'exception de l'élément arbitraire. Peut être interprété en termes de iterate.
• map(F,S): renvoie l'ensemble des valeurs distinctes résultant de l'application de la fonction F à chaque élément de S .
• filter(P,S): renvoie le sous-ensemble contenant tous les éléments de S qui satisfont un prédicat P donné .
• fold(A0,F,S): renvoie la valeur A _{| S |} après application pour chaque élément e de S, pour une opération binaire F. F doit être associative et commutative pour que cela soit bien défini.Ai+1 := F(Ai, e)
• clear(S): supprimer tous les éléments de S .
• equal(S1', S2'): vérifie si les deux ensembles donnés sont égaux (c'est-à-dire qu'ils contiennent tous et uniquement les mêmes éléments).
• hash(S): renvoie une valeur de hachage pour l'ensemble statique S tel que si alorsequal(S1, S2)hash(S1) = hash(S2)

D'autres opérations peuvent être définies pour des ensembles avec des éléments d'un type spécial :

• sum(S): renvoie la somme de tous les éléments de S pour une certaine définition de « somme ». Par exemple, sur des entiers ou des réels, elle peut être définie comme .fold(0, add, S)
• collapse(S): étant donné un ensemble d'ensembles, renvoie l'union. Par exemple, collapse({{1}, {2, 3}}) == {1, 2, 3}. Peut être considéré comme une sorte de sum.
• flatten(S): étant donné un ensemble composé d'ensembles et d'éléments atomiques (éléments qui ne sont pas des ensembles), renvoie un ensemble dont les éléments sont les éléments atomiques de l'ensemble de niveau supérieur d'origine ou les éléments des ensembles qu'il contient. En d'autres termes, supprimez un niveau d'imbrication – comme collapse,mais autorisez les atomes. Cela peut être fait une seule fois, ou en aplatissant de manière récursive pour obtenir un ensemble d'éléments atomiques uniquement. Par exemple, flatten({1, {2, 3}}) == {1, 2, 3}.
• nearest(S,x): renvoie l'élément de S qui est le plus proche en valeur de x (selon une certaine métrique ).
• min(S), : renvoie l'élément minimum/maximum de S .max(S)

Les ensembles peuvent être implémentés à l'aide de diverses structures de données , qui offrent différents compromis de temps et d'espace pour diverses opérations. Certaines implémentations sont conçues pour améliorer l'efficacité d'opérations très spécialisées, telles que nearestou union. Les implémentations décrites comme « à usage général » s'efforcent généralement d'optimiser les opérations element_of, addet delete. Une implémentation simple consiste à utiliser une liste , en ignorant l'ordre des éléments et en prenant soin d'éviter les valeurs répétées. C'est simple mais inefficace, car les opérations comme l'appartenance à un ensemble ou la suppression d'éléments sont O ( n ), car elles nécessitent l'analyse de la liste entière. Les ensembles sont souvent implémentés à l'aide de structures de données plus efficaces, en particulier diverses variantes d' arbres , d'essais ou de tables de hachage .

Comme les ensembles peuvent être interprétés comme une sorte de carte (par la fonction indicatrice), les ensembles sont généralement implémentés de la même manière que les cartes (partielles) ( tableaux associatifs ) – dans ce cas où la valeur de chaque paire clé-valeur a le type unitaire ou une valeur sentinelle (comme 1) – à savoir, un arbre de recherche binaire auto-équilibré pour les ensembles triés (qui a O(log n) pour la plupart des opérations), ou une table de hachage pour les ensembles non triés (qui a O(1) cas moyen, mais O(n) cas le plus défavorable, pour la plupart des opérations). Une table de hachage linéaire triée peut être utilisée pour fournir des ensembles ordonnés de manière déterministe.

De plus, dans les langages qui prennent en charge les maps mais pas les ensembles, les ensembles peuvent être implémentés en termes de maps. Par exemple, un idiome de programmation courant en Perl qui convertit un tableau en un hachage dont les valeurs sont la valeur sentinelle 1, pour une utilisation en tant qu'ensemble, est :

mes %éléments = carte { $_ => 1 } @elements ;

D'autres méthodes populaires incluent les tableaux . En particulier, un sous-ensemble des entiers 1.. n peut être implémenté efficacement sous forme de tableau de n bits , qui prend également en charge des opérations d'union et d'intersection très efficaces. Une carte Bloom implémente un ensemble de manière probabiliste, en utilisant une représentation très compacte mais en risquant un faible risque de faux positifs sur les requêtes.

Les opérations booléennes sur les ensembles peuvent être implémentées en termes d'opérations plus élémentaires ( pop, clearet add), mais des algorithmes spécialisés peuvent produire des limites de temps asymptotiques plus basses. Si les ensembles sont implémentés sous forme de listes triées, par exemple, l'algorithme naïf pour prendra un temps proportionnel à la longueur m de S multipliée par la longueur n de T ; alors qu'une variante de l' algorithme de fusion de listes fera le travail en un temps proportionnel à m + n . De plus, il existe des structures de données d'ensemble spécialisées (telles que la structure de données union-find ) qui sont optimisées pour une ou plusieurs de ces opérations, au détriment des autres. union(S,T)

L'un des premiers langages à prendre en charge les ensembles était Pascal ; de nombreux langages l'incluent désormais, que ce soit dans le langage de base ou dans une bibliothèque standard .

• En C++ , la bibliothèque de modèles standard (STL) fournit la setclasse de modèle, qui est généralement implémentée à l'aide d'un arbre de recherche binaire (par exemple, un arbre rouge-noir ) ; la STL de SGIhash_set fournit également la classe de modèle, qui implémente un ensemble à l'aide d'une table de hachage. C++11 prend en charge la unordered_setclasse de modèle, qui est implémentée à l'aide d'une table de hachage. Dans les ensembles, les éléments eux-mêmes sont les clés, contrairement aux conteneurs séquencés, où les éléments sont accessibles à l'aide de leur position (relative ou absolue). Les éléments d'un ensemble doivent avoir un ordre faible strict.
• La bibliothèque standard Rust fournit les types génériques HashSetet BTreeSet.
• Java propose l' Set interface pour prendre en charge les ensembles (avec la HashSetclasse l'implémentant à l'aide d'une table de hachage) et la SortedSetsous-interface pour prendre en charge les ensembles triés (avec la TreeSetclasse l'implémentant à l'aide d'un arbre de recherche binaire).
• Le framework Foundation d' Apple (qui fait partie de Cocoa ) fournit les classes Objective-CNSSet , NSMutableSet, NSCountedSet, NSOrderedSetet NSMutableOrderedSet. Les API CoreFoundation fournissent les types CFSet et CFMutableSet à utiliser en C .
• Python a des types set et frozenset intégrés depuis la version 2.4, et depuis Python 3.0 et 2.7, prend en charge les littéraux d'ensemble non vides à l'aide d'une syntaxe d'accolades, par exemple :{x, y, z} ; les ensembles vides doivent être créés à l'aide de set(), car Python utilise {}pour représenter le dictionnaire vide.
• Le .NET Framework fournit l’interface générique HashSetet SortedSetles classes qui implémentent l’ ISetinterface générique.
• La bibliothèque de classes de SmalltalkSet inclut et IdentitySet, qui utilisent respectivement l'égalité et l'identité pour les tests d'inclusion. De nombreux dialectes proposent des variantes pour le stockage compressé ( NumberSet, CharacterSet), pour le tri ( OrderedSet, SortedSet, etc.) ou pour les références faibles ( WeakIdentitySet).
• La bibliothèque standard de Rubyset comprend un module qui contient Setdes SortedSetclasses qui implémentent des ensembles à l'aide de tables de hachage, ces dernières permettant l'itération dans l'ordre trié.
• La bibliothèque standard d' OCamlSet contient un module qui implémente une structure de données d'ensemble fonctionnelle utilisant des arbres de recherche binaires.
• L' implémentation GHC de Haskell fournit un Data.Setmodule qui implémente des ensembles immuables à l'aide d'arbres de recherche binaires.
• Le package Tcl Tcllib fournit un module d'ensemble qui implémente une structure de données d'ensemble basée sur des listes TCL.
• La bibliothèque standard Swift contient un Settype, depuis Swift 1.2.
• JavaScript a été introduit Setcomme objet intégré standard avec la norme ECMAScript 2015 .
• La bibliothèque standard d' Erlangsets possède un module.
• Clojure a une syntaxe littérale pour les ensembles hachés et implémente également les ensembles triés.
• LabVIEW dispose d'un support natif pour les ensembles, à partir de la version 2019.
• Ada fournit les packages Ada.Containers.Hashed_Setset Ada.Containers.Ordered_Sets.

Comme indiqué dans la section précédente, dans les langages qui ne prennent pas directement en charge les ensembles mais prennent en charge les tableaux associatifs , les ensembles peuvent être émulés à l'aide de tableaux associatifs, en utilisant les éléments comme clés et en utilisant une valeur fictive comme valeurs, qui sont ignorées.

Une généralisation de la notion d'ensemble est celle d'un multiset ou bag , qui est similaire à un ensemble mais autorise des valeurs répétées (« égales ») (doublons). Ceci est utilisé dans deux sens distincts : soit les valeurs égales sont considérées comme identiques et sont simplement comptées, soit les valeurs égales sont considérées comme équivalentes et sont stockées comme des éléments distincts. Par exemple, étant donné une liste de personnes (par nom) et d'âges (en années), on pourrait construire un multiset d'âges, qui compte simplement le nombre de personnes d'un âge donné. Alternativement, on peut construire un multiset de personnes, où deux personnes sont considérées comme équivalentes si leurs âges sont les mêmes (mais peuvent être des personnes différentes et avoir des noms différents), auquel cas chaque paire (nom, âge) doit être stockée, et la sélection sur un âge donné donne toutes les personnes d'un âge donné.

Formellement, il est possible que des objets en informatique soient considérés comme « égaux » sous une certaine relation d'équivalence , mais toujours distincts sous une autre relation. Certains types d'implémentations multi-ensembles stockeront des objets égaux distincts sous forme d'éléments séparés dans la structure de données ; tandis que d'autres la réduiront à une seule version (la première rencontrée) et conserveront un nombre entier positif de la multiplicité de l'élément.

Comme pour les ensembles, les multi-ensembles peuvent naturellement être implémentés à l'aide d'une table de hachage ou d'arbres, qui produisent des caractéristiques de performances différentes.

L'ensemble de tous les sacs de type T est donné par l'expression sac T. Si par multiset on considère que les éléments égaux sont identiques et qu'on les compte simplement, alors un multiset peut être interprété comme une fonction du domaine d'entrée aux entiers non négatifs ( nombres naturels ), généralisant l'identification d'un ensemble avec sa fonction indicatrice. Dans certains cas, un multiset dans ce sens de comptage peut être généralisé pour autoriser des valeurs négatives, comme en Python.

• La bibliothèque de modèles standard de C++ implémente à la fois les multi-ensembles triés et non triés. Elle fournit la multisetclasse pour le multi-ensemble trié, comme une sorte de conteneur associatif , qui implémente ce multi-ensemble à l'aide d'un arbre de recherche binaire auto-équilibré . Elle fournit la unordered_multisetclasse pour le multi-ensemble non trié, comme une sorte de conteneur associatif non ordonné , qui implémente ce multi-ensemble à l'aide d'une table de hachage . Le multi-ensemble non trié est standard à partir de C++11 ; auparavant, la STL de SGI fournit la hash_multisetclasse, qui a été copiée et finalement standardisée.
• Pour Java , des bibliothèques tierces fournissent des fonctionnalités multi-ensembles :
  • Apache Commons Collections fournit les interfaces Baget SortedBag, avec des classes d'implémentation telles que HashBaget TreeBag.
  • Google Guava fournit l' Multisetinterface, avec des classes d'implémentation comme HashMultisetet TreeMultiset.
• Apple fournit la NSCountedSetclasse dans le cadre de Cocoa et les types CFBaget CFMutableBagdans le cadre de CoreFoundation .
• La bibliothèque standard de Python inclut collections.Counter, qui est similaire à un multi-ensemble.
• Smalltalk inclut la Bagclasse, qui peut être instanciée pour utiliser l'identité ou l'égalité comme prédicat pour le test d'inclusion.

Lorsqu'une structure de données multi-ensemble n'est pas disponible, une solution de contournement consiste à utiliser un ensemble régulier, mais à remplacer le prédicat d'égalité de ses éléments pour toujours renvoyer « non égal » sur des objets distincts (cependant, ceux-ci ne pourront toujours pas stocker plusieurs occurrences du même objet) ou à utiliser un tableau associatif mappant les valeurs à leurs multiplicités entières (cela ne permettra pas du tout de faire la distinction entre des éléments égaux).

Opérations typiques sur les sacs :

• contains(B, x): vérifie si l'élément x est présent (au moins une fois) dans le sac B
• is_sub_bag(B1, B2): vérifie si chaque élément du sac B ₁ apparaît dans B ₁ pas plus souvent qu'il n'apparaît dans le sac B ₂ ; parfois noté B ₁ ⊑ B ₂ .
• count(B, x): renvoie le nombre de fois que l'élément x apparaît dans le sac B ; parfois noté B # x .
• scaled_by(B, n): étant donné un nombre naturel n , renvoie un sac qui contient les mêmes éléments que le sac B , sauf que chaque élément qui apparaît m fois dans B apparaît n * m fois dans le sac résultant ; parfois noté n ⊗ B .
• union(B1, B2): renvoie un sac contenant uniquement les valeurs qui apparaissent dans le sac B ₁ ou le sac B ₂ , sauf que le nombre de fois qu'une valeur x apparaît dans le sac résultant est égal à ( B ₁ # x) + ( B ₂ # x) ; parfois noté B ₁ ⊎ B ₂ .

Dans les bases de données relationnelles , une table peut être un ensemble (mathématique) ou un multi-ensemble, selon la présence de contraintes d'unicité sur certaines colonnes (ce qui la transforme en clé candidate ).

SQL permet la sélection de lignes à partir d'une table relationnelle : cette opération produira en général un multi-ensemble, à moins que le mot-clé ne DISTINCTsoit utilisé pour forcer les lignes à être toutes différentes, ou que la sélection inclue la clé primaire (ou une clé candidate).

Dans ANSI SQL, le MULTISETmot clé peut être utilisé pour transformer une sous-requête en une expression de collection :

SÉLECTIONNEZ expression1 , expression2 ... DE nom_table ...

est une sélection générale qui peut être utilisée comme expression de sous-requête d'une autre requête plus générale, tandis que

MULTISET ( SELECT expression1 , expression2 ... FROM nom_table ...)

transforme la sous-requête en une expression de collection qui peut être utilisée dans une autre requête ou dans une affectation à une colonne de type de collection approprié.