Definir (tipo de dados abstratos) - Set (abstract data type)

Na ciência da computação , um conjunto é um tipo de dado abstrato que pode armazenar valores únicos, sem qualquer ordem particular . É uma implementação computacional do conceito matemático de um conjunto finito . Ao contrário da maioria dos outros tipos de coleção , em vez de recuperar um elemento específico de um conjunto, normalmente se testa um valor para associação em um conjunto.

Algumas estruturas de conjunto de dados são projetadas para conjuntos estáticos ou congelados que não mudam depois de construídos. Os conjuntos estáticos permitem apenas operações de consulta em seus elementos - como verificar se um determinado valor está no conjunto ou enumerar os valores em alguma ordem arbitrária. Outras variantes, denominadas conjuntos dinâmicos ou mutáveis , permitem também a inserção e exclusão de elementos do conjunto.

Um multiset é um tipo especial de conjunto no qual um elemento pode figurar várias vezes.

Teoria de tipo

Na teoria dos tipos , os conjuntos são geralmente identificados com sua função indicadora ( função característica): consequentemente, um conjunto de valores de tipo pode ser denotado por ou . (Subtipos e subconjuntos podem ser modelados por tipos de refinamento , e conjuntos de quocientes podem ser substituídos por setoides .) A função característica de um conjunto é definida como: ${\ displaystyle A}$ ${\ displaystyle 2 ^ {A}}$ ${\ displaystyle {\ mathcal {P}} (A)}$ ${\ displaystyle F}$ ${\ displaystyle S}$

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

Em teoria, muitas outras estruturas de dados abstratas podem ser vistas como estruturas de conjuntos com operações adicionais e / ou axiomas adicionais impostos às operações padrão. Por exemplo, um heap abstrato pode ser visto como uma estrutura definida com uma operação que retorna o elemento de menor valor. min(S)

Operações

Operações teóricas do conjunto central

Pode-se definir as operações da álgebra de conjuntos :

union(S,T): Retorna a união de conjuntos S e T .
intersection(S,T): Retorna a intersecção de conjuntos S e T .
difference(S,T): Retorna a diferença de conjuntos S e T .
subset(S,T): Um predicado que testa se o conjunto S é um subconjunto do conjunto T .

Conjuntos estáticos

As operações típicas que podem ser fornecidas por uma estrutura de conjunto estático S são:

is_element_of(x,S): Verifica se o valor x está no conjunto S .
is_empty(S): verifica se o conjunto S está vazio.
size(S)ou : devolve o número de elementos em S .cardinality(S)
iterate(S): retorna uma função que retorna mais um valor de S em cada chamada, em alguma ordem arbitrária.
enumerate(S): retorna uma lista contendo os elementos de S em alguma ordem arbitrária.
build(x₁,x₂,…,x_n,): cria uma estrutura de conjunto com valores x ₁ , x ₂ , ..., x _n .
create_from(collection): cria uma nova estrutura de conjunto contendo todos os elementos de uma determinada coleção ou todos os elementos retornados por um determinado iterador .

Conjuntos dinâmicos

Estruturas de conjuntos dinâmicos normalmente adicionam:

create(): cria uma nova estrutura de conjunto inicialmente vazia.
- create_with_capacity(n): cria uma nova estrutura de conjunto, inicialmente vazia, mas capaz de conter até n elementos.
add(S,x): adiciona o elemento x a S , se ainda não estiver presente.
remove(S, x): remove o elemento x de S , se estiver presente.
capacity(S): retorna o número máximo de valores que S pode conter.

Algumas estruturas definidas podem permitir apenas algumas dessas operações. O custo de cada operação dependerá da implementação e, possivelmente, também dos valores particulares armazenados no conjunto e da ordem em que são inseridos.

Operações adicionais

Existem muitas outras operações que podem (em princípio) ser definidas nos termos acima, tais como:

pop(S): Retorna um elemento arbitrário de S , eliminando-o a partir de S .
pick(S): Retorna um elemento arbitrário de S . Funcionalmente, o modificador poppode ser interpretado como o par de seletores (pick, rest),onde restretorna o conjunto que consiste em todos os elementos, exceto para o elemento arbitrário. Pode ser interpretado em termos de iterate.
map(F,S): Devolve o conjunto de valores distintos resultantes de aplicar a função F a cada elemento de S .
filter(P,S): Retorna o subconjunto que contém todos os elementos de S que satisfazem um dado predicado P .
fold(A₀,F,S): retorna o valor A _{| S |}depois de aplicar para cada elemento e de S, para alguma operação binária F. F deve ser associativo e comutativo para que seja bem definido.A_i+1 := F(A_i, e)
clear(S): Eliminar todos os elementos de S .
equal(S₁', S₂'): verifica se os dois conjuntos fornecidos são iguais (ou seja, contêm todos e apenas os mesmos elementos).
hash(S): retorna um valor hash para o conjunto estático S de forma que se entãoequal(S₁, S₂)hash(S₁) = hash(S₂)

