1
resposta

Fiz o exercício dentro do "main" e percebi a diferença entre HashSet e ArrayList, porem quando passo esse código para uma classe passando esses objetos como parâmetro a diferença praticamente desaparece?

-- MAIN package exerc10;

import java.util.ArrayList; import java.util.Collection; import java.util.HashSet;

public class exerc10 {

public static void main(String[] args) {

int total = 30000;

Collection testeHash = new HashSet(); ComparaTempo c1 = new ComparaTempo(testeHash, total);

System.out.println("Teste com HASHSET"); c1.testaOjeto();

Collection testeList = new ArrayList(); ComparaTempo c2 = new ComparaTempo(testeList, total);

System.out.println("\nTeste com ARRAYLIST"); c1.testaOjeto();

}

}

-- CLASSE

package exerc10;

import java.util.Collection;

public class ComparaTempo {

private long totalRegistro; Collection teste;

public ComparaTempo(Collection teste, long totalRegistro){ this.totalRegistro = totalRegistro; this.teste = teste; }

public void testaOjeto(){

long inicio = System.currentTimeMillis(); System.out.println("INICI0 DO TESTE..."); for(int i = 0; i < this.totalRegistro; i++){ teste.add(i); } long fim = System.currentTimeMillis(); long tempoInserir = fim - inicio; System.out.println("TEMPO GASTO INSERÇÃO: " + tempoInserir);

inicio = System.currentTimeMillis(); for(int i = 0; i < totalRegistro; i++){ teste.contains(i); } fim = System.currentTimeMillis(); long tempoPesquisa = fim - inicio; System.out.println("TEMPO GASTO PESQUISA: " + tempoPesquisa);

System.out.println("TEMPO GASTO TOTAL: " + (tempoPesquisa+tempoInserir));

}

}

1 resposta

Olá Edilson,

Como você não incluiu os tempos que demoraram cada uma das execuções, vamos tentar pensar com base na documentação do Java e de reflexões sobre as estruturas de dados.

No caso do HashSet, a documentação diz que as operações add e contains oferecidas pela classe são desempenhadas em ordem constante (ou seja, O(1), pensando em complexidade de algoritmos), pois é assumido que a função de hash dispersa os elementos de modo apropriado dentro do HashSet.

Já no caso do ArrayList, a documentação diz que a operação add roda em tempo constante amortizado, ou seja, quase um O(1) (faz sentido, pois o elemento é adicionado ao fim da lista). Diz também que outras operações, incluindo o contains, rodam em ordem aproximadamente linear, ou seja, O(n).

Resumindo: teoricamente, no teu teste, é pro tempo do HashSet ser ligeiramente menor que o do ArrayList. A diferença pode ser pouca por conta de 30000 ser um número relativamente pequeno pra tais comparações. Como O(n) lida com casos mais assintóticos, valem testes com mais elementos (300 mil, 3 milhões e por aí vai) e ir vendo como essas diferenças de tempo evoluem.

Espero ter te ajudado. Qualquer coisa, avisa aí.

Abraço.