stringtranslate.com

Conjunto (tipo de datos abstracto)

En informática , un conjunto es un tipo de datos abstracto que puede almacenar valores únicos, sin ningún orden particular . Es una implementación informática del concepto matemático de un 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 la pertenencia de un valor 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 sobre sus elementos, como verificar si un valor dado está en el conjunto o enumerar los valores en un orden arbitrario. Otras variantes, llamadas conjuntos dinámicos o mutables , también permiten la inserción y eliminación de elementos del conjunto.

Un multiconjunto es un tipo especial de conjunto en el que un elemento puede aparecer varias veces en el conjunto.

Teoría de tipos

En la teoría de tipos , los conjuntos se identifican generalmente con su función indicadora (función característica): en consecuencia, un conjunto de valores de tipo puede denotarse por o . (Los subtipos y subconjuntos pueden modelarse por tipos de refinamiento , y los conjuntos cocientes pueden reemplazarse por setoides ). La función característica de un conjunto se define como:

En teoría, muchas otras estructuras de datos abstractas pueden considerarse como estructuras de conjunto con operaciones adicionales y/o axiomas adicionales impuestos a las operaciones estándar. Por ejemplo, un montón abstracto puede considerarse como una estructura de conjunto con una operación que devuelve el elemento de menor valor.min(S)

Operaciones

Operaciones básicas de la teoría de conjuntos

Se pueden definir las operaciones del álgebra de conjuntos :

Conjuntos estáticos

Las operaciones típicas que puede proporcionar una estructura de conjunto estática S son:

Conjuntos dinámicos

Las estructuras de conjuntos dinámicos generalmente agregan:

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:

Se pueden definir otras operaciones para conjuntos con elementos de un tipo especial:

Implementaciones

Los conjuntos se pueden implementar utilizando varias estructuras de datos , que proporcionan diferentes compensaciones de tiempo y espacio para varias operaciones. Algunas implementaciones están diseñadas para mejorar la eficiencia de operaciones muy especializadas, como nearesto union. Las implementaciones descritas como de "uso general" normalmente intentan optimizar las operaciones element_of, addy delete. Una implementación simple es utilizar 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 la lista completa. [b] Los conjuntos a menudo se implementan utilizando estructuras de datos más eficientes, en particular varios tipos de árboles , intentos o tablas hash .

Como los conjuntos pueden interpretarse 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 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). Una tabla hash lineal ordenada [8] puede usarse para proporcionar conjuntos ordenados determinísticamente.

Además, en lenguajes que admiten mapas pero no conjuntos, los conjuntos se pueden implementar en términos de mapas. Por ejemplo, un modismo de programación común en Perl que convierte una matriz en un hash cuyos valores son el valor centinela 1, para su uso como conjunto, es:

mis %elementos = mapa { $_ => 1 } @elementos ;         

Otros métodos populares incluyen matrices . En particular, un subconjunto de los números enteros 1.. n se puede implementar de manera eficiente como una matriz de n bits , que también admite operaciones de unión e intersección muy eficientes. Un mapa de Bloom implementa un conjunto de manera probabilística, utilizando una representación muy compacta pero con un pequeño riesgo de falsos positivos en las consultas.

Las operaciones de conjuntos booleanos se pueden implementar en términos de operaciones más elementales ( pop, clear, y add), pero los algoritmos especializados pueden producir límites de tiempo asintóticos más bajos. Si los conjuntos se implementan como listas ordenadas, por ejemplo, el algoritmo ingenuo para tomará un tiempo proporcional a la longitud m de S 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 especializadas (como la estructura de datos de unión-búsqueda ) que están optimizadas para una o más de estas operaciones, a expensas de otras.union(S,T)

Soporte de idiomas

Uno de los primeros lenguajes que admitió conjuntos fue Pascal ; ahora muchos lenguajes lo incluyen, ya sea en el lenguaje principal o en una biblioteca estándar .

Como se señaló en la sección anterior, en lenguajes que no admiten conjuntos directamente pero sí matrices asociativas , los conjuntos se pueden emular usando matrices asociativas, utilizando los elementos como claves y un valor ficticio como valores, que se ignoran.

Conjunto múltiple