Outras operações podem ser definidas para conjuntos com elementos de um tipo especial:

sum(S): retorna a soma de todos os elementos de S para alguma definição de "soma". Por exemplo, em números inteiros ou reais, pode ser definido como .fold(0, add, S)
collapse(S): dado um conjunto de conjuntos, retorna a união. Por exemplo collapse({{1}, {2, 3}}) == {1, 2, 3},. Pode ser considerado uma espécie de sum.
flatten(S): dado um conjunto que consiste em conjuntos e elementos atômicos (elementos que não são conjuntos), retorna um conjunto cujos elementos são os elementos atômicos do conjunto de nível superior original ou elementos dos conjuntos que ele contém. Em outras palavras, remova um nível de aninhamento - como, collapse,mas permite átomos. Isso pode ser feito uma única vez ou nivelando recursivamente para obter um conjunto de apenas elementos atômicos. Por exemplo flatten({1, {2, 3}}) == {1, 2, 3},.
nearest(S,x): retorna o elemento de S que é o mais próximo em valor de x (por alguma métrica ).
min(S), : Retorna o elemento mínimo / máximo de S .max(S)

Implementações

Os conjuntos podem ser implementados usando várias estruturas de dados , que fornecem diferentes compensações de tempo e espaço para várias operações. Algumas implementações são projetadas para melhorar a eficiência de operações muito especializadas, como nearestou union. Implementações descritos como "uso geral" tipicamente esforços para optimizar as element_of, adde deleteoperações. Uma implementação simples é usar uma lista , ignorando a ordem dos elementos e tomando cuidado para evitar valores repetidos. Isso é simples, mas ineficiente, já que operações como associação de conjunto ou exclusão de elemento são O ( n ), pois exigem a varredura de toda a lista. Os conjuntos são frequentemente implementados usando estruturas de dados mais eficientes, particularmente vários tipos de árvores , tentativas ou tabelas de hash .

Como os conjuntos podem ser interpretados como um tipo de mapa (pela função do indicador), os conjuntos são comumente implementados da mesma maneira que os mapas (parciais) ( matrizes associativas ) - neste caso, em que o valor de cada par de valor-chave tem o tipo de unidade ou um valor sentinela (como 1) - ou seja, uma árvore de busca binária de auto-equilíbrio para conjuntos classificados (que tem O (log n) para a maioria das operações), ou uma tabela hash para conjuntos não classificados (que tem O (1) caso médio, mas O (n) pior caso, para a maioria das operações). Uma tabela hash linear classificada pode ser usada para fornecer conjuntos ordenados deterministicamente.

Além disso, em linguagens que suportam mapas, mas não conjuntos, os conjuntos podem ser implementados em termos de mapas. Por exemplo, um idioma de programação comum em Perl que converte uma matriz em um hash cujos valores são o valor sentinela 1, para uso como um conjunto, é:

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

Outros métodos populares incluem matrizes . Em particular, um subconjunto de inteiros 1 .. n pode ser implementado de forma eficiente como uma matriz de bits de n , que também suporta operações de união e interseção muito eficientes. Um mapa Bloom implementa um conjunto probabilisticamente, usando uma representação muito compacta, mas arriscando uma pequena chance de falsos positivos nas consultas.

As operações de conjunto booleana pode ser implementado em termos de operações mais elementares ( pop, clear, e add), mas especializada algoritmos podem produzir limites de tempo inferior assintótica. Se os conjuntos são implementados como listas ordenadas, por exemplo, o algoritmo ingênuo para levará um tempo proporcional ao comprimento m de S vezes o comprimento n de T ; enquanto uma variante do algoritmo de mesclagem de lista fará o trabalho em tempo proporcional am + n . Além disso, existem estruturas de dados de conjunto especializadas (como a estrutura de dados union-find ) que são otimizadas para uma ou mais dessas operações, às custas de outras. union(S,T)

Suporte de linguas

