|
||
| A. Ciências Exatas e da Terra - 2. Ciência da Computação - 17. Ciência da Computação | ||
| UMA AVALIAÇÃO DE ESTRUTURAS DE DADOS HÍBRIDAS: HASHING (ABERTO COM AVL) + REHASHING | ||
| Ingrid Guedes Teles 1 (ingridteles@yahoo.com.br), Rogério Trévia Nibon 1, Wiler Rodrigues Coelho Junior 1 e Marcos José Negreiros Gomes 1 | ||
| (1. Depto. de Estatística e Computação, Universidade Estadual do Ceará - UECE) | ||
| INTRODUÇÃO:
A combinação de diferentes estruturas de dados pode resultar em um ganho de performance na resolução de problemas que envolvem inserção, remoção e busca de dados. Este trabalho tem como objetivo apresentar uma dessas combinações, a qual envolve árvores AVL, Tabelas de Difusão Aberta e Fechada, com rehashing simples e dobrado, criando-se uma estrutura híbrida na tentativa de otimizar os tempos das operações de inserção, de busca e de remoção, comparando o tempo de execução dessas operações com estruturas de alto desempenho já conhecidas. |
||
| METODOLOGIA:
Foi utilizado o open hashing, pois ele permite a inserção de elementos em posições já ocupadas da tabela de difusão (hashing), para isto a estrutura dinâmica árvore AVL foi associada a cada posição da tabela. Caso a estrutura dinâmica fosse uma lista encadeada, a complexidade no pior caso seria O(n), enquanto que com árvores AVL a complexidade é O(log(n)). Quando a altura da árvore de uma posição da tabela ultrapassa um certo limite (fator de carga) informado, consideramos então que ocorreu uma colisão e aplicamos a tentativa quadrática para localizar uma outra posição para este elemento. Após várias inserções, se a tabela ficar “meio cheia”, continuar o processo pode não ser útil, pois não teremos garantia de encontrar uma posição livre na estrutura, conforme o teorema da tentativa quadrática do hashing fechado. Quando isto acontece fazemos o rehashing que pode ser do tipo simples ou dobrado, dependendo do parâmetro informado pelo usuário. O ambiente de desenvolvimento e de testes foi o sistema operacional Windows XP, com processador AMD Athlon 1.15GHz, memória RAM de 512MB. A linguagem programação utilizada foi Java, v1.4.2 e a ferramenta para geração dos gráficos comparativos foi o JFreeChart 0.9.21. Utilizamos também a linguagem C++, compilador Borland C++ Builder, com o objetivo de avaliar o comportamento dos procedimentos implementados na forma compilada. |
||
| RESULTADOS:
Comparando o rehashing simples com o dobrado notamos que o número de rehashing realizados pelo tipo simples é bem maior que os realizados pelo tipo dobrado. O tamanho da tabela final quando o rehashing simples é utilizado é bem menor que o tamanho da tabela final quando o rehashing dobrado é utilizado, otimizando assim o uso da memória no primeiro caso. A ocorrência de colisões no rehashing simples é bem maior. Comparando o tempo de inserção da árvore AVL com o do rehashing dobrado com AVL, no início o desempenho da árvore AVL é melhor, mas à medida que uma grande quantidade de elementos é inserida, o rehashing dobrado tem um ganho considerável no tempo médio de processamento das inserções mantendo-se em grande vantagem do ponto de vista custo de memória versus desempenho médio no tempo. Obviamente os métodos mantiveram-se com comportamentos estáveis nas duas linguagens, porém as avaliações de experimentos em C++ puderam ser maiores, haja vista a sua estrutura intrínseca (compilada). |
||
| CONCLUSÕES:
A combinação de estruturas de dados simples pode resultar em outras estruturas híbridas poderosas, que têm um desempenho extraordinário em certas aplicações. O ganho de desempenho pode implicar em uma subutilização de memória e, portanto, é importante que se faça uma análise detalhada do objetivo, julgando a relação custo/benefício que a estrutura pode trazer. |
||
| Trabalho de Iniciação Científica | ||
| Palavras-chave: Estruturas de Dados; Árvores AVL; Tabelas hashing. | ||
| Anais da 57ª Reunião Anual da SBPC - Fortaleza, CE - Julho/2005 |