Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM11 - Coggle Diagram
MM11
Space and Time Trade-Offs
Encontrar equilíbrio adequado entre:
consumo de memória
tempo de execução
Trade-off Espaço x Tempo
Mais espaço -> menos tempo
Tabelas hash.
Tabelas de consulta (lookup tables).
Caches.
Estruturas auxiliares.
Menos espaço -> mais tempo
Busca sequencial.
Recomputação de resultados.
Estruturas compactas.
Pre-proecssamneto
Conceito
Gastar trabalho antecipadamente.
Reduzir custo das consultas futuras.
Exemplo
Construir índices.
Ordenar previamente.
Criar tabelas auxiliares.
Caching
Armazenar resultados já calculados.
Evita recomputações, mas consome memória adicional
Lookup tables
Tabelas contendo respostas pré-calculadas.
Consultas extremamente rapidas, mas grande utilização de memória
Sets and Dictionaries
Conceito de ADT (Abstract Data Type)
Separação entre interface e implementação
O usuário da estrutura conhece apenas as operações disponíveis.
A implementação interna pode variar sem alterar a interface.
Diferentes estruturas podem implementar o mesmo ADT.
Objetivo
Organizar dados de forma eficiente.
Facilitar busca, inserção e remoção.
Ocultar detalhes internos de armazenamento.
Set (Conjunto)
Definição
Coleção de elementos distintos.
Não existe conceito de posição.
Não há elementos duplicados.
Operações fundamentais
Inserção
Adiciona um elemento ao conjunto.
Não insere se o elemento já existir.
Remoção
Elimina um elemento existente.
Busca
Verifica se determinado elemento pertence ao conjunto.
Tamanho
Retorna quantidade de elementos armazenados.
Limpeza
Remove todos os elementos.
Dictionary (Dicionário)
Definição
Estrutura baseada em pares:
chave (key)
valor (record/data)
Característica principal
A chave identifica unicamente um registro.
O acesso aos dados ocorre através da chave.
Operações fundamentais
Insert(k,e)
Insere registro e associado à chave k.
Remove(k)
Remove o registro associado à chave.
RemoveAny()
Remove algum elemento arbitrário.
Find(k)
Procura registro usando a chave.
Size()
Retorna número de registros.
Clear()
Esvazia o dicionário.
Relação entre Sets e Dictionaries
Set
Apenas chave.
Interesse está na existência do elemento.
Exemplo:
{5, 8, 12, 20}
Dictionary
Chave + informação associada.
Exemplo:
CPF -> Pessoa
Matrícula -> Aluno
Código -> Produto
Hashing
.
Objetivo
Problema
Como localizar um registro rapidamente
Solução
Transformar a chave em um endereço.
Função hash
Função que converte uma chave em índice
Caracteristicas desejaveis
Uniformidade
Distribuir elementos por toda a tabela.
Eficiência
Baixo custo computacional.
Determinismo
Mesma chave produz mesmo resultado.
Estrutura da tabela hash
Chaves
Dados de entrada.
Função Hash
Calcula posição.
Tabela
Vetor onde os registros são armazenados.
Processo de Inserção
Receber chave -> aplicar função hash -> obter indice -> armazenar registro
Processo de Busca
Receber chave -> aplicar função hash -> ir ao indice -> ver se o elementp está la
Colisão: duas chaves produzem o mesmo índice
Resolução por Chaining
Estrutura
Cada posição guarda uma lista.
Inserção
Elemento é colocado na lista correspondente.
Busca
Percorre apenas a lista daquele bucket.
Resolução por Chaining
Resolução por open addressing
Todos os elementos permanecem na própria tabela
Linear Probing
Quadratic Probing
Double Hashing
Fator de Carga (Load Factor)
lambda pequeno: poucas colisões
lambda grande: muitas colisoes
Rehashing
Quando a tabela fica muito cheia
Processo
Criar tabela maior
Recalcular hashes
Reinserir elementos