sequencial, binária e tabelas hash

Prévia do material em texto

Métodos de pesquisa em listas: sequencial, binária e tabelas hash
A tabela hash é uma estrutura de dados muito eficiente, que associa chaves de pesquisa a valores. A partir de uma chave simples, é possível fazer a inserção, a busca e a atualização de dados em complexidade de tempo constante, ou seja, O(1), no caso médio.
O principal desafio está na escolha da função hash, pois se for feita de forma imprecisa, acarretará um desempenho linear, ou seja, O(K), devido a colisões em suas linhas. Dessa forma, a escolha da função hash é o ponto-chave para o desempenho da tabela hash.
1. 
A busca sequencial é uma técnica simples e intuitiva para buscar elementos em vetores ou listas.
Tendo a informação de que os dados estão ordenados de forma crescente,​​​​​​​ qual otimização você pode aplicar na busca sequencial?
D. Parar a execução e informar que o valor não existe, quando o valor atual for maior que o buscado.
O desempenho de pior caso da busca sequencial pode ser otimizado sabendo-se que o vetor está ordenado. Para tanto, continua-se a buscar um elemento enquanto o elemento atual for maior que o buscado. No momento em que ele for menor, sabe-se que o vetor é ordenado e, no futuro, não será possível encontrar outro elemento maior. O contrário não é verdade, pois, caso seja encontrado um valor menor que o buscado, ainda é possível achar valores maiores no futuro. Funções hash podem ser utilizadas apenas em tabelas hash. Ainda, descobrir a posição de um elemento sem buscar em várias posições do vetor também só é possível em tabelas hash.
2. 
A busca binária é uma técnica eficiente para buscar elementos em vetores ou listas. A única restrição desse método é que o vetor ou a lista estejam ordenados.
Das seguintes sequências de acessos em um vetor, qual é válida em uma execução de busca binária?​​​​​​​
C. 5, 2, 1.
Em cada iteração da busca binária, o elemento do meio do intervalo atual é acessado. Nesse sentido, para acessar a posição 1, é necessário que o tamanho do intervalo seja 2. Assumindo que o vetor tivesse tamanho 2, não seria possível nas alternativas (1, 2, 5) e (1, 5, 2) acessar elementos maiores que 2 após esse primeiro acesso. No caso da alternativa (5, 7, 3), o problema vai quando o elemento 5 é acessado e logo todos os menores que 5 são ignorados, mas, logo após, o número 3 é acessado. O mesmo ocorre na alternativa (5, 2, 8). Portanto, a alternativa correta é (5, 2, 1), um vetor de tamanho 10; o primeiro acesso é o 5, após a metade é o 2 e, por fim, o 1.
3. Tabelas hash são estruturas muito eficientes utilizadas por diversas linguagens de programação e serviços. Entender seu funcionamento é crucial para o desenvolvedor, o qual deverá decidir o tamanho da tabela e a função hash que otimiza o desempenho de determinada aplicação.
Considere uma tabela hash de 5 posições (de 1 a 5, aceitando repetições) e uma função hash que representa a i-ésima letra do alfabeto com o número i. Quantas colisões ocorrem após a inserção das chaves: A, B, A, C, A, E​​​​​​​?
B. 2.
Uma tabela hash de 5 posições tem índices de 1 a 5. A função hash converte um caractere para um índice de acordo com a ordem no alfabeto. Por exemplo, a letra A é 1, a letra B é 2, e assim por diante. Nesse sentido, colisões vão ocorrer apenas quando a mesma letra for inserida. Como foi inserida três vezes a letra A, e as colisões ocorrem a partir da segunda inserção, o total de colisões é 2: a segunda inserção da letra A e a terceira.
4. 
Métodos de busca são muito utilizados em milhares de sistemas e aplicações reais. O projetista e o desenvolvedor devem ter muito conhecimento sobre seu funcionamento e também sobre as vantagens e desvantagens de cada método.
Para uma aplicação que realiza muitas inserções e atualizações nos dados, qual é o método mais indicado?​​​​​​​
D. Tabela hash implementada com vetores e listas para tratar colisões.
A busca sequencial tem um custo muito alto e só é indicada para aplicações com vetores pequenos que realizam poucas buscas. A binária, por outro lado, pode ser eficiente, dependendo do caso: inserir dados sempre ordenados aumenta o custo da inserção, que, no caso de aplicação com muitas inserções e atualizações nos dados, é um ponto importante; ordenar apenas quando atualizar vai aumentar o custo das atualizações, que também são muito recorrentes nesse caso. Já uma lista encadeada não permite encontrar os elementos de forma veloz, pois é necessário percorrê-la do início ao fim. Assim, a resposta correta é tabela hash, pois, dada uma chave, é possível inserir e atualizar apenas computando a função hash, que tem baixo custo.
5. 
Uma das maneiras de avaliar o melhor método para uma aplicação é analisar a complexidade de pior e melhor caso dos métodos e constatar com as entradas da aplicação-alvo. Para tanto, é necessário conhecimento sobre ordens assintóticas.
Nesse sentido, qual é a complexidade de pior caso das buscas sequencial, binária e na tabela hash, respectivamente?​​​​​​​
C. O(n), O(log2 n), O(K).
Para calcular a complexidade de pior caso, deve-se pensar na pior entrada possível para o programa. No caso da busca sequencial, como se tem um laço que vai de 1 até N, o pior caso é percorrer esse laço N vezes. Nesse sentido, a complexidade da busca sequencial é O(n). Quando se fala da busca binária, ela é mais eficiente, pois a cada iteração elimina metade do intervalo. Essa eliminação de metade do vetor por vez remete a uma árvore binária, por isso o nome da busca. Nesse caso, a complexidade de tempo é O(log2 n). Por fim, a tabela hash tem uma complexidade de melhor caso de O(1); entretanto, no pior caso, podem ocorrer K colisões, e uma lista encadeada será percorrida até o K-ésimo elemento. Logo, complexidade O(K).
Desafio
As colisões ocorrem quando mais de uma chave é mapeada para a mesma posição da tabela. Quando isso acontece, uma busca sequencial naquela posição é necessária para encontrar uma chave. Se isso acontecer muitas vezes, o desempenho de uma aplicação ou sistema pode ser reduzido em até centenas de vezes.
Qual função hash você utilizaria, buscando diminuir o número de colisões ocorridas? Exemplifique.
O defeito da função hash utilizada originalmente é que ela retorna sempre o primeiro caractere do nome da pessoa. Fazendo isso, sempre que os nomes começarem com a mesma letra, diversas colisões irão ocorrer. Uma função hash mais eficiente seria uma que, utilizando multiplicação por números primos, utilizasse todos os caracteres da string e não só o primeiro.
Por exemplo:
def funcao_hash(chave, tamanho_tabela):
 valor = 5381
 for caractere in chave:
 valor = 33 * valor + ord(caractere)
 valor = valor % tamanho_tabela
 return valor
print(funcao_hash("João", 1024))
print(funcao_hash("Maria", 1024))