Pesquisa em memória primária: hashing Algoritmos e Estruturas de Dados II

  • Published on
    18-Apr-2015

  • View
    104

  • Download
    1

Embed Size (px)

Transcript

<ul><li> Slide 1 </li> <li> Pesquisa em memria primria: hashing Algoritmos e Estruturas de Dados II </li> <li> Slide 2 </li> <li> Hashing 2 Algoritmos vistos efetuam comparaes para localizar uma chave. Hashing: mapeia o conjunto das chaves em uma tabela. Dada uma chave, aplica-se uma funo de transformao na chave para obter a posio em que estaria na tabela. </li> <li> Slide 3 </li> <li> Hashing 3 Um mtodo de pesquisa com o uso da transformao de chave constitudo de duas etapas principais: Computar o valor da funo de transformao, a qual transforma a chave de pesquisa em um endereo da tabela. Considerando que duas ou mais chaves podem ser transformadas em um mesmo endereo de tabela, necessrio existir um mtodo para lidar com colises. 20 10 23 74 x%10 funo hashing 020 110 2 323 474 tabela </li> <li> Slide 4 </li> <li> Hashing: colises 4 Quando um grande conjunto de possveis chaves mapeado em um subconjunto pequeno (tabela), fatalmente colises iro ocorrer. Etass colises tm de ser resolvidas de alguma forma. Mesmo que se obtenha uma funo de transformao que distribua os registros de forma uniforme entre as entradas da tabela, existe uma alta probabilidade de haver colises. </li> <li> Slide 5 </li> <li> Hashing: colises 5 O paradoxo do aniversrio (Feller,1968, p. 33), diz que em um grupo de 23 ou mais pessoas, juntas ao acaso, existe uma chance maior do que 50% de que 2 pessoas comemorem aniversrio no mesmo dia. Para hashing: Tabela com 365 posies Adio de 23 chaves Chance &gt; 50% de haver coliso </li> <li> Slide 6 </li> <li> Hashing: colises 6 A probabilidade p de se inserir N itens consecutivos sem coliso em uma tabela de tamanho M : </li> <li> Slide 7 </li> <li> Hashing: colises 7 Seja uma tabela com 50.063.860 de posies (M): Chaves (N)Chance de colisoFator de carga (N/M) 10000.995%0.002% 20003.918%0.004% 400014.772%0.008% 600030.206%0.012% 800047.234%0.016% 1000063.171%0.020% 1200076.269%0.024% 1400085.883%0.028% 1600092.248%0.032% 1800096.070%0.036% 2000098.160%0.040% 2200099.205%0.044% </li> <li> Slide 8 </li> <li> Funo de Transformao 8 Uma funo de transformao deve mapear chaves em inteiros dentro do intervalo [0...M 1], onde M o tamanho da tabela. A funo de transformao ideal aquela que: Seja simples de ser computada. Para cada chave de entrada, qualquer uma das sadas possveis igualmente provvel de ocorrer. Exemplo: Usa o resto da diviso por M (onde k a chave) h(k) = k % M </li> <li> Slide 9 </li> <li> Chaves no Numricas 9 As chaves no numricas devem ser transformadas em nmeros: n o nmero de caracteres da chave. Chave[i] corresponde representao ASCII do i- simo caractere da chave. p[i] um inteiro de um conjunto de pesos gerados para 1 i n. H </li> <li> Slide 10 </li> <li> Chaves no numricas 10 Indice h(TipoChave Chave, TipoPesos p) { unsigned int Soma = 0; int i; int comp = strlen(Chave); for (i = 0; i &lt; comp; i++) Soma += (unsigned int) Chave[i] * p[i]; return (Soma % M); } </li> <li> Slide 11 </li> <li> Resoluo de Colises 11 Encadeamento Endereamento aberto </li> <li> Slide 12 </li> <li> Resoluo de Colises - Encadeamento 12 Cria uma lista encadeada para cada endereo da tabela. Todas as chaves com mesmo endereo na tabela so encadeadas em uma lista linear. 0 U tabela 1 A P 2 3 4 5 E Q I ST </li> <li> Slide 13 </li> <li> Resoluo de Colises Encadeamento 13 Exemplo: Considerando a i-sima letra do alfabeto representada por i e a funo de transformao h(Chave) = Chave mod M (M=10). Insira EXEMPLO na tabela hashing. E = 5 X = 25 M = 13 P = 16 L = 12 O = 15 </li> <li> Slide 14 </li> <li> Estrutura de Dicionrio para Encadeamento 14 #define M 10 #define n 5 typedef char TipoChave[n]; typedef unsigned int TipoPesos[n]; typedef struct { /* outros componentes */ TipoChave Chave; } TipoItem; typedef unsigned int Indice; typedef struct _celula* Apontador; typedef TipoLista TipoDicionario[M]; typedef struct _celula { TipoItem Item; Apontador Prox; } Celula; typedef struct { Celula *Primeiro, *Ultimo; } TipoLista; TipoDicionario M ItemProx Celula TipoLista </li> <li> Slide 15 </li> <li> Estrutura de Dicionrio para Encadeamento 15 void Inicializa(TipoDicionario T) { int i; for (i = 0; i &lt; M; i++) /* inicializa as M listas */ FLVazia(&amp;T[i]); } </li> <li> Slide 16 </li> <li> Estrutura de Dicionrio para Encadeamento 16 Apontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T){ /* Apontador de retorno aponta para o item anterior da lista */ Indice i; Apontador Ap; i = h(Ch, p); if (Vazia(T[i])) return NULL; /* Pesquisa sem sucesso */ else { Ap = T[i].Primeiro-&gt;Prox; while ((Ap-&gt;Prox != NULL) &amp;&amp; (strncmp(Ch, Ap-&gt;Item.Chave, sizeof(TipoChave)))) { Ap = Ap-&gt;Prox;} if (!strncmp(Ch, Ap-&gt;Item.Chave, sizeof(TipoChave))) return Ap; else return NULL; /* Pesquisa sem sucesso */ } </li> <li> Slide 17 </li> <li> Estrutura de Dicionrio para Encadeamento 17 void InsereHashing(TipoItem x, TipoPesos p, TipoDicionario T) { Indice i; if (Pesquisa(x.Chave, p, T) == NULL) /* insere do TAD Lista */ Insere(x, &amp;T[h(x.Chave, p)]); else printf(Registro ja esta presente\n"); } void RetiraHashing(TipoItem x, TipoPesos p, TipoDicionario T) { Apontador Ap = Pesquisa(x.Chave, p, T); if (Ap == NULL) printf(" Registro nao esta presente\n"); else Retira(Ap, &amp;T[h(x.Chave, p)], &amp;x); /*Retira do TAD Lista*/ } </li> <li> Slide 18 </li> <li> Encadeamento: Anlise 18 Tamanho esperado de cada lista: N/M Assumindo que qualquer item do conjunto tem igual probabilidade endereado para qualquer entrada de T. N: nmero de registros, M: tamanho da tabela Operaes Pesquisa, InsereHashing e RetiraHashing: O(1 + N/M) 1: tempo para encontrar a entrada na tabela N/M: tempo para percorrer a lista Tempo constante se N/M for constante. </li> <li> Slide 19 </li> <li> Resoluo de Colises: Endereamento Aberto 19 Neste tipo de estratgia, as chaves so armazenadas na prpria tabela. Quando encontra uma coliso para uma chave x, procura localizaes alternativas h 1 (x),h 2 (x),.... Hashing linear Hashing quadrtico </li> <li> Slide 20 </li> <li> Endereamento Aberto: Exemplo 20 Se a i-sima letra do alfabeto representada pelo nmero i e a funo de transformao abaixo utilizada h(Chave) = Chave mod M No exemplo, considera-se M = 7 O resultado da insero das chaves L U N E S na tabela, usando hashing linear (j = 1 ) para resolver colises mostrado a seguir. </li> <li> Slide 21 </li> <li> Endereamento Aberto: Exemplo 21 h(L) = h(12) = 5 h(U) = h(21) = 0 h(N) = h(14) = 0 h(E) = h(5) = 5 h(S) = h(19) = 5 </li> <li> Slide 22 </li> <li> Endereamento Aberto: Implementao 22 #define Vazio "!!!!!!!!!!" #define Retirado "**********" #define M 7 #define n 11 /* Tamanho da chave */ typedef unsigned int Apontador; typedef char TipoChave[n]; typedef unsigned TipoPesos[n]; typedef struct { /* outros componentes */ TipoChave Chave; } TipoItem; typedef unsigned int Indice; typedef TipoItem TipoDicionario[M]; </li> <li> Slide 23 </li> <li> Endereamento Aberto: Implementao 23 void Inicializa(TipoDicionario T) { int i; /* inicializa todas as posies como vazias */ for (i = 0; i &lt; M; i++) strcpy(T[i].Chave, Vazio); } </li> <li> Slide 24 </li> <li> Endereamento Aberto: Implementao 24 Apontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T) { unsigned int i = 0; unsigned int Inicial; Inicial = h(Ch, p); /* transforma a chave */ while ((strcmp(T[(Inicial + i) % M].Chave, Vazio) != 0) &amp;&amp; (strcmp(T[(Inicial + i) % M].Chave, Ch) != 0) &amp;&amp; (i &lt; M)) i++; if (strcmp(T[(Inicial + i) % M].Chave, Ch) == 0) return ((Inicial + i) % M); else return M; /* Pesquisa sem sucesso */ } </li> <li> Slide 25 </li> <li> Endereamento Aberto: Implementao 25 void Retira(TipoChave Ch, TipoPesos p, TipoDicionario T) { Indice i; i = Pesquisa(Ch, p, T); if (i &lt; M) /* registro encontrado */ strcpy(T[i].Chave, Retirado); else printf("Registro nao esta presente\n"); } </li> <li> Slide 26 </li> <li> Endereamento Aberto: Implementao 26 void Insere(TipoItem x, TipoPesos p, TipoDicionario T) { unsigned int i = 0; unsigned int Inicial; if (Pesquisa(x.Chave, p, T) &lt; M) { printf("Elemento ja esta presente\n"); return; } Inicial = h(x.Chave, p); /* transforma a chave */ while ((strcmp(T[(Inicial + i) % M].Chave, Vazio) != 0) &amp;&amp; (strcmp(T[(Inicial + i) % M].Chave, Retirado) != 0) &amp;&amp; (i &lt; M)) i++; if (i &lt; M) { strcpy (T[(Inicial + i) % M].Chave, x.Chave); /* Copiar os demais campos de x, se existirem */ } else printf(Tabela cheia\n"); } </li> <li> Slide 27 </li> <li> Endereamento Aberto: Anlise 27 Seja = N / M o fator de carga da tabela. Conforme demonstrado por Knuth (1973), o custo de uma pesquisa com sucesso O hashing linear sofre de um mal chamado agrupamento. Ocorre na medida em que a tabela comea a car cheia, pois a insero de uma nova chave tende a ocupar uma posio na tabela que esteja contgua a outras posies j ocupadas, o que deteriora o tempo necessrio para novas pesquisas. </li> <li> Slide 28 </li> <li> Endereamento Aberto: Anlise 28 = N / MC(n) 0.10001.0556 0.20001.1250 0.30001.2143 0.40001.3333 0.50001.5000 0.60001.7500 0.70002.1667 0.80003.0000 0.90005.5000 0.950010.5000 0.980025.5000 0.990050.5000 </li> <li> Slide 29 </li> <li> Vantagens e Desvantagens da Transformao da Chave 29 Vantagens Alta ecincia no custo de pesquisa, que O(1) para o caso mdio. Simplicidade de implementao. Desvantagens Pior caso O(N). </li> </ul>