Pesquisa em Memória Primária - Hashing David Menotti Estruturas de Dados I DECOM – UFOP

  • Published on
    17-Apr-2015

  • View
    102

  • Download
    0

Embed Size (px)

Transcript

<ul><li> Slide 1 </li> <li> Pesquisa em Memria Primria - Hashing David Menotti Estruturas de Dados I DECOM UFOP </li> <li> Slide 2 </li> <li> David Menotti Estrutura de Dados I Transformao de Chave (Hashing) Os registros armazenados em uma tabela so diretamente endereados a partir de uma transformao aritmtica sobre a chave de pesquisa. Hash signica: Fazer picadinho de carne e vegetais para cozinhar. Fazer uma baguna. (Websters New World Dictionary) Espalhar x Transformar (informtica x computao) </li> <li> Slide 3 </li> <li> David Menotti Estrutura de Dados I Um mtodo de pesquisa com o uso da transformao de chave constitudo de duas etapas principais: 1 - Computar o valor da funo de transformao, a qual transforma a chave de pesquisa em um endereo da tabela. 2 - Considerando que duas ou mais chaves podem ser transformadas em um mesmo endereo de tabela, necessrio existir um mtodo para lidar com colises. Qualquer que seja a funo de transformao, algumas colises iro ocorrer fatalmente, e tais 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. Transformao de Chave (Hashing) </li> <li> Slide 4 </li> <li> David Menotti Estrutura de Dados I 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. Assim, se for utilizada uma funo de transformao uniforme que enderece 23 chaves randmicas em uma tabela de tamanho 365, a probabilidade de que haja colises maior do que 50%. Transformao de Chave (Hashing) </li> <li> Slide 5 </li> <li> David Menotti Estrutura de Dados I A probabilidade p de se inserir N itens consecutivos sem coliso em uma tabela de tamanho M : Transformao de Chave (Hashing) </li> <li> Slide 6 </li> <li> David Menotti Estrutura de Dados I NP 100,883 220,524 230,493 300,303 Alguns valores de p para diferentes valores de N, onde M = 365. Para N pequeno a probabilidade p pode ser aproximada por p N (N 1))/730. Por exemplo, para N = 10 ento p 87,7%. Transformao de Chave (Hashing) </li> <li> Slide 7 </li> <li> David Menotti Estrutura de Dados I Funes de Transformao 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. </li> <li> Slide 8 </li> <li> David Menotti Estrutura de Dados I Mtodo mais Usado Usa o resto da diviso por M. h(K) = K % M (em linguagem C ) onde K um inteiro correspondente chave. </li> <li> Slide 9 </li> <li> David Menotti Estrutura de Dados I Mtodo mais Usado Cuidado na escolha do valor de M. M deve ser um nmero primo, mas no qualquer primo: devem ser evitados os nmeros primos obtidos a partir de b*i j onde b a base do conjunto de caracteres (geralmente b = 64 para BCD, 128 para ASCII, 256 para EBCDIC, ou 100 para alguns cdigos decimais), e i e j so pequenos inteiros. </li> <li> Slide 10 </li> <li> David Menotti Estrutura de Dados I Transformaes de Chaves no numricas 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 randomicamente para 1 i n. </li> <li> Slide 11 </li> <li> David Menotti Estrutura de Dados I Vantagem de se usar pesos: Dois conjuntos diferentes de pesos p1[i] e p2[i], 1 i n, leva a duas funes de transformao h1(K) e h2(K) diferentes. Transformaes de Chaves no numricas </li> <li> Slide 12 </li> <li> David Menotti Estrutura de Dados I Programa que gera um peso para cada caractere de uma chave constituda de n caracteres: void GeraPesos(TipoPesos p) { /* Gera valores randomicos entre 1 e 10.000 */ int i; struct timeval semente; /* Utilizar o tempo como semente para a funcao srand() */ gettimeofday(&amp;semente,NULL); srand((int)(semente.tv_sec + 1000000*semente.tv_usec)); for (i = 0; i &lt; n; i++) p[i] = 1+(int) (10000.0*rand()/(RAND_MAX+1.0)); } Transformaes de Chaves no numricas </li> <li> Slide 13 </li> <li> David Menotti Estrutura de Dados I Implementao da funo de transformao: Indice h(TipoChave Chave, TipoPesos p) { int i; unsigned int Soma = 0; int comp = strlen(Chave); for (i = 0; i &lt; comp; i++) Soma += (unsigned int)Chave[i] * p[i]; return (Soma % M); } Transformaes de Chaves no numricas </li> <li> Slide 14 </li> <li> David Menotti Estrutura de Dados I Resolvendo colises Listas Encadeadas Endereamento Aberto </li> <li> Slide 15 </li> <li> David Menotti Estrutura de Dados I Listas Encadeadas Uma das formas de resolver as colises simplesmente construir uma lista linear encadeada para cada endereo da tabela. Assim, todas as chaves com mesmo endereo so encadeadas em uma lista linear. </li> <li> Slide 16 </li> <li> David Menotti Estrutura de Dados I Listas Encadeadas Exemplo: Se a i-sima letra do alfabeto representada pelo nmero i e a funo de transformao h(Chave) = Chave mod M utilizada para M = 7, o resultado da insero das chaves P E S Q U I S A na tabela o seguinte: Por exemplo, h(A) = h(1) = 1, h(E) = h(5) = 5, h(S) = h(19) = 5, etc </li> <li> Slide 17 </li> <li> David Menotti Estrutura de Dados I Exemplo F E R I A D O </li> <li> Slide 18 </li> <li> David Menotti Estrutura de Dados I Endereamento Aberto Quando o nmero de registros a serem armazenados na tabela puder ser previamente estimado, ento no haver necessidade de usar apontadores para armazenar os registros. Existem vrios mtodos para armazenar N registros em uma tabela de tamanho M &gt; N, os quais utilizam os lugares vazios na prpria tabela para resolver as colises. (Knuth, 1973, p.518) </li> <li> Slide 19 </li> <li> David Menotti Estrutura de Dados I No Endereamento aberto todas as chaves so armazenadas na prpria tabela, sem o uso de apontadores explcitos. Existem vrias propostas para a escolha de localizaes alternativas. A mais simples chamada de hashing linear, onde a posio h j na tabela dada por: h j = (h(x) + j) mod M, para 1 j M 1. Endereamento Aberto </li> <li> Slide 20 </li> <li> David Menotti Estrutura de Dados I Exemplo Se a i-sima letra do alfabeto representada pelo nmero i e a funo de transformao h(Chave) = Chave mod M utilizada para M = 7, ento o resultado da insero das chaves L U N E S na tabela T, usando hashing linear para resolver colises mostrado abaixo. </li> <li> Slide 21 </li> <li> David Menotti Estrutura de Dados I Exemplo Por exemplo: 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> C digo para Tratamento de Coliso Usando Listas Encadeadas </li> <li> Slide 23 </li> <li> David Menotti Estrutura de Dados I #define M 7 #define n 21 /* tamanho da chave */ typedef char TipoChave[n]; typedef unsigned int TipoPesos[n]; typedef struct { /* outros componentes */ TipoChave Chave; } TipoItem; typedef unsigned int Indice; Estrutura do Dicionrio para Listas Encadeadas </li> <li> Slide 24 </li> <li> David Menotti Estrutura de Dados I typedef struct _celula* Apontador; typedef struct _celula { TipoItem Item; Apontador Prox; } Celula; typedef struct { Celula *Primeiro, *Ultimo; } TipoLista; typedef TipoLista TipoDicionario[M]; Estrutura do Dicionrio para Listas Encadeadas </li> <li> Slide 25 </li> <li> David Menotti Estrutura de Dados I void Inicializa(TipoDicionario T) { int i; for (i = 0; i &lt; M; i++) FLVazia(&amp;T[i]); } Operaes do Dicionrio Usando Listas Encadeadas </li> <li> Slide 26 </li> <li> David Menotti Estrutura de Dados I Apontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T) { /*Obs.: Apontador de retorno aponta para o item anterior da lista */ Indice i; Apontador Ap; i = h(Ch, p); if (LEhVazia(T[i])) return NULL; /* Pesquisa sem sucesso */ else { Ap = T[i].Primeiro; while ((Ap-&gt;Prox-&gt;Prox != NULL) &amp;&amp; (strncmp(Ch, Ap-&gt;Prox-&gt;Item.Chave, sizeof(TipoChave)) )) {Ap = Ap-&gt;Prox;} if (!strncmp(Ch, Ap-&gt;Prox-&gt;Item.Chave, sizeof(TipoChave))) return Ap; else return NULL; /* Pesquisa sem sucesso */ } Operaes do Dicionrio Usando Listas Encadeadas </li> <li> Slide 27 </li> <li> David Menotti Estrutura de Dados I int Insere(TipoItem x, TipoPesos p, TipoDicionario T) { if (Pesquisa(x.Chave, p, T) == NULL) { Ins(&amp;(T[h(x.Chave, p)),x]); return 1;} return 0; } int Retira(TipoItem x, TipoPesos p, TipoDicionario T) { Apontador Ap; Ap = Pesquisa(x.Chave, p, T); if (Ap == NULL) return 0; Ret(&amp;(T[h(x.Chave, p)]), Ap, &amp;x); return 1; } Operaes do Dicionrio Usando Listas Encadeadas </li> <li> Slide 28 </li> <li> David Menotti Estrutura de Dados I Anlise Assumindo que qualquer item do conjunto tem igual probabilidade de ser endereado para qualquer entrada de T, ento o comprimento esperado de cada lista encadeada N/M, onde N representa o nmero de registros na tabela e M o tamanho da tabela. Logo: as operaes Pesquisa, Insere e Retira custam O(1 + N/M ) operaes em mdia, onde a constante 1 representa o tempo para encontrar a entrada na tabela e N/M o tempo para percorrer a lista. Para valores de M prximos de N, o tempo se torna constante, isto , independente de N. </li> <li> Slide 29 </li> <li> C digo para Endereamento Aberto </li> <li> Slide 30 </li> <li> David Menotti Estrutura de Dados I #define Vazio "!!!!!!!!!!!!!!!!!!!!" #define Retirado "********************" #define M 7 #define n 21 /* Tamanho da chave */ Estrutura do Dicionrio Usando Endereamento Aberto </li> <li> Slide 31 </li> <li> David Menotti Estrutura de Dados I 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]; Estrutura do Dicionrio Usando Endereamento Aberto </li> <li> Slide 32 </li> <li> David Menotti Estrutura de Dados I void Inicializa(TipoDicionario T) { int i; for (i = 0; i &lt; M; i++) memcpy(T[i].Chave, Vazio, n); } Estrutura do Dicionrio Usando Endereamento Aberto </li> <li> Slide 33 </li> <li> David Menotti Estrutura de Dados I Apontador Pesquisa(TipoChave Ch, TipoPesos p, TipoDicionario T) { unsigned int i = 0; unsigned int Inicial; Inicial = h(Ch, p); 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 */ } Estrutura do Dicionrio Usando Endereamento Aberto </li> <li> Slide 34 </li> <li> David Menotti Estrutura de Dados I int Insere(TipoItem x, TipoPesos p, TipoDicionario T) { unsigned int i = 0; unsigned int Inicial; if (Pesquisa(x.Chave, p, T) &lt; M) return 0; Inicial = h(x.Chave, p); 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) { /* Copiar os demais campos de x, se existirem */ strcpy (T[(Inicial + i) % M].Chave, x.Chave); return 1; } else return 0; } Estrutura do Dicionrio Usando Endereamento Aberto </li> <li> Slide 35 </li> <li> David Menotti Estrutura de Dados I int Retira(TipoChave Ch, TipoPesos p, TipoDicionario T) { Indice i; i = Pesquisa(Ch, p, T); if (i == M) return 0; memcpy(T[i].Chave, Retirado, n); return 1; } Estrutura do Dicionrio Usando Endereamento Aberto </li> <li> Slide 36 </li> <li> David Menotti Estrutura de Dados I 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(clustering) (Knuth, 1973, pp.520521). Este fenmeno 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. Anlise </li> <li> Slide 37 </li> <li> David Menotti Estrutura de Dados I Anlise Entretanto, apesar do hashing linear ser um mtodo relativamente pobre para resolver colises os resultados apresentados so bons. O melhor caso, assim como o caso mdio, O(1). </li> <li> Slide 38 </li> <li> David Menotti Estrutura de Dados I Vantagens e Desvantagens de Transformaes de Chaves Vantagens: Alta ecincia no custo de pesquisa, que O(1) para o caso mdio. Simplicidade de implementao Desvantagens: Custo para recuperar os registros na ordem lexicogrca das chaves alto, sendo necessrio ordenar o arquivo. Pior caso O(N) </li> </ul>