Ensemble (informatique)
En informatique, un ensemble ou set est un type abstrait qui peut stocker certaines valeurs, sans ordre particulier, et sans répétition. Il s'agit d'une mise en œuvre informatique de la notion mathématique d'ensemble fini.
Description
[modifier | modifier le code]Un ensemble stocke des valeurs, sans ordre défini, et ne contient pas de données en double (la tentative d'insertion d'une donnée déjà présente est sans effet)[1]. Contrairement à la plupart des autres types de collections[2] les ensembles sont plus utilisés pour tester l'appartenance d'une valeur à cet ensemble que pour en extraire des données.
Structure de données
[modifier | modifier le code]Certaines structures de données de type ensemble sont conçues pour être statiques (ou « gelées ») : elles ne peuvent pas être modifiées après leur conception. Ces ensembles statiques ne permettent que des opérations de requête sur leurs éléments — telles que vérifier si une valeur donnée est présente dans l'ensemble, ou énumérer les valeurs dans un ordre arbitraire. Il existe généralement sur les serveurs les supportant des opérateurs tels qu'union, intersection et différence permettant des opérations de requête rapides[1]. D'autres variantes, appelées ensembles dynamiques ou modifiables, permettent également l'insertion et la suppression d'éléments de l'ensemble.
Une structure de données de type abstrait est une collection, ou agrégat, de données. Les données peuvent être des opérateurs booléens, des nombres, des caractères ou autres structures de données. Si l'on prend en compte les fonctionnalités d'empaquetage[3] ou d'indexation[4], il existe quatre grandes structures de données :
- non empaquetée, non indexée: collection d'objets (bunch)
- empaquetée, non indexée : ensemble
- non empaquetée, indexée : chaîne (séquence)
- empaquetée, indexée : liste (array).
Dans cette structuration, les ensembles contiennent des éléments, alors que la collection d'objets consiste en ces éléments[5].
Une structure de données probabiliste implémentant ce type est le filtre de Bloom.
Notes et références
[modifier | modifier le code]- Rudi Bruchez, Les bases de données NoSQL : Comprendre et mettre en œuvre, Paris, Éditions Eyrolles, , 279 p. (ISBN 978-2-212-13560-2, lire en ligne), p. 172
- Constituent d'autres types de collections (de type conteners) les listes, les multiensembles, les arborescences et les graphes
- "Empaqueter", faire des paquets, consiste à fournir un conteneur pour une agrégation d'objets afin de les transformer en un objet unique. Dans le cas d'un appel de fonction: sans paquet, une fonction ne peut être appelée à agir sur une chaîne qu'en passant en revue chaque élément du groupe comme argument séparé, ce qui complique considérablement l'exécution de la fonction (et est tout simplement pas possible dans certains langages de programmation). En regroupant les éléments en un ensemble, la fonction peut maintenant être appelée sur un argument unique, élémentaire : l'ensemble d'objets (bunch's package en anglais).
- L'indexation est possible lorsque les éléments envisagés sont totalement ordonnés. En l'absence d'ordre, les éléments d'un multi-ensemble (par exemple) ne présentent pas de relations telles qu'inférieures/supérieures, ou précédents/ suivants un autre élément : ils ne peuvent être comparés qu'en termes absolus (identiques/différents)
- Eric C.R. Hehner [a Practical Theory of Programming http://www.cs.utoronto.ca/~hehner/aPToP/aPToP.pdf] p. 14
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Set (abstract data type) » (voir la liste des auteurs).