Una generalización de la noción de conjunto es la de multiconjunto o bolsa , que es similar a un conjunto pero permite valores repetidos ("iguales") (duplicados). Esto se utiliza en dos sentidos distintos: o bien los valores iguales se consideran idénticos y simplemente se cuentan, o bien 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 multiconjunto de edades, que simplemente cuenta el número de personas de una edad dada. Alternativamente, se puede construir un multiconjunto 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 cada par (nombre, edad) debe almacenarse, y la selección de una edad dada da todas las personas de una edad dada.

Formalmente, es posible que los objetos en informática se consideren "iguales" bajo alguna relación de equivalencia , pero que sean distintos bajo otra relación. Algunos tipos de implementaciones de conjuntos múltiples almacenarán objetos iguales distintos como elementos separados en la estructura de datos, mientras que otros los reducirán a una sola versión (la primera que se encuentre) y mantendrán un recuento entero positivo de la multiplicidad del elemento.

Al igual que con los conjuntos, los multiconjuntos se pueden implementar naturalmente utilizando tablas hash o árboles, 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 multiconjunto se consideran idénticos los elementos iguales y simplemente se cuentan, entonces un multiconjunto puede interpretarse como una función del dominio de entrada a los enteros no negativos ( números naturales ), generalizando la identificación de un conjunto con su función indicadora. En algunos casos un multiconjunto en este sentido de conteo puede generalizarse para permitir valores negativos, como en Python.

Cuando no está disponible una estructura de datos de múltiples conjuntos, una solución alternativa es utilizar un conjunto regular, pero anular el predicado de igualdad de sus elementos para que siempre devuelva "no igual" en objetos distintos (sin embargo, esto aún no podrá almacenar múltiples ocurrencias del mismo objeto) o utilizar una matriz asociativa que asigne los valores a sus multiplicidades enteras (esto no podrá distinguir entre elementos iguales en absoluto).

Operaciones típicas en bolsas:

Conjuntos múltiples en SQL

En las bases de datos relacionales , una tabla puede ser un conjunto (matemático) o un multiconjunto, 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 DISTINCTse use la palabra clave para forzar que las filas sean todas diferentes, o la selección incluya la clave principal (o una clave candidata).

En ANSI SQL, la MULTISETpalabra clave se puede utilizar para transformar una subconsulta en una expresión de colección:

SELECCIONAR expresión1 , expresión2 ... DE 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 puede usarse en otra consulta o en la asignación a una columna del tipo de colección apropiado.

Véase también

Notas

  1. ^ Por ejemplo, en Python pickse puede implementar en una clase derivada de la función incorporada setlo siguiente:
    clase  Set ( conjunto ):  def  pick ( self ):  return  next ( iter ( self ))
  2. ^ La inserción de elementos se puede realizar en O (1) tiempo simplemente insertándolos en un final, pero si se evitan los duplicados esto toma O ( n ) tiempo.

Referencias

  1. ^ Python: pop()
  2. ^ 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 v. Luck, Heinz Marburger, pág. 76
  3. ^ Problema de Python 7212: recuperar un elemento arbitrario de un conjunto sin eliminarlo; consulte el mensaje 106593 sobre el nombre estándar
  4. ^ Característica Ruby n.° 4553: agregar Set#pick y Set#pop
  5. ^ Síntesis inductiva de programas funcionales: planificación universal, plegado de programas finitos y abstracción de esquemas mediante razonamiento analógico, Ute Schmid , Springer, 21 de agosto de 2003, pág. 240
  6. ^ Tendencias recientes en la especificación de tipos de datos: 10.º taller sobre especificación de tipos de datos abstractos, organizado conjuntamente con el 5.º taller 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
  7. ^ Rubí: aplanar()
  8. ^ Wang, Thomas (1997), Tabla hash lineal ordenada, archivada desde el original el 12 de enero de 2006
  9. ^ Stephen Adams, "Conjuntos eficientes: un acto de equilibrio", Journal of Functional Programming 3(4):553-562, octubre de 1993. Recuperado el 11 de marzo de 2015.
  10. ^ "Especificación del lenguaje ECMAScript 2015 – ECMA-262 6.ª edición". www.ecma-international.org . Consultado el 11 de julio de 2017 .