Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets e Dictionaries (conjuntos e dicionários), Hashing, Space and Time…
Sets e Dictionaries (conjuntos e dicionários)
Hashing
é baseado na ideia de distribuir chaves em uma array unidimensional H[0..m − 1] chamada de
hash table
. A distribuição é feita computando, para cada chave, o valor de uma função predeterminada h chamada de
hash function
. A função designa um inteiro entre 0 e m-1, chamado de
hash address
para uma chave
"In general, a hash function needs to satisfy somewhat conflicting requirements:"
:red_flag:
:star: se o tamanho da
hash table
(m) for menor que o de número de chaves (n), acontecerão colisões (duas chaves ou mais sendo colocadas na mesma célula da
hash table
). Apesar de que colisões devem ser esperadas mesmo (m) for bem maior que (n). Todo esquema de hashing deve ter um mecanismo de resolução de colisões :star:
Open Hashing (Separate Chaining)
Closed Hashing (Open Addressing)
Space and Time Trade-Offs
input enhancement
prestructuring
dynamic programming
os dois recursos, tempo e espaço, não precisam competir por eficiência, eles podem se alinhar e trazer uma solução algorítmica para um problema que minimiza tanto o running time quanto o espaço usado
nã se pode falar de space-time trade-offs sem mencionar a área de compreensão de dados
sets
(conjuntos)
o que é:
maneiras comuns de implementar:
na computação, as operações que se realizam num set são normalmente, procurar por um item, apagar um item ou adicionar um item novo.
Dicionários
a estrutura de dados que realiza essas 3 operações é chamada de
dicionário
implementação:
são uma coleção não ordenada de elementos distintos (pode estar vazio),
é definido por uma listagem explicita de seus elementos ou por uma propriedade especifica que todos os elementos do set e apenas eles tenham
suas operações mais importantes são checar se um item dado é parte de um set, encontrar a união de dois sets e encontrar a intercessão
1: consideram apenas sets que fazem parte de um set U maior chamado de set universal. Qualquer subset de U pode ser representado por uma
bit string
de tamanho n chamada de
bit vector
se U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, então S = {2, 3, 5, 7} é representado por 011010100
essa maneira de implementar o set torna realizar suas operações básicas muito rápido, mas ao custo de potencialmente usar muito armazenamento
2: mais comum, usa-se a estrutura de lista para indicar os elementos
diferente de listas, sets não podem ter elementos repetidos. Eles também são uma coleção não ordenada, então mudar a posição de um elemento não muda o set
uma implementação eficiente deve manter um compromisso entre a operação de busca e as outras duas
pode ser implementado de diversas maneiras, desde o uso não sofisticado de arrays (ordenadas ou não), até usos como
hashing e balanced search tree
A number of applications in computing require a dynamic partition of some n-element set into a collection of disjoint subsets. After being initialized as a collection of n one-element subsets, the collection is subjected to a sequence of intermixed union and search operations. This problem is called the
set union problem
:red_flag:
em termos mais gerais é a ideia de pré-processar os inputs do problema (como um todo ou só em partes), e guardar a informação adquirida para acelerar a resolução do problema depois
utiliza espaço extra, para dá um acesso mais rápido e/ou flexivel
parte do processamento é feito antes do problema ser resolvido, mas diferente do método input-enhancement, ele lida com estrutura de acesso
Ex:
counting methods for sorting
Boyer-Moore algorithm for string matching and its simplified version suggested by Horspool
Ex:
hashing
indexing with B-trees
grava soluções para subproblemas sobrepostos de um dado problema, daí a solução do problema é obtida
"Such a situation arises, in particular, when an algorithm uses a spaceefficient data structure to represent a problem’s input, which leads, in turn, to a
faster algorithm."
:red_flag:
"Note, however, that in data compression, size reduction is the goal rather than a technique for solving another problem."
:red_flag:
A hash table’s size should not be excessively large compared to the number of keys, but it should be sufficient to not jeopardize the implementation’s time efficiency.
A hash function needs to distribute keys among the cells of the hash table as evenly as possible. (This requirement makes it desirable, for most applications, to have a hash function dependent on all bits of a key, not just some of them.)
A hash function has to be easy to compute.
In open hashing, keys are stored in linked lists attached to cells of a hash table.
Each list contains all the keys hashed to its cell
In closed hashing, all keys are stored in the hash table itself without the use of linked lists. (Of course, this implies that the table size m must be at least as large as the number of keys n.) Different strategies can be employed for collision resolution. The simplest one—called linear probing—checks the cell following the one where the collision occurs. If that cell is empty, the new key is installed there; if the next cell is already occupied, the availability of that cell’s immediate successor is checked, and so on. Note that if the end of the hash table is reached, the search is wrapped to the beginning of the table; i.e., it is treated as a circular array.