Uma das primeiras linguagens a oferecer suporte a conjuntos foi Pascal ; muitas linguagens agora o incluem, seja na linguagem central ou em uma biblioteca padrão .

Em C ++ , a Standard Template Library (STL) fornece a setclasse de modelo, que é tipicamente implementada usando uma árvore de pesquisa binária (por exemplo, árvore vermelha-preta ); O STL da SGI também fornece a hash_setclasse de modelo, que implementa um conjunto usando uma tabela hash. C ++ 11 tem suporte para a unordered_setclasse de modelo, que é implementada usando uma tabela hash. Em conjuntos, os próprios elementos são as chaves, em contraste com os recipientes sequenciados, onde os elementos são acessados usando sua posição (relativa ou absoluta). Os elementos do conjunto devem ter uma ordem estritamente fraca.
Java oferece a Set interface para oferecer suporte a conjuntos (com a HashSetclasse implementando-a usando uma tabela hash) e a SortedSetsubinterface para oferecer suporte a conjuntos classificados (com a TreeSetclasse implementando-a usando uma árvore de pesquisa binária).
A Apple 's quadro Foundation (parte do Cacau ) fornece os Objective-C aulas NSSet, NSMutableSet, NSCountedSet, NSOrderedSet, e NSMutableOrderedSet. Os CoreFoundation APIs fornecem os CFSET e CFMutableSet tipos para uso em C .
Python tem tipos setefrozenset embutidos desde 2.4, e desde Python 3.0 e 2.7, oferece suporte a conjuntos de literais não vazios usando uma sintaxe de colchetes, por exemplo {x, y, z}:; conjuntos vazios devem ser criados usando set(), porque Python usa {}para representar o dicionário vazio.
O .NET Framework fornece o genérico HashSete as SortedSetclasses que implementam a ISetinterface genérica .
A biblioteca de classes de Smalltalk inclui Sete IdentitySet, usando igualdade e identidade para teste de inclusão, respectivamente. Muitos dialetos fornecer variações para armazenamento comprimido ( NumberSet, CharacterSet), por encomenda ( OrderedSet, SortedSet, etc.) ou para referências fracas ( WeakIdentitySet).
A biblioteca padrão do Ruby inclui um setmódulo que contém Sete SortedSetclasses que implementam conjuntos usando tabelas hash, a última permitindo a iteração em ordem classificada.
A biblioteca padrão do OCaml contém um Setmódulo, que implementa uma estrutura de dados de conjunto funcional usando árvores de pesquisa binárias.
A implementação do GHC de Haskell fornece um Data.Setmódulo que implementa conjuntos imutáveis usando árvores de pesquisa binárias.
O pacote Tcl Tcllib fornece um módulo de conjunto que implementa uma estrutura de conjunto de dados baseada em listas TCL.
A biblioteca padrão do Swift contém um Settipo, desde o Swift 1.2.
JavaScript introduzido Setcomo um objeto interno padrão com o padrão ECMAScript 2015.
A biblioteca padrão de Erlang possui um setsmódulo.
Clojure tem sintaxe literal para conjuntos em hash e também implementa conjuntos classificados.
O LabVIEW possui suporte nativo para conjuntos, a partir da versão 2019.

Conforme observado na seção anterior, em linguagens que não suportam diretamente conjuntos, mas suportam matrizes associativas , os conjuntos podem ser emulados usando matrizes associativas, usando os elementos como chaves e usando um valor fictício como os valores, que são ignorados.

Multiset

Uma generalização da noção de conjunto é a de multiset ou bolsa , que é semelhante a um conjunto, mas permite valores repetidos ("iguais") (duplicados). Isso é usado em dois sentidos distintos: ou valores iguais são considerados idênticos e são simplesmente contados, ou valores iguais são considerados equivalentes e são armazenados como itens distintos. Por exemplo, dada uma lista de pessoas (por nome) e idades (em anos), pode-se construir um multiconjunto de idades, que simplesmente conta o número de pessoas de uma determinada idade. Alternativamente, pode-se construir um multiset de pessoas, onde duas pessoas são consideradas equivalentes se suas idades forem as mesmas (mas podem ser pessoas diferentes e ter nomes diferentes), caso em que cada par (nome, idade) deve ser armazenado e selecionando em uma determinada idade dá todas as pessoas de uma determinada idade.

