Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets and Dictionaries, Space and Time Trade-Offs - Coggle Diagram
Sets and Dictionaries
Conjuntos(sets)
Coleção não ordenada (podendo ser vazia) de itens distintos chamados elementos do conjunto.
-Conjunto específico (listagem explícita dos elementos); ex: S = {2, 3, 5, 7} -Conjunto não específico; ex: S = {n: n é um número primo menor que 10}
Operações de conjunto importantes
verificar a associação de um determinado item em um determinado conjunto
encontrar a união de dois conjuntos, que compreende todos os elementos em um ou ambos
encontrar a interseção de dois conjuntos, que compreende todos os elementos comuns nos conjuntos
Maneiras de implementação de conjuntos num programa
Considerando-se apenas conjuntos que são subconjuntos de algum conjunto grande U, chamado de conjunto universal
Se o conjunto U tem n elementos, então qualquer subconjunto S de U pode ser representado por uma cadeia de bits de tamanho n, chamado de
vetor bit
, em que o elemento
i
th é 1 se e somente se o elemento
i
th de U é incluído no conjunto S.
ex: se U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, então S = {2, 3, 5, 7} é representado pela cadeia de bits 011010100.
Esta maneira de representar conjuntos torna possível implementar as operações de conjunto padrão muito rápido, mas à custa de potencialmente usar uma grande quantidade de armazenamento.
Usando a estrutura de lista para indicar os elementos do conjunto
Repare, contudo, que os dois pontos principais de distinção entre conjuntos e listas. Primeiro, um conjunto não pode conter elementos idênticos; uma lista pode. Este requisito de exclusividade é às vezes contornado pela introdução de um Multiset, ou bolsa, uma coleção não ordenada de itens que não são necessariamente distintos.
Em segundo lugar, um conjunto é uma coleção não ordenada de itens; portanto, alterar a ordem de seus elementos não altera o conjunto. Uma lista, definida como uma coleção ordenada de itens, é exatamente o oposto.
Dicitionaries
Na computação, as operações que precisamos executar para um conjunto ou um Multiset na maioria das vezes estão procurando um determinado item, adicionando um novo item e excluindo um item da coleção. Uma estrutura de dados que implementa essas três operações é chamada de dicionário (um tipo de dados abstrato).
Consequentemente, uma implementação eficiente de um dicionário tem que encontrar um compromisso entre a eficiência da pesquisa e as eficiências das outras duas operações.
Há várias maneiras de implementar um dicionário, usando arrays a técnicas muito mais sofisticadas, como hashing e árvores de busca balanceadas
Uma série de aplicações em computação requerem uma partição dinâmica de um conjunto de n elementos em uma coleção de subconjuntos disjuntos.
Space and Time Trade-Offs
Em termos um pouco mais gerais, a ideia é pré-processar a entrada do problema, no todo ou em parte, e armazenar as informações adicionais obtidas para acelerar a solução do problema depois. Chamamos a esta abordagem melhorias de entradas
Outro tipo de técnica que explora trade-offs de espaço por tempo simplesmente usa espaço extra para facilitar um acesso mais rápido e/ ou mais flexível aos dados. Chamamos essa abordagem de pré-estruturação.
Hashing
O hash é baseado na ideia de distribuir chaves entre um array unidimensional H[0... m - 1] chamado de
tabela hash
. A distribuição é feita por computação, para cada uma das chaves, o valor de alguma função predefinida
h
chamada de
função hash
. Esta função atribui um número inteiro entre 0 e m - 1, chamado de
endereço hash
, a uma chave. Universo << m << keys
O tamanho de uma tabela hash não deve ser excessivamente grande em comparação com o número de chaves, mas deve ser suficiente para não comprometer a eficiência de tempo da implementação
Uma função hash precisa distribuir chaves entre as células da tabela hash da forma mais uniforme possível. (Este requisito torna desejável, para a maioria das aplicações, ter uma função hash dependente de todos os bits de uma chave, não apenas alguns deles)
Uma função hash deve ser fácil de calcular
Obviamente, se escolhermos o tamanho de uma tabela de hash m para ser menor que o número de chaves n, obteremos colisões, um fenômeno de duas (ou mais) chaves sendo hash na mesma célula da tabela de hash. Mas colisões devem ser esperadas mesmo que m seja consideravelmente maior que n. Na verdade, no pior dos casos, todas as chaves podem ser hash para a mesma célula da tabela hash
Felizmente, com um tamanho de tabela hash apropriadamente escolhido e uma boa função hash, essa situação acontece muito raramente. Ainda assim, todo esquema de hash deve ter um mecanismo de resolução de colisão.
Este mecanismo é diferente nas duas versões principais do hash: hash aberto (também chamado de encadeamento separado) e hash fechado (também chamado de endereçamento aberto)
Hash aberto (encadeamento separado)
No hashing aberto, as chaves são armazenadas em listas ligadas ligadas às células de uma tabela de hash. Cada lista contém todas as chaves com hash na sua célula.
Faz-se isso simplesmente aplicando a uma chave de pesquisa o mesmo procedimento que foi usado para criar a tabela.
Em geral, a eficiência da pesquisa depende do comprimento das listas vinculadas, que, por sua vez, dependem do tamanho do dicionário e da tabela, bem como da qualidade
Se a função hash distribui n chaves entre m células da tabela de hash aproximadamente uniformemente, cada lista terá cerca de n/ m chaves longas. A razão α = n/m, chamada de fator de carga da tabela de hash, desempenha um papel crucial na eficiência do hash.
Em geral, o número médio de ponteiros (elos da cadeia) inspecionados em pesquisas bem sucedidas, S, e pesquisas mal sucedidas, U, acaba sendo: S = 1 + α/2, U = α
Além das comparações, precisamos gastar tempo calculando o valor da função hash para uma chave de pesquisa, mas é uma constante de tempo de operação, independente de n e m. Note que estamos obtendo essa eficiência notável não só como resultado da engenhosidade do método, mas também à custa de espaço extra.
As duas outras operações do dicionário, inserção e exclusão, são quase idênticas à pesquisa. As inserções são normalmente feitas no final de uma lista e a exclusão é realizada pesquisando uma chave a ser excluída e, em seguida, removendo-a de sua lista. Portanto, a eficiência dessas operações é idêntica à da pesquisa, e elas são todas Θ(1) no caso médio se o número de chaves n for aproximadamente igual ao tamanho m da tabela hash.
Hash fechadohash fechado (endereçamento aberto)
No hashing fechado, todas as chaves são armazenadas na própria tabela hash sem o uso de listas ligadas. (Obviamente, isto implica que o tamanho da tabela m deve ser pelo menos tão grande como o número de chaves n.) Diferentes estratégias podem ser empregadas para resolução de colisão.
O mais simples deles, chamado de sondagem linear, verifica a célula após a que ocorre a colisão. Se essa célula estiver vazia, a nova chave é instalada lá; se a próxima célula já estiver ocupada, a disponibilidade do sucessor imediato dessa célula é verificada e assim por diante. Note que se o final da tabela de hash é alcançado, a pesquisa é embrulhada para o início da tabela; ou seja, ele é tratado como um array circular.
Embora as operações de pesquisa e inserção sejam diretas para esta versão do hash, a exclusão não é. Por exemplo, se simplesmente excluirmos a chave ARE do último estado da tabela de hash na Figura 7.6, não poderemos encontrar a chave LOGO depois. Na verdade, depois de computar h(SOON) = 11, o algoritmo iria encontrar este local vazio e relatar o resultado da pesquisa mal sucedida. Uma solução simples é usar "exclusão preguiçosa", ou seja, marcar locais previamente ocupados por um símbolo especial para distingui-los de locais que não foram ocupados.
O número médio de vezes que o algoritmo deve acessar a tabela hash com o fator de carga α em sucesso e sem sucesso pesquisas é, respectivamente: S = 1/2 (1 + 1/(1 - α)) e U = 1/2 (1 + 1/(1 - α)²)
Ainda assim, à medida que a tabela de hash se aproxima de estar cheia, o desempenho da sondagem linear se deteriora por causa de um fenômeno chamado agrupamento(clustering). Um cluster em sondagem linear é uma sequência de células ocupadas contíguamente (com um possível envolvimento)
À medida que os clusters se tornam maiores, a probabilidade de que um novo elemento seja anexado a um cluster aumenta; além disso, grandes clusters aumentam a probabilidade de que dois clusters se aglutinem após a inserção de uma nova chave, causando ainda mais agrupamento.
Uma estratégia de resolução de colisões é o hashing duplo. Neste esquema, usamos outra função hash, s(K), para determinar um incremento fixo para a sequência de sondagem a ser usada após uma colisão no local l = h(K):
1 more item...
h ← 0; for i ← 0 to s − 1 do h ← (h ∗ C + ord(ci)) mod m,
Há mais uma técnica de design de algoritmo relacionada à ideia de trade-off espaço-por-tempo: programação dinâmica. Esta estratégia é baseada no registro de soluções para sobreposição de subproblemas de um determinado problema em uma tabela a partir da qual uma solução para o problema em questão é então obtida.
Os dois recursos-tempo e espaço-não precisam competir entre si em todas as situações de design. Na verdade, eles podem se alinhar para trazer uma solução algorítmica que minimize o tempo de execução e o espaço consumido
Não se pode discutir trade-offs de espaço-tempo sem mencionar a área extremamente importante da compressão de dados. Note, no entanto, que na compressão de dados, a redução de tamanho é o objetivo e não uma técnica para resolver outro problema.