Ensemble (type de données abstrait) - Set (abstract data type)

En informatique , un ensemble est un type de données abstrait qui peut stocker des valeurs uniques, sans ordre particulier . C'est une implémentation informatique du concept mathématique d'un 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 l'appartenance à un ensemble.

Certaines structures de données d'ensembles sont conçues pour des ensembles statiques ou figés qui ne changent pas après leur construction. Les ensembles statiques n'autorisent que les opérations de requête sur leurs éléments, comme vérifier si une valeur donnée est dans l'ensemble ou énumérer les valeurs dans un ordre arbitraire. D'autres variantes, appelées ensembles dynamiques ou mutables , permettent é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 figurer plusieurs fois.

Théorie des types

En théorie des types , les ensembles sont généralement identifiés à leur fonction indicatrice ( fonction caractéristique) : ainsi, un ensemble de valeurs de type peut être noté 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 ensembles .) La fonction caractéristique d'un ensemble est définie comme : ${\style d'affichage A}$ ${\style d'affichage 2^{A}}$ ${\mathcal {P}}(A)$ ${\style d'affichage F}$ ${\style d'affichage S}$

F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases }}

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)

Opérations

Opérations théoriques de base

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 .

Ensembles statiques

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(x₁,x₂,…,x_n,): 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 retournés par l' itérateur donné .

Ensembles dynamiques

Les structures d'ensembles 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 maximum de valeurs que S peut contenir.

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

Opérations supplémentaires

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 composé 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 donné P .
fold(A₀,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 associatif et commutatif pour que cela soit bien défini.A_i+1 := F(A_i, e)
clear(S): supprime tous les éléments de S .
equal(S₁', S₂'): 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 telle que si alorsequal(S₁, S₂)hash(S₁) = hash(S₂)

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

sum(S): renvoie la somme de tous les éléments de S pour une définition de "somme". Par exemple, sur des entiers ou des réels, il peut être défini 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 premier niveau d'origine ou des é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 récursivement pour obtenir un ensemble d'éléments uniquement atomiques. Par exemple, flatten({1, {2, 3}}) == {1, 2, 3}.
nearest(S,x): renvoie l'élément de S dont la valeur est la plus proche de x (par une métrique ).
min(S), : renvoie l'élément minimum/maximum de S .max(S)

Implémentations

Les ensembles peuvent être implémentés à l'aide de diverses structures de données , qui offrent différents compromis temporels et spatiaux 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, add, et 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 telles que l'appartenance à un ensemble ou la suppression d'éléments sont O ( n ), car elles nécessitent de parcourir toute la liste. Les ensembles sont souvent implémentés à la place en utilisant des structures de données plus efficaces, en particulier diverses saveurs 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 indicateur), les ensembles sont généralement implémentés de la même manière que les cartes (partielles) ( tableaux associatifs ) - dans ce cas dans lequel la valeur de chaque paire clé-valeur a le type d'unité 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) pire cas, 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 cartes mais pas les ensembles, les ensembles peuvent être implémentés en termes de cartes. Par exemple, un idiome de programmation courant en Perl qui convertit un tableau en un hachage dont les valeurs sont la valeur sentinelle 1, à utiliser comme un ensemble, est :

my %elements = map { $_ => 1 } @elements;

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

Les opérations sur les ensembles booléens peuvent être implémentées en termes d'opérations plus élémentaires ( pop, clear, et add), mais des algorithmes spécialisés peuvent produire des limites temporelles asymptotiques plus faibles. Si les ensembles sont implémentés sous forme de listes triées, par exemple, l'algorithme naïf de prendra un temps proportionnel à la longueur m de S fois la longueur n de T ; alors qu'une variante de l' algorithme de fusion de liste fera le travail en 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)

