Artigo Java Magazine 71 - Java Collections Framework

Java Collections Framework

Conhecendo o desempenho das suas estruturas de dados

Aprenda como medir o desempenho das classes contidas na Java Collections Framework e escolher a mais eficiente para cada tarefa

De que se trata o artigo:

Análise empírica das estruturas de dados do Java Collections Framework, de acordo com as operações de inserção, busca e remoção. Neste artigo, fala-se da implementação de um benchmark para fazer a medição de desempenho das principais classes das interfaces List, Set e Map.

Para que serve:

Visa mostrar ao leitor qual a melhor estrutura de dados a ser utilizada de acordo com uma operação. Para isso é utilizado um software matemático chamado Octave, o qual é ideal para operações algébricas e para gerar gráficos através de programação.

Em que situação o tema é útil:

O conhecimento do desempenho das estruturas de dados visa melhorar o tempo de execução dos seus próximos programas. Toda estrutura possui pontos fortes e fracos: o segredo é saber balancear esses pontos para se obter um bom desempenho em programas complexos.

Java Collections Framework:

O Java Collections Framework contém estruturas de dados pré-empacotadas, bem como algoritmos para sua manipulação, oferecendo excelente desempenho com maximização da velocidade de execução e minimização do consumo de memória. O estudo de estruturas de dados é essencial para que seja desenvolvido um programa com bom desempenho.

Neste artigo foi realizado um estudo empírico para averiguar quais estruturas desse framework apresentam os melhores desempenhos em uma dada operação. Para isso fizemos a implementação de um benchmark para a análise de desempenho das estruturas, sendo analisadas as operações de inserção, busca e remoção de elementos.

Veremos uma abordagem prática sobre o framework de coleções em Java. Os quesitos de avaliação são inserção de dados, busca e remoção, os quais serão explorados de forma empírica, investigando o desempenho de cada tipo de coleção. A implementação desses testes e os resultados obtidos permitirão ao leitor conhecer de forma mais concreta e prática as características das collections, cujo uso adequado pode ser importante para o bom desempenho da maioria das aplicações.

Introdução ao framework de coleções em Java

O framework de coleções em Java (Java Collections Framework) possibilita o uso e extensão de estruturas de dados comuns de forma fácil e flexível. Com pouco esforço é possível implementar listas, conjuntos, mapas e outros containers de objetos ersos para atender às várias finalidades das suas aplicações.

Este framework contém estruturas de dados pré-empacotadas, bem como algoritmos para sua manipulação, oferecendo aos programadores excelente desempenho com maximização da velocidade de execução e minimização do consumo de memória.

Muitas das operações inerentes às coleções são executadas sem intervenção dos programadores, como por exemplo, impedir elementos repetidos em conjuntos e organizar a ordem dos objetos armazenados em mapas, listas e conjuntos.

A referência deste framework pode ser encontrada na documentação da Java SE 6: java.sun.com/javase/6/docs/technotes/guides/collections/.

Para conhecer melhor o framework de coleções do Java, veja mais informações sobre as interfaces Collection, Set, List, SortedSet, Map e SortedMap.

Descrição da implementação

Comparamos as principais implementações das interfaces List, Set e Map. Para List, selecionamos as classes ArrayList, Vector e LinkedList; para Set, HashSet, LinkedHashSet e TreeSet; e para Map, HashMap, LinkedHashMap e TreeMap.

Para medir o desempenho das estruturas de cada grupo, começamos criando conjuntos de dados aleatórios. Após isso, medimos os tempos de inserção desses dados nas estruturas, medimos os tempos de busca de 100 elementos aleatórios contidos em cada estrutura. Depois, medimos os tempos de remoção de todos os dados das estruturas. Os tempos de execução de cada etapa são medidos e guardados em arquivos com a extensão .dat. Tais arquivos são processados pelo software Octave (www.octave.org) e os gráficos são gerados.

A Listagem 1 mostra o código referente à geração de números aleatórios. Note que usamos o método Set.contains() para detectar números já gerados e evitar repetições.

Listagem 1. Método para gerar números aleatórios e não-repetidos

public String gerarNumerosAleatorios(int n, int max) {

  HashSet<Integer> HS = new HashSet<Integer>();

  int valor=0;

  StringBuilder sb = new StringBuilder();

  Random Gerador = new Random();