Please enable JavaScript.
Coggle requires JavaScript to display documents.
Conjuntos(Sets) e Dicionários - Coggle Diagram
Conjuntos(Sets) e Dicionários
Um conjunto(set) pode ser descrito como uma coleção desordenada (possivelmente vazia) de itens chamados elementos.
As operações mais importantes de um conjunto são:
checar se o elemento está no conjunto dado.
encontrar a união de 2 conjuntos, que seriam todos os elementos pertencentes a ambos os conjuntos.
encontrar a intersecção de 2 conjuntos, que seriam os elementos em comum dos 2 conjuntos.
Conjuntos podem ser implementados em aplicações computacionais de 2 jeitos:
1.
Conjuntos que são subconjuntos de um
conjunto universal
U
.
Tem um
vetor de bits
que indica quando um elemento do conjunto
U
está ou não em um dado subconjunto.
2.
Uma estrutura de lista que indica os elementos dos conjuntos.
Só funciona para conjuntos finitos.
Diferenças de Conjuntos para Listas
Não pode conter elementos iguais.
Pode ser contornado com a introdução de
multiset
e
bags (bolsas)
.
Por ser uma coleção desordenada de elementos, mesmo se trocadas as posições dos elementos o conjunto continua o mesmo.
Dicionário: um conjunto em que os elementos podem ser adicionados, removidos e procurados.
Pode ser implementado de diferentes formas, vai de um uso não sofisticado de arrays à tecnicas sofisticadas como hashing e árvores de busca balanceada.
Balanço(Trade-off) de espaço e tempo
Aprimoramento de entrada:
Funciona como um pré-processamento, inteiro ou em partes, de uma entrada do problema, e o armazenamento de informações adicionais obtidas para acelerar sua solução.
Algoritmos baseados neste aprimoramento:
métodos de contagem para ordenação;
algoritmo de Boyer-Moore para combinar Strings.
Pré-estruturação:
Usa espaço extra para facilitar o acesso mais rápido e/ou flexível aos dados.
Parte do processamento é realizado antes do problema ser resolvido e lida com estrutura de acesso.
Algoritmos baseados:
hashing;
indexação com B-trees.
Programação dinâmica:
Baseada em guardar soluções para subproblemas sobrepostos de um dado problema em uma mesa na qual a solução do problema é então obtido.
Hashing
Implementação de dicionário usando registros como elementos.
Esses registros possuem vários campos, cada um responsável por um tipo particular de informação sobre a entidade que o registro representa.
Um desses campos é a
chave
que é usada para identificar essa "entidade" representada pelo registro.
Hashing
é baseada na ideia de distribuir chaves em um array unidimensional H[0...m-1] chamado
hash table
.
A distribuição é feita computando, para cada chave, o valor de uma função predefinida chamada
hash function
.
Essa função atribui à uma chave um valor inteiro entre 0 e m-1, chamado
hash address
.
Em geral, a função hashing precisa satisfazer alguns requisitos conflitantes:
O tamanho da hash table não deve ser muito grande comparado ao número de chaves, mas deve ser o suficiente para não colocar em perigo a implementação da eficiência temporal.
Uma hash function precisa distribuir as chaves entre as células da hash table o mais uniformemente possível.
Uma hashing function precisa ser computada facilmente.
Se o tamanho da hash table
m
for menor que a qtde. de chaves
n
, acontece o que é chamado de
colisão
.
Colisão
é um fenômeno que acontece quando duas (ou mais) chaves são armazenadas na mesma célula na hash table.
Todo esquema de hashing deve ter um mecanismo de resolução em caso de colisão.
O mecanismo é diferente nas 2 principais versões de hashing:
open hashing (aberta)
e
closed hashing (fechada)
.
Open hashing (Separate Chaining)
As chaves são armazenadas em listas encadeadas anexadas às células da hash table.
No geral, a eficiência da operação de procura depende do tamanho da lista encadeada que, por sua vez, depende do tamanho do dicionário e da table, e da qualidade da hash function.
Se a hash function distribui
n
chaves entre
m
células da hash table uniformemente, cada lista vai ter tamanho
n/m
.
A razão α=
n/m
, chamada
load factor
da hash table, tem um papel importante na eficiência do algoritmo.
Normalmente é necessário que o load factor não seja muito distante de 1.
O valor ser muito pequeno implica em muitas listas vazias e um uso de espaço ineficiente.
O valor ser muito grande implica em listas encadeadas maiores e operações de procura mais longas temporalmente.
Porém, o valor ser próximo de 1 implica em uma grande eficiência na procura de uma dada chave.
As operações de inserção e remoção são quase idênticas às operações de procura, e todas elas são Θ(1) no caso normal se a qtde. de chaves
n
é próxima ao tamanho
m
da hash table.
Closed hashing (Open Addressing)
As chaves são armazenadas na própria hash table.
Podem ser implementadas diferentes resoluções para problemas de colisão.
A mais simples chamada
linear probing
, checa se a célula seguinte à célula em que a colisão ocorreu está vazia, se sim, a nova chave é instalada lá, se não, é checada a disponibilidade da célula seguinte e assim por diante.
Para nesses casos, usando a operação de procura, a função h(K) é computada, se a célula h(K) estiver vazia a procura é mal sucedida, mas se não estiver vazia K é comparado com o ocupante da célula.
Se K e o ocupante forem iguais, temos uma procura bem sucedida, se não, K é comparado com a chave da próxima célula até ser encontrado ou uma chave correspondente ou uma célula vazia.
Embora as operações de procura e inserção sejam simples, por causa disso, a de remoção não é.
É usada então uma "remoção preguiçosa", em que as células previamente ocupadas são marcadas com um símbolo, usado para distingui-las entre as células não previamente ocupadas.
Quando a hash table fica próxima de estar cheia, a performance da linear probing deteriora por causa de um fenômeno chamado
clustering
.
Um
cluster
em linear probing é uma sequência contínua de células ocupadas. Ele faz com que as operações em um dicionário sejam menos eficientes.
Outras estratégias de resolução de coalisão são sugeridas para diminuir este problema, uma delas é a chamada
double hashing
, que usa outra hash function s(K).
Algumas análises sugerem que double hashing seja superior a linear probing, porém ela também se deteriora quando a table chega a ficar próxima de estar cheia.
Uma solução ideal nesse caso seria usar
rehashing
: a table é escaneada e todas as chaves são relocadas para uma table maior.
Em hashing as operações de procura, inserção e remoção levam Θ(1) tempo em casos normais e Θ(n) nos piores casos.
Com algumas modificações o hashing pode ser usado para guardar grandes dicionários em discos, uma variação que é chamada de
extendible hashing
.