En informática , un conjunto es un tipo de datos abstracto que puede almacenar valores únicos, sin ningún orden en particular . Es una implementación informática del concepto matemático de conjunto finito . A diferencia de la mayoría de los otros tipos de colecciones , en lugar de recuperar un elemento específico de un conjunto, normalmente se prueba un valor para la pertenencia a un conjunto.
Algunas estructuras de datos de conjuntos están diseñadas para conjuntos estáticos o congelados que no cambian después de su construcción. Los conjuntos estáticos solo permiten operaciones de consulta en sus elementos, como verificar si un valor dado está en el conjunto o enumerar los valores en algún orden arbitrario. Otras variantes, llamadas conjuntos dinámicos o mutables , permiten también la inserción y eliminación de elementos del conjunto.
Un conjunto múltiple es un tipo especial de conjunto en el que un elemento puede figurar varias veces.
Teoría de tipos
En la teoría de tipos , los conjuntos se identifican generalmente con su función de indicador (función característica): en consecuencia, un conjunto de valores de tipo puede ser denotado por o . (Los subtipos y subconjuntos se pueden modelar mediante tipos de refinamiento , y los conjuntos de cocientes se pueden reemplazar por setoides ). de un conjunto Se define como:
En teoría, muchas otras estructuras de datos abstractas pueden verse como estructuras de conjuntos con operaciones adicionales y / o axiomas adicionales impuestos a las operaciones estándar. Por ejemplo, un montón abstracto puede verse como una estructura de conjunto con una operación que devuelve el elemento de menor valor.min(S)
Operaciones
Operaciones teóricas de conjuntos básicos
Se pueden definir las operaciones del álgebra de conjuntos :
union(S,T)
: Devuelve la unión de los conjuntos S y T .intersection(S,T)
: Devuelve la intersección de conjuntos S y T .difference(S,T)
: Devuelve la diferencia de conjuntos S y T .subset(S,T)
: Un predicado que las pruebas si el conjunto S es un subconjunto de un conjunto T .
Conjuntos estáticos
Las operaciones típicas que puede proporcionar una estructura de conjunto estática S son:
is_element_of(x,S)
: Comprueba si el valor x está en el conjunto S .is_empty(S)
: comprueba si el conjunto S está vacío.size(S)
o : devuelve el número de elementos en S .cardinality(S)
iterate(S)
: devuelve una función que devuelve un valor más de S en cada llamada, en algún orden arbitrario.enumerate(S)
: devuelve una lista que contiene los elementos de S en algún orden arbitrario.build(x1,x2,…,xn,)
: crea una estructura de conjunto con valores x 1 , x 2 , ..., x n .create_from(collection)
: crea una nueva estructura de conjunto que contiene todos los elementos de la colección dada o todos los elementos devueltos por el iterador dado .
Conjuntos dinámicos
Las estructuras de conjuntos dinámicos suelen agregar:
create()
: crea una nueva estructura de conjunto inicialmente vacía.create_with_capacity(n)
: crea una nueva estructura de conjunto, inicialmente vacía pero capaz de contener hasta n elementos.
add(S,x)
: Agrega el elemento x de S , si no está ya presente.remove(S, x)
: elimina el elemento x de S , si está presente.capacity(S)
: devuelve el número máximo de valores que S puede contener.
Algunas estructuras de conjuntos pueden permitir solo algunas de estas operaciones. El costo de cada operación dependerá de la implementación y posiblemente también de los valores particulares almacenados en el conjunto y del orden en que se inserten.
Operaciones adicionales
Hay muchas otras operaciones que pueden (en principio) definirse en términos de lo anterior, tales como:
pop(S)
: Devuelve un elemento arbitrario de S , eliminarlo de S . [1]pick(S)
: Devuelve un elemento arbitrario de S . [2] [3] [4] Funcionalmente, el mutadorpop
se puede interpretar como el par de selectores(pick, rest),
donderest
devuelve el conjunto que consta de todos los elementos excepto el elemento arbitrario. [5] Puede interpretarse en términos deiterate
. [a]map(F,S)
: Devuelve el conjunto de valores distintos que resultan de la aplicación de la función F a cada elemento de S .filter(P,S)
: devuelve el subconjunto que contiene todos los elementos de S que satisfacen un predicado P dado .fold(A0,F,S)
: devuelve el valor A | S | después de aplicar para cada elemento e de S, para alguna operación binaria F. F debe ser asociativa y conmutativa para que esté bien definida.Ai+1 := F(Ai, e)
clear(S)
: Eliminar todos los elementos de S .equal(S1', S2')
: comprueba si los dos conjuntos dados son iguales (es decir, contienen todos y solo los mismos elementos).hash(S)
: devuelve un valor hash para el conjunto estático S tal que si entoncesequal(S1, S2)
hash(S1) = hash(S2)
Se pueden definir otras operaciones para conjuntos con elementos de un tipo especial:
sum(S)
: devuelve la suma de todos los elementos de S para alguna definición de "suma". Por ejemplo, sobre enteros o reales, se puede definir como .fold(0, add, S)
collapse(S)
: dado un conjunto de conjuntos, devuelve la unión. [6] Por ejemplocollapse({{1}, {2, 3}}) == {1, 2, 3}
,. Puede considerarse una especie desum
.flatten(S)
: dado un conjunto que consta de conjuntos y elementos atómicos (elementos que no son conjuntos), devuelve un conjunto cuyos elementos son los elementos atómicos del conjunto de nivel superior original o elementos de los conjuntos que contiene. En otras palabras, elimine un nivel de anidación,collapse,
pero permita átomos. Esto se puede hacer una sola vez, o aplanar recursivamente para obtener un conjunto de solo elementos atómicos. [7] Por ejemploflatten({1, {2, 3}}) == {1, 2, 3}
,.nearest(S,x)
: devuelve el elemento de S que tiene el valor más cercano a x (por alguna métrica ).min(S)
, : Devuelve el elemento de mínimo / máximo de S .max(S)
Implementaciones
Los conjuntos se pueden implementar utilizando varias estructuras de datos , que proporcionan diferentes compensaciones de tiempo y espacio para diversas operaciones. Algunas implementaciones están diseñadas para mejorar la eficiencia de operaciones muy especializadas, como nearest
o union
. Las implementaciones descritas como "uso general" típicamente se esfuerzan por optimizar las element_of
, add
y delete
operaciones. Una implementación simple es usar una lista , ignorando el orden de los elementos y teniendo cuidado de evitar valores repetidos. Esto es simple pero ineficiente, ya que las operaciones como la pertenencia a un conjunto o la eliminación de elementos son O ( n ), ya que requieren escanear toda la lista. [b] En cambio, los conjuntos se implementan a menudo utilizando estructuras de datos más eficientes, particularmente varios tipos de árboles , intentos o tablas hash .
Como los conjuntos se pueden interpretar como una especie de mapa (por la función indicadora), los conjuntos se implementan comúnmente de la misma manera que los mapas (parciales) ( matrices asociativas ), en este caso en el que el valor de cada par clave-valor tiene el valor tipo de unidad o un valor centinela (como 1), es decir, un árbol de búsqueda binario autoequilibrado para conjuntos ordenados [ definición necesaria ] (que tiene O (log n) para la mayoría de las operaciones), o una tabla hash para conjuntos no ordenados (que tiene O (1) caso promedio, pero O (n) peor caso, para la mayoría de las operaciones). Se puede utilizar una tabla hash lineal ordenada [8] para proporcionar conjuntos ordenados de forma determinista.
Además, en los idiomas que admiten mapas pero no conjuntos, los conjuntos se pueden implementar en términos de mapas. Por ejemplo, un lenguaje de programación común en Perl que convierte una matriz en un hash cuyos valores son el valor centinela 1, para usar como un conjunto, es:
my % elements = map { $ _ => 1 } @elements ;
Otros métodos populares incluyen matrices . En un subconjunto particular de los números enteros 1 .. n puede ser implementado de manera eficiente como un n bits matriz de bits , que también soporta las operaciones de unión e intersección muy eficientes. Un mapa de Bloom implementa un conjunto probabilísticamente, usando una representación muy compacta pero arriesgando una pequeña posibilidad de falsos positivos en las consultas.
Las operaciones de conjuntos Boolean pueden implementarse en términos de operaciones más elementales ( pop
, clear
y add
), pero especializados algoritmos pueden producir límites de tiempo inferior asintótica. Si los conjuntos se implementan como listas ordenadas, por ejemplo, el algoritmo ingenuo para tomará un tiempo proporcional a la longitud m de S multiplicada por la longitud n de T ; mientras que una variante del algoritmo de fusión de listas hará el trabajo en un tiempo proporcional a m + n . Además, existen estructuras de datos de conjuntos especializados (como la estructura de datos de búsqueda de unión ) que están optimizadas para una o más de estas operaciones, a expensas de otras.union(S,T)
Ayuda de idioma
Uno de los primeros lenguajes que admitió conjuntos fue Pascal ; muchos idiomas lo incluyen ahora, ya sea en el idioma principal o en una biblioteca estándar .
- En C ++ , la biblioteca de plantillas estándar (STL) proporciona la
set
clase de plantilla, que normalmente se implementa mediante un árbol de búsqueda binario (por ejemplo, árbol rojo-negro ); El STL de SGI también proporciona lahash_set
clase de plantilla, que implementa un conjunto mediante una tabla hash. C ++ 11 tiene soporte para launordered_set
clase de plantilla, que se implementa mediante una tabla hash. En los conjuntos, los elementos en sí son las claves, a diferencia de los contenedores secuenciados, donde se accede a los elementos utilizando su posición (relativa o absoluta). Los elementos del conjunto deben tener un orden estrictamente débil. - Java ofrece la
Set
interfaz para admitir conjuntos (con laHashSet
clase que la implementa mediante una tabla hash) y laSortedSet
subinterfaz para admitir conjuntos ordenados (con laTreeSet
clase que la implementa mediante un árbol de búsqueda binario). - Manzana 's marco de la Fundación (parte de Cacao ) proporciona los Objective-C clases
NSSet
,NSMutableSet
,NSCountedSet
,NSOrderedSet
, yNSMutableOrderedSet
. Los CoreFoundation API proporcionan los cfset y CFMutableSet tipos para su uso en C . - Python tiene sety frozensettipos incorporados desde 2.4, y desde Python 3.0 y 2.7, admite literales de conjuntos no vacíos usando una sintaxis de corchetes, por ejemplo
{x, y, z}
:; Los conjuntos vacíos deben crearse usandoset()
, porque Python usa{}
para representar el diccionario vacío. - El .NET Framework proporciona los genéricos
HashSet
ySortedSet
las clases que implementan la genéricaISet
interfaz. - La biblioteca de clases de Smalltalk incluye
Set
yIdentitySet
, utilizando la igualdad y la identidad para la prueba de inclusión, respectivamente. Muchos dialectos proporcionan variaciones para el almacenamiento comprimido (NumberSet
,CharacterSet
), para el pedido (OrderedSet
,SortedSet
, etc.) o para referencias débiles (WeakIdentitySet
). - La biblioteca estándar de Ruby incluye un
set
módulo que contieneSet
ySortedSet
clases que implementan conjuntos usando tablas hash, esta última permitiendo la iteración en orden ordenado. - La biblioteca estándar de OCaml contiene un
Set
módulo que implementa una estructura de datos de conjunto funcional utilizando árboles de búsqueda binarios. - La implementación de GHC de Haskell proporciona un
Data.Set
módulo que implementa conjuntos inmutables mediante árboles de búsqueda binarios. [9] - El paquete Tcl Tcllib proporciona un módulo de conjunto que implementa una estructura de datos de conjunto basada en listas de TCL.
- La biblioteca estándar de Swift contiene un
Set
tipo, desde Swift 1.2. - JavaScript introducido
Set
como un objeto integrado estándar con el estándar ECMAScript 2015 [10] . - La biblioteca estándar de Erlang tiene un
sets
módulo. - Clojure tiene una sintaxis literal para conjuntos hash y también implementa conjuntos ordenados.
- LabVIEW tiene soporte nativo para conjuntos, desde la versión 2019.
Como se señaló en la sección anterior, en los lenguajes que no admiten directamente conjuntos pero sí admiten matrices asociativas , los conjuntos se pueden emular utilizando matrices asociativas, utilizando los elementos como claves y utilizando un valor ficticio como valores, que se ignoran.
Multiset
Una generalización de la noción de conjunto es la de un conjunto múltiple o bolsa , que es similar a un conjunto pero permite valores repetidos ("iguales") (duplicados). Esto se usa en dos sentidos distintos: o los valores iguales se consideran idénticos y simplemente se cuentan, o los valores iguales se consideran equivalentes y se almacenan como elementos distintos. Por ejemplo, dada una lista de personas (por nombre) y edades (en años), se podría construir un conjunto múltiple de edades, que simplemente cuenta el número de personas de una edad determinada. Alternativamente, se puede construir un conjunto múltiple de personas, donde dos personas se consideran equivalentes si sus edades son las mismas (pero pueden ser personas diferentes y tener nombres diferentes), en cuyo caso se debe almacenar cada par (nombre, edad) y seleccionar en una edad determinada da a todas las personas de una edad determinada.
Formalmente, es posible que los objetos en informática se consideren "iguales" bajo alguna relación de equivalencia pero aún distintos bajo otra relación. Algunos tipos de implementaciones de conjuntos múltiples almacenarán distintos objetos iguales como elementos separados en la estructura de datos; mientras que otros lo reducirán a una versión (la primera que se encuentre) y mantendrán un recuento de enteros positivo de la multiplicidad del elemento.
Al igual que con los conjuntos, los conjuntos múltiples se pueden implementar de forma natural utilizando tablas o árboles hash, que producen diferentes características de rendimiento.
El conjunto de todas las bolsas sobre el tipo T viene dado por la expresión bolsa T.Si por multiset uno considera idénticos elementos iguales y simplemente los cuenta, entonces un multiset puede interpretarse como una función desde el dominio de entrada a los enteros no negativos ( natural números ), generalizando la identificación de un conjunto con su función indicadora. En algunos casos, un conjunto múltiple en este sentido de conteo puede generalizarse para permitir valores negativos, como en Python.
- La biblioteca de plantillas estándar de C ++ implementa conjuntos múltiples ordenados y no ordenados. Proporciona la
multiset
clase para el multiset ordenado, como una especie de contenedor asociativo , que implementa este multiset mediante un árbol de búsqueda binario autoequilibrado . Proporciona launordered_multiset
clase para el multiset sin clasificar, como una especie de contenedores asociativos no ordenados , que implementa este multiset mediante una tabla hash . El multiset sin clasificar es estándar a partir de C ++ 11 ; anteriormente, STL de SGI proporciona lahash_multiset
clase, que fue copiada y finalmente estandarizada. - Para Java , las bibliotecas de terceros proporcionan funciones de varios conjuntos:
- Apache Commons Collections proporciona las interfaces
Bag
ySortedBag
, con clases de implementación comoHashBag
yTreeBag
. - Google Guava proporciona la
Multiset
interfaz, con clases de implementación comoHashMultiset
yTreeMultiset
.
- Apache Commons Collections proporciona las interfaces
- Apple proporciona la
NSCountedSet
clase como parte de Cocoa y los tiposCFBag
yCFMutableBag
como parte de CoreFoundation . - La biblioteca estándar de Python incluye
collections.Counter
, que es similar a un multiset. - Smalltalk incluye la
Bag
clase, de la que se puede crear una instancia para usar la identidad o la igualdad como predicado para la prueba de inclusión.
Cuando una estructura de datos de varios conjuntos no está disponible, una solución es utilizar un conjunto regular, pero anular el predicado de igualdad de sus elementos para devolver siempre "no igual" en objetos distintos (sin embargo, no podrá almacenar múltiples apariciones de el mismo objeto) o use una matriz asociativa que mapee los valores a sus multiplicidades enteras (esto no podrá distinguir entre elementos iguales en absoluto).
Operaciones típicas en bolsas:
contains(B, x)
: comprueba si el elemento x está presente (al menos una vez) en la bolsa Bis_sub_bag(B1, B2)
: comprueba si cada elemento de la bolsa B 1 aparece en B 1 no más a menudo que en la bolsa B 2 ; a veces se denota como B 1 ⊑ B 2 .count(B, x)
: devuelve el número de veces que el elemento x aparece en la bolsa B ; a veces se denota como B # x .scaled_by(B, n)
: dado un número natural n , devuelve una bolsa que contiene los mismos elementos que la bolsa B , excepto que cada elemento que aparece m veces en B aparece n * m veces en la bolsa resultante; a veces denotado como n ⊗ B .union(B1, B2)
: devuelve una bolsa que contiene solo los valores que ocurren en la bolsa B 1 o la bolsa B 2 , excepto que el número de veces que aparece un valor x en la bolsa resultante es igual a ( B 1 # x) + ( B 2 # X); a veces se denota como B 1 ⊎ B 2 .
Multijuegos en SQL
En las bases de datos relacionales , una tabla puede ser un conjunto (matemático) o un conjunto múltiple, dependiendo de la presencia de restricciones de unicidad en algunas columnas (lo que la convierte en una clave candidata).
SQL permite la selección de filas de una tabla relacional: esta operación, en general, producirá un conjunto múltiple, a menos que se use la palabra clave DISTINCT
para forzar que las filas sean todas diferentes, o que la selección incluya la clave principal (o candidata).
En ANSI SQL, la MULTISET
palabra clave se puede utilizar para transformar una subconsulta en una expresión de colección:
SELECT expresión1 , expresión2 ... FROM nombre_tabla ...
es una selección general que se puede utilizar como expresión de subconsulta de otra consulta más general, mientras que
MULTISET ( SELECT expresión1 , expresión2 ... FROM nombre_tabla ...)
transforma la subconsulta en una expresión de colección que se puede utilizar en otra consulta o en la asignación a una columna del tipo de colección apropiado.
Ver también
- Filtro de floración
- Conjunto disjunto
- Set (matemáticas)
Notas
- ^ Por ejemplo, en Python
pick
se puede implementar en una clase derivada del integrado de laset
siguiente manera:clase Set ( set ): def pick ( self ): return next ( iter ( self ))
- ^ La inserción de elementos se puede hacer en O (1) tiempo simplemente insertando al final, pero si se evita duplicar esto toma O ( n ) tiempo.
Referencias
- ^ Python: pop ()
- ^ Gestión y procesamiento de estructuras de datos complejas: tercer taller sobre sistemas de información e inteligencia artificial, Hamburgo, Alemania, 28 de febrero - 2 de marzo de 1994. Actas, ed. Kai contra la suerte, Heinz Marburger, pág. 76
- ^ Python Issue7212 : Recupere un elemento arbitrario de un conjunto sin eliminarlo; ver msg106593 sobre el nombre estándar
- ^ Característica Ruby # 4553 : Agregar Set # pick y Set # pop
- ^ Síntesis inductiva de programas funcionales: planificación universal, plegado de programas finitos y abstracción de esquemas por razonamiento analógico, Ute Schmid, Springer, 21 de agosto de 2003, p. 240
- ^ Tendencias recientes en la especificación de tipos de datos: décimo taller sobre la especificación de tipos de datos abstractos, conjunto con el quinto taller de COMPASS, S. Margherita, Italia, 30 de mayo - 3 de junio de 1994. Documentos seleccionados, volumen 10, ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, pág. 38
- ^ Ruby: aplanar ()
- ↑ Wang, Thomas (1997), Sorted Linear Hash Table , archivado desde el original el 12 de enero de 2006
- ^ Stephen Adams, " Conjuntos eficientes: un acto de equilibrio " , Journal of Functional Programming 3 (4): 553-562, octubre de 1993. Consultado el 11 de marzo de 2015.
- ^ "ECMAScript 2015 Language Specification - ECMA-262 6th Edition" . www.ecma-international.org . Consultado el 11 de julio de 2017 .