Formalmente, é possível que objetos na ciência da computação sejam considerados "iguais" sob alguma relação de equivalência, mas ainda distintos sob outra relação. Alguns tipos de implementações multiset irão armazenar objetos iguais distintos como itens separados na estrutura de dados; enquanto outros irão reduzi-lo a uma versão (a primeira encontrada) e manter uma contagem inteira positiva da multiplicidade do elemento.

Tal como acontece com os conjuntos, os multisets podem ser implementados naturalmente usando uma tabela de hash ou árvores, que geram características de desempenho diferentes.

O conjunto de todos os sacos sobre o tipo T é dado pela expressão bag T. Se por multiset alguém considera itens iguais idênticos e simplesmente os conta, então um multiset pode ser interpretado como uma função do domínio de entrada para os inteiros não negativos ( natural números ), generalizando a identificação de um conjunto com sua função de indicador. Em alguns casos, um multiset neste sentido de contagem pode ser generalizado para permitir valores negativos, como em Python.

A Biblioteca de modelos padrão do C ++ implementa multisets classificados e não classificados. Ele fornece a multisetclasse para o multiset classificado, como um tipo de contêiner associativo , que implementa esse multiset usando uma árvore de pesquisa binária de autobalanceamento . Ele fornece a unordered_multisetclasse para o multiset não classificado, como uma espécie de contêineres associativos não ordenados , que implementa esse multiset usando uma tabela hash . O multiset não classificado é padrão a partir do C ++ 11 ; anteriormente, o STL da SGI fornecia a hash_multisetclasse, que era copiada e posteriormente padronizada.
Para Java , as bibliotecas de terceiros fornecem funcionalidade multiset:
- O Apache Commons Collections fornece as interfaces Bage SortedBag, com classes de implementação como HashBage TreeBag.
- O Google Guava fornece a Multisetinterface, com a implementação de classes como HashMultisete TreeMultiset.
A Apple fornece a NSCountedSetclasse como parte do Cocoa e os tipos CFBage CFMutableBagcomo parte do CoreFoundation .
A biblioteca padrão do Python inclui collections.Counter, que é semelhante a um multiset.
Smalltalk inclui a Bagclasse, que pode ser instanciada para usar identidade ou igualdade como predicado para teste de inclusão.

Onde uma estrutura de dados multiset não está disponível, uma solução alternativa é usar um conjunto regular, mas substituir o predicado de igualdade de seus itens para sempre retornar "diferente" em objetos distintos (no entanto, tal ainda não será capaz de armazenar várias ocorrências de o mesmo objeto) ou use uma matriz associativa mapeando os valores para suas multiplicidades inteiras (isso não será capaz de distinguir entre elementos iguais).

Operações típicas em bolsas:

contains(B, x): verifica se o elemento x está presente (pelo menos uma vez) no saco B
is_sub_bag(B₁, B₂): verifica se cada elemento no saco B ₁ ocorre em B _{1 com} a mesma frequência que ocorre no saco B ₂ ; às vezes denotado como B ₁ ⊑ B ₂ .
count(B, x): retorna o número de vezes que o elemento x ocorre na bolsa B ; às vezes denotado como B # x .
scaled_by(B, n): dado um número natural n , retorna uma bolsa que contém os mesmos elementos que a bolsa B , exceto que cada elemento que ocorre m vezes em B ocorre n * m vezes na bolsa resultante; por vezes designado como n ⊗ B .
union(B₁, B₂): retorna uma bolsa contendo apenas aqueles valores que ocorrem na bolsa B ₁ ou na bolsa B ₂ , exceto que o número de vezes que um valor x ocorre na bolsa resultante é igual a ( B ₁ # x) + ( B ₂ # x); às vezes denotado como B ₁ ⊎ B ₂ .

Multisets em SQL

Em bancos de dados relacionais , uma tabela pode ser um conjunto (matemático) ou um multiconjunto, dependendo da presença de restrições de unicidade em algumas colunas (o que a transforma em uma chave candidata ).

SQL permite a seleção de linhas de uma tabela relacional: esta operação em geral produzirá um multiconjunto, a menos que a palavra DISTINCT- chave seja usada para forçar as linhas a serem todas diferentes, ou a seleção inclua a chave primária (ou uma candidata).

Em ANSI SQL, a MULTISETpalavra - chave pode ser usada para transformar uma subconsulta em uma expressão de coleção:

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

é uma seleção geral que pode ser usada como expressão de subconsulta de outra consulta mais geral, enquanto

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

transforma a subconsulta em uma expressão de coleção que pode ser usada em outra consulta ou na atribuição a uma coluna do tipo de coleção apropriado.

Languages

In other projects