Support linguistique

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èles, qui est généralement implémentée à l'aide d'un arbre de recherche binaire (par exemple, arbre rouge-noir ) ; La STL de SGI fournit également la hash_setclasse 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 en utilisant leur position (relative ou absolue). Les éléments d'ensemble doivent avoir un ordre faible strict.
Java offre 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).
Apple s » framework Foundation (partie du cacao ) fournit les Objective-C des classes NSSet, NSMutableSet, NSCountedSet, NSOrderedSetet NSMutableOrderedSet. Les API CoreFoundation fournissent les types CFSet et CFMutableSet à utiliser en C .
Python a built-in setet frozensettypes depuis 2,4, et depuis python 3.0 et 2.7, prend en charge les littéraux ensemble non vide en utilisant une syntaxe accolade, par exemple: {x, y, z}; les ensembles vides doivent être créés à l'aide de set(), car Python l'utilise {}pour représenter le dictionnaire vide.
Le .NET Framework fournit le générique HashSetet les SortedSetclasses qui implémentent l' ISetinterface générique .
La bibliothèque de classes de Smalltalk inclut Setet IdentitySet, en utilisant respectivement l'égalité et l'identité pour le test d'inclusion. De nombreux dialectes fournissent des variantes pour le stockage compressé ( NumberSet, CharacterSet), pour le classement ( OrderedSet, SortedSet, etc.) ou pour les références faibles ( WeakIdentitySet).
La bibliothèque standard de Ruby comprend un setmodule qui contient Setet des SortedSetclasses qui implémentent des ensembles à l'aide de tables de hachage, cette dernière permettant l'itération dans l'ordre trié.
La bibliothèque standard d' OCaml contient un Setmodule qui implémente une structure de données d'ensembles fonctionnels à l'aide d'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 set qui implémente une structure de données set basée sur des listes TCL.
La bibliothèque standard Swift contient un Settype, puisque Swift 1.2.
JavaScript a été introduit en Settant qu'objet intégré standard avec la norme ECMAScript 2015.
La bibliothèque standard d' Erlang a un setsmodule.
Clojure a une syntaxe littérale pour les ensembles hachés et implémente également des ensembles triés.
LabVIEW a un support natif pour les ensembles, à partir de la version 2019.

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 factice comme valeurs, qui sont ignorées.

Multiset

Une généralisation de la notion d'ensemble est celle d'un multi-ensemble ou sac , qui est similaire à un ensemble mais permet des valeurs répétées ("égales") (doublons). Ceci est utilisé dans deux sens distincts : soit des valeurs égales sont considérées comme identiques et sont simplement comptées, soit des valeurs égales sont considérées comme équivalentes et sont stockées en tant qu'éléments distincts. Par exemple, étant donné une liste de personnes (par nom) et d'âges (en années), on pourrait construire un ensemble multiple d'âges, qui compte simplement le nombre de personnes d'un âge donné. Alternativement, on peut construire un multi-ensemble de personnes, où deux personnes sont considérées comme équivalentes si leurs âges sont identiques (mais peuvent être des personnes différentes et avoir des noms différents), auquel cas chaque paire (nom, âge) doit être stockée, et en sélectionnant 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 relation d'équivalence mais toujours distincts sous une autre relation. Certains types d'implémentations multi-ensembles stockeront des objets égaux distincts en tant qu'éléments séparés dans la structure de données ; tandis que d'autres le réduiront à une 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 donnent des caractéristiques de performances différentes.

L'ensemble de tous les sacs sur le type T est donné par l'expression sac T. Si par multi-ensemble on considère les éléments égaux identiques et les compte simplement, alors un multi-ensemble peut être interprété comme une fonction du domaine d'entrée aux entiers non négatifs ( naturel nombres ), généralisant l'identification d'un ensemble avec sa fonction indicatrice. Dans certains cas, un multi-ensemble 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 des multi-ensembles triés et non triés. Il 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é . Il fournit la unordered_multisetclasse pour le multi-ensemble non trié, comme une sorte de conteneurs associatifs non ordonnés , 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 fournissait la hash_multisetclasse, qui a été copiée et finalement standardisée.
Pour Java , les bibliothèques tierces fournissent des fonctionnalités multi-ensembles :
- Apache Commons Collections fournit les interfaces Baget SortedBag, avec l'implémentation de classes telles que HashBaget TreeBag.
- Google Guava fournit l' Multisetinterface, avec l'implémentation de classes telles que 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-ensembles n'est pas disponible, une solution de contournement consiste à utiliser un ensemble normal, mais à remplacer le prédicat d'égalité de ses éléments pour toujours renvoyer « pas égal » sur des objets distincts (cependant, ceux-ci ne pourront toujours pas stocker plusieurs occurrences de le même objet) ou utilisez un tableau associatif mappant les valeurs à leurs multiplicités entières (cela ne pourra pas du tout 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(B₁, B₂): vérifie si chaque élément du sac B ₁ n'apparaît pas plus souvent dans B _{1 qu'il} n'apparaît dans le sac B ₂ ; parfois désigné par 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(B₁, B₂): 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 désigné par B ₁ ⊎ B ₂ .

Multisets en SQL

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 en fait une clé candidate ).

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

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

SELECT expression1, expression2... FROM table_name...

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 table_name...)

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

Languages

In other projects