AED Algoritmos e Estruturas de Dados LEEC /2007. Tabelas de Dispersão - PDF
Download "AED Algoritmos e Estruturas de Dados LEEC /2007. Tabelas de Dispersão"
Eliza Philippi di Azevedo
1 AED Algoritmos e Estruturas de Dados LEEC /2007 Tabelas de Dispersão Tabelas de Dispersão - Introdução (1) As tabelas de dispersão (hash tables) são estruturas de dados adequadas para: Tabelas de símbolos para compiladores Dicionários etc Elementos identificados por uma chave genérica As tabelas de dispersão beneficiam da elevada rapidez revelada pelas tabelas/listas nas principais operações de manipulação de dados: Inserção (rápida em listas) Acesso (rápida em tabelas) AED (IST/DEEC) 2
2 Tabelas de Dispersão - Introdução (2) Relembrando a eficiência das operações em várias alternativas de representação: LISTAS ÁRVORES TABELAS Acesso O(N) O(log N) O(1) Inserção O(1) O(log N) O(N) Procura O(N) O(log N) O(log N) A chave evita procura (sempre custosa) Será possível usar capacidade ilimitada da lista, com a eficiência de uma tabela? Se sim, como inserir um dado numa tabela cheia? Chave: campo único em cada registo (ex: número de aluno) AED (IST/DEEC) 3 Tabelas de Dispersão - Introdução (3) Dispersão de 8 elementos por N listas (N=1,2,3,...). -1 lista: -2 listas: -3 listas: Conclusão: é necessária uma função de distribuição de elementos por cada lista. AED (IST/DEEC) 4
3 Tabelas de Dispersão - Introdução (4) No limite, teremos uma tabela de N posições: em cada posição temos uma lista de tamanho 1. Função de dispersão: converte a chave genérica de cada elemento num índice da tabela. Elemento (chave) Função de Dispersão AED (IST/DEEC) 5 Tabelas de Dispersão - Introdução (5) Colisão: situação em que duas chaves diferentes resultaram, pela função de dispersão, no mesmo índice da tabela. Énecessário estabelecer a estratégia para resolução de colisões Compromisso entre espaço-tempo Sem limitações de espaço: função de dispersão trivial, em que a chave resulta num endereço de memória. Sem limitações de tempo: resolução de colisões através de procura sequencial. Com limitações de espaço e tempo: Tabelas de Dispersão AED (IST/DEEC) 6
4 Tabelas de Dispersão Introdução(6) As tabelas de dispersão utilizam: tabela base de indexação funções de dispersão algoritmos para resolução de colisões (se necessário) AED (IST/DEEC) 7 Tabela Base Métodos de dispersão com índices livres: Quando o número de elementos pode ser estimado à partida em N Tabela de M elementos (M > N) 0 M-1 Métodos de dispersão por separação em listas: Quando o número de elementos a guardar (N) édesconhecido Tabela de M listas de elementos (M < N) 0 M-1 AED (IST/DEEC) 8
5 Funções de Dispersão (1) Objectivo: Distribuir uniformemente chaves do elementos por inteiros entre [0, M-1] (evitar colisões) A função de dispersão mais usada é a divisão: Chaves pequenas (representáveis por uma palavra de memória): tratar as chaves como inteiros (k) h(k) = k % M (em C, % calcula o resto da divisão inteira) usar um número primo para M. AED (IST/DEEC) 9 Funções de Dispersão (2) Chave k k%1000 k%1024 k% colisão, usados apenas os 3 últimos dígitos 2 colisões, usados apenas os 10 bits de menor peso AED (IST/DEEC) 10
6 Funções de Dispersão (3) Chaves longas (cadeias de caracteres) usar cada caracter como um inteiro (valor da representação ASCII) h(k) = k % M dar um peso a cada caracter correspondente à sua posição na cadeia usar um número primo para o tamanho da tabela #define PESO 117 int hash(char *s, int M){ unsigned h; for (h=0; *s!= \0 ; s++) h = (PESO*h + (unsigned)*s) % M; return h;} Carct ASCII a 97 b 98 c 99 hash( abc,101) = 37 PESO, número primo da ordem de M, usado normalmente quando se tem M>>strlen(s) AED (IST/DEEC) 11 Funções de Dispersão (4) Outras funções (computacionalmente mais complexas) Mediania: somar os quadrados dos valores obtidos em cada símbolo, retirando n bits do meio do código dos caracteres (n = log 2 M) Partição: dividir o código dos caracteres em segmentos de n bits, somar os segmentos e tomar os n bits de menor peso. AED (IST/DEEC) 12
7 Introdução às tabelas de dispersão Componentes das tabelas de dispersão Funções de dispersão divisão Síntese da Aula 1 de Tabelas de Dispersão AED (IST/DEEC) 13 Resolução de Colisões (1) Para uma tabela de tamanho M, quantas inserções podem ser feitas até àprimeira colisão? Problema clássico de probabilidades: Para uma função de dispersão aleatória as primeiras colisões ocorrem ao fim de sqrt(pi*m/2) M sqrt(pi*m/2) Os algoritmos de resolução de colisões depende do tipo de tabela base escolhido. AED (IST/DEEC) 14
8 Resolução de Colisões (2) Procura linear N < M : método com índices livres. Dado que há sempre posições livres na tabela, procurar outra posição. Procura linear: se a posição correspondente ao índice devolvido pela função de dispersão estiver ocupada, ir incrementando o índice até se encontrar uma posição livre. AED (IST/DEEC) 15 Resolução de Colisões (3) Procura linear AED (IST/DEEC) 16
9 Desempenho: Resolução de Colisões (4) Procura linear os elementos tendem a ficar agrupados (clusters) os agrupamentos grandes tendem a crescer ainda mais o tempo médio de procura tende a crescer para M à medida que a tabela enche operações na tabela de dispersão tornam-se demasiado lentas quando a tabela atinge 70% - 80% da sua capacidade. AED (IST/DEEC) 17 Resolução de Colisões (5) Dupla Dispersão Dupla dispersão: se a posição correspondente ao índice devolvido pela função de dispersão estiver ocupada, utilizar outra função de dispersão para determinar o valor a incrementar na procura de uma posição livre para o elemento. aleatória quadrática (p i =ai 2 +bi+c, em que a,b,c são função da máquina) linear (p i =ni) Desempenho: evita a criação de agrupamentos operações na tabela de dispersão só se tornam demasiado lentas quando a tabela atinge 90% - 95% da sua capacidade AED (IST/DEEC) 18
10 Resolução de Colisões (6) Dupla Dispersão Inc.=5 Inc.=3 Inc.=3 Inc.=1 AED (IST/DEEC) 19 Resolução de Colisões (7) Número médio de comparações em função do factor de carga lf load factor = N/M: Aleatório E r = -1/lf*ln(1-lf) Linear E l = (1-lf/2)/(1-lf) Encadeado E c = 1+lf/2 lf El Er Ec 20% % % % % AED (IST/DEEC) 20
11 Resolução de Colisões (8) Inserção no início N > M : método de separação em listas (endereçamento encadeado). Dado que há menos posições na tabela que elementos, vão de certeza ocorrer colisões. Inserção no início: se a lista correspondente ao índice devolvido pela função de dispersão já contiver elementos, inserir o novo elemento no início da lista. AED (IST/DEEC) 21 Resolução de Colisões (9) Inserção no início a a a e e u e o o i i i Custo de inserção: 1 Custo médio de procura (sem sucesso): N/M Custo médio de procura (com sucesso): N/2M AED (IST/DEEC) 22
12 a e Resolução de Colisões (10) Inserção ordenada Inserção ordenada: se a lista correspondente ao índice devolvido pela função de dispersão já contiver elementos, inserir ordenadamente o novo elemento na lista. a e a e u i i Custo de inserção: N/2M Custo médio de procura (com ou sem sucesso): N/2M AED (IST/DEEC) 23 Resolução de Colisões (11) #include <stdlib.h> #include <string.h> #define HASHSIZE 211 typedef struct _s { char *name; int id; struct _s *next; } table_element; table_element *HashTab[HASHSIZE]; table_element *search(char *Str){ table_element *ptr = HashTab[hash(Str, HASHSIZE)]; for( ; ptr!= NULL; ptr = ptr->next) if(!strcmp(str, ptr->name)) return ptr; return NULL;} AED (IST/DEEC) 24
13 Resolução de Colisões (12) table_element *insert(char *Str, int Val){ table_element *ptr; unsigned HashVal; if((ptr = search(str)) == NULL){ ptr = (table_element *) malloc(sizeof(table_element)); if(ptr == NULL) return NULL; HashVal = hash(str, HASHSIZE); ptr->name = strdup(str); ptr->id = Val; ptr->next = HashTab[HashVal]; HashTab[HashVal] = ptr;} return ptr;} AED (IST/DEEC) 25 Tabelas de Dispersão - Conclusão Implementam operações de inserção e procura em tempo constante (análise amortizada). Desvantagens: não há garantia de desempenho ( performance ) chaves longas podem envolver muita aritmética podem ocupar mais memória do que necessário não suportam eficientemente todas as operações sobre tipos de dados abstractos (ordenação, etc) AED (IST/DEEC) 26
14 Resolução de colisões Dupla dispersão Síntese da Aula 2 de Tabelas de Dispersão Encadeado Comparação da eficiência AED (IST/DEEC) 27
São Carlos, 01 de outubro 2010 THE R* - TREE : AN EFFICIENT AND ROBUST ACCESS METHOD FOR POINTS AND RECTANGLES+
São Carlos, 01 de outubro 2010 THE R* - TREE : AN EFFICIENT AND ROBUST ACCESS METHOD FOR POINTS AND RECTANGLES+ Conceito R* -tree É uma variante da R-tree utilizada para indexação de informação espacial;
Laboratório 12 Pesquisa e Ordenação
Instituto Politécnico de Setúbal Escola Superior de Tecnologia Departamento de Sistemas e Informática Laboratório 12 Pesquisa e Ordenação Disciplina de Introdução à Programação Ano Lectivo 2006/2007 DSI
Arquivos de Acesso Direto. Vanessa Braganholo
Arquivos de Acesso Direto Vanessa Braganholo Arquivo de Acesso Direto } Definição: arquivo em que o acesso a um registro pode ser feito diretamente, sem ter que ler todos os registros que vêm antes dele