Java Collections

Prévia do material em texto

UFPI - CCN - CIÊNCIA DA COMPUTAÇÃO
ESTRUTURA DE DADOS - Professor: Dr. Raimundo Moura
RELATÓRIO TÉCNICO
Eduardo Bezerra de Sousa
Ildefonso Amorim de Souza Braga Mury
Rodrigo do Nascimento Borges
Vicente Cleyton Gonçalves de Sousa Carvalho
TRABALHO FINAL - COLLECTIONS
1) A classe ArrayList tem como estrutura base um vetor alocado
dinamicamente, portanto maleável de acordo com o tamanho necessário. Em
estruturas desse tipo é possível acessar os elementos diretamente, bastando apenas
conhecer o índice. Em contrapartida, quando se trata de adicionar ou remover um
elemento, é preciso percorrer a estrutura, o que resulta em um custo computacional
relativamente alto (O(n)). Não há remoção automática de elementos duplicados. Tal
aplicação também não é thread-safe, ou seja, não pode ser manipulada por diferentes
tarefas simultaneamente.
A classe Vector tem a mesma implementação de ArrayList, distinguindo em um
único ponto, sendo ele o thread-safety (ou sincronização).
A classe LinkedList se baseia na alocação de um nó e um ponteiro para outro
nó, logo, a adição e remoção de elementos é ideal, pois faz as operações no início,
meio e fim da lista sem mudar a estrutura. Tal aplicação também aceita elementos
duplicados. Por outro lado, para buscar e mudar algum nó é necessário percorrer a lista
sendo a complexidade no pior caso de ordem N.
- Implementação
O código feito em Java com a ferramenta Eclipse implementa a classe
LinkedList da Collections API e utiliza a leitura de um arquivo predefinido como
forma de entrada. Nome do arquivo: “leipzig100k.txt” - aproximadamente
140.000 palavras.
. Também é usada a classe Stopwatch para calcular o tempo de execução
do programa, e os gráficos pedidos em questões futuras são gerados em
classes externas.
(Figura 1: Predefinição do arquivo utilizado no programa).
(Fig. 2: Implementação da lista encadeada para a primeira questão.)
(Fig. 3: Resultado da execução do programa com tempo de execução).
2) Inicialmente vale ressaltar que todas as três classes se configuram pela
condição Set, portanto podemos estabelecer que elas aceitarão somente valores
únicos (não há repetição de elementos).
A Hashset usa como base uma HashTable, associando assim valores de
chaves, busca e achar o valor desejado. A complexidade para as operações simples
(adicionar,remover e alterar) de forma geral é boa, pois não importa a quantidade de
chaves, sempre será O(1). Porém o funcionamento dessa classe não garante a
ordenação dos elementos.
A TreeSet tem como definição uma árvore binária de busca, sendo assim sua
implementação garante a ordenação dos componentes. No entanto, as operações de
adição e remoção são de categoria O(log (n)), sendo assim um pouco mais demorada
que a HashSet. É importante também que os objetos possam ser comparáveis ou ser
adicionado um comparador para garantir a ordenação.
Finalmente na LinkedHashSet temos um meio termo das classes anteriores,
tendo uma boa performance como a HashTable e ordenação como a TreeSet. Um
ponto exclusivo dessa classe é a interação com a mesma ordem de inserção.
- Implementação
O código feito em Java com a ferramenta Eclipse implementa a classe
HashSet da Collections API e utiliza a leitura de um arquivo predefinido como
forma de entrada. Nome do arquivo: “leipzig100k.txt” - aproximadamente
140.000 palavras.
Também é usada a classe Stopwatch para calcular o tempo de execução
do programa, e os gráficos pedidos em questões futuras são gerados em
classes externas.
(Fig. 4: Implementação do HashSet para a segunda questão.)
(Fig. 5: Resultado da execução do programa com tempo de execução.)
3) A HashMap é uma estrutura de dados baseada na função hash com uma
informação de uma única chave associado a um único valor. O acesso a essa
informação é rápida, sendo de ordem constante (O(1)). Porém não existe a ordenação
das chaves ou valores e pode haver chaves nulas.
Já a TreeMap é um mapeamento baseado em árvore binária de busca, e disso
advém a garantia de ordenação dos elementos (novamente é preciso que os dados
sejam comparáveis ou seja adicionado um comparador). Entretanto terá um aumento
no custo das operações, sendo de O(log (n)) e além disso não contém chaves nulas,
mas pode ter valores nulos.
E finalmente a LinkedHashMap é usada para manter a ordem de inserção dos
elementos, sendo sua eficiência mais lenta que HashMap e mais rápida que TreeMap.
- Implementação
O código feito em Java com a ferramenta Eclipse implementa a classe
HashSet da Collections API e utiliza a leitura de um arquivo predefinido como
forma de entrada. Nome do arquivo: “leipzig100k.txt” - aproximadamente
140.000 palavras.
Também é usada a classe Stopwatch para calcular o tempo de execução
do programa, e os gráficos pedidos em questões futuras são gerados em
classes externas.
(Fig. 6: Implementação do HashMap para a terceira questão.)
(Fig. 7: Resultados da execução do programa com tempo de execução.)
4)
(Fig. 8: Gráfico gerado com os dados dos testes.)
5) O código feito em Java com a ferramenta Eclipse implementa 3 métodos de
busca diferentes, um para cada estrutura. É utilizado a leitura de um arquivo
predefinido como forma de entrada. Nome do arquivo: “leipzig100k.txt” -
aproximadamente 140.000 palavras, e as palavras a serem buscadas são: Lisbon,
NASA, Kyunghee, Konkuk, Sogang, momentarily, rubella, vaccinations,
government, Authorities.
Dessa vez o tempo de execução foi medido em nanossegundos devido a pouca
precisão obtida em duas das três buscas quando medidas em segundos.
(Fig. 9: String auxiliar que contém as palavras a serem buscadas no programa.)
O algoritmo consiste em percorrer a string auxiliar usando um foreach e buscar
pela palavra correspondente nas estruturas usando os métodos contains para
LinkedList e HashSet e containsKey para o HashMap. O tempo de execução é contado
de antes do início da repetição até seu fim.
(Fig. 10: Implementação dos métodos de busca para a quinta questão.)
6)
(Fig. 11: Gráfico gerado com os dados dos testes.)
7) O código feito em Java com a ferramenta Eclipse implementa 3 métodos de
remoção diferentes, um para cada estrutura. É utilizado a leitura de um arquivo
predefinido como forma de entrada. Nome do arquivo: “leipzig100k.txt” -
aproximadamente 140.000 palavras, e as palavras a serem buscadas são: Lisbon,
NASA, Kyunghee, Konkuk, Sogang, momentarily, rubella, vaccinations,
government, Authorities. Nesta implementação é usada a mesma string auxiliar da
questão 5.
O tempo de execução nesta resolução também foi medido em nanossegundos
devido a pouca precisão obtida em duas das três buscas quando medidas em
segundos.
O algoritmo consiste em percorrer a string auxiliar usando um foreach e remover
a palavra correspondente nas estruturas usando o método remove presente nas 3
classes. O tempo de execução é contado de antes do início da repetição até seu fim.
(Fig. 12: Implementação dos métodos de remoção para a sétima questão.)
8)
(Fig. 13: Gráfico gerado com os dados dos testes.)
9) A classe PriorityQueue é implementada quando a fila deve ser operada com
base em uma prioridade. A ordenação da fila será baseada na comparação natural dos
valores ou usando o comparador definido na construção. Um ponto negativo é a
obrigatoriedade na comparação dos objetos, pois se não for possível realizar tal
operação, então não teremos a execução do código. A classe também não é segura
para thread e também possui complexidade O(log (n)) para os métodos de adição e
pesquisa.