Qual das estrutudas (int[] e List) apresenta melhor desempenho

26 de julho de 2006 6 respostas

wilsonjsp 26 de julho de 2006

boa noite a todos…

alguém sabe quais das estruturas ( int[] ou List ) têm melhor desempenho, considerando que seja preciso fazer: inicializacao, atribuição de um valor aleatório, e atualização de um valor em uma posição aleatório.

eu fiz o teste abaixo e em todos os caso o int[] teve um melhor desempenho, isso é verdade mesmo ou tem algo que deve ser considerado a mais? e em termos de memória o int[] é melhor também?

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;

public class teste {
	public static void main(String[] args) {
		SimpleDateFormat formata = new SimpleDateFormat("hh:mm:ss"); 
		Date tempo = new Date();
	
		long inicioDoProcessamento;
		long fimDoProcessamento;
		
		long inicioDoProcessamentoDosTresTeste;
		
		int valorAleatorio;
		Object object;
		
		int[] arg = new int [1000000];
		List list = new ArrayList(1);
		System.out.println("------------------------------Teste int[ ]-------------------------\n");
		
		//Inicio do teste int[]
		tempo= new Date();
		inicioDoProcessamentoDosTresTeste = tempo.getTime();
		
		//teste de inicializacao do int[]
		tempo= new Date();
		inicioDoProcessamento = tempo.getTime();
		
		System.out.println("Teste 1: Inicializacao da estrutura: \n-------");
		System.out.println("Começando...: "+formata.format(tempo));
		for (int i = 0; i < arg.length; i++) 
			arg[i] = 0; 
		
		tempo= new Date();
		fimDoProcessamento = tempo.getTime();
		
		System.out.println("Terminou....: "+formata.format(tempo));
		System.out.println("Tempo gasto para do Teste 1 (UM): "+(fimDoProcessamento - inicioDoProcessamento)+"\n");
	
		//teste de Atribuicao de um valor aleatorio no Int[]
		//As duas estruturas geram um inteiro aleatorio e um Object
		tempo= new Date();
		inicioDoProcessamento = tempo.getTime();
		
		System.out.println("Teste 2: Atribuicao de um valor aleatorio: \n-------");
		System.out.println("Começando...: "+formata.format(tempo));
		for (int i = 0; i < arg.length; i++) {
			valorAleatorio=(int) (Math.random()*1000);
			object =new Object();
			arg[i] = valorAleatorio; 		
		}
		tempo= new Date();
		fimDoProcessamento = tempo.getTime();
		System.out.println("Terminou....: "+formata.format(tempo));
		System.out.println("Tempo gasto para o Teste 2(DOIS): "+(fimDoProcessamento - inicioDoProcessamento)+"\n");

		//teste de atualizacao de um  valor de uma posicao aleatorio do Int[]
		tempo= new Date();
		inicioDoProcessamento = tempo.getTime();
		
		System.out.println("Teste 3: Atualizacao de um valor de uma posicao aleatorio: \n-------");
		System.out.println("Começando...: "+formata.format(tempo));
		for (int i = 0; i < arg.length; i++) {
			valorAleatorio=(int) (Math.random()*1000);
			arg[valorAleatorio] = -1; 
		}
		tempo=new Date();
		fimDoProcessamento = tempo.getTime();
		
		System.out.println("Terminou....: "+formata.format(tempo));
		
		System.out.println("Tempo gasto para o Teste 3(TRES): "+(fimDoProcessamento - inicioDoProcessamento));
		System.out.println("\n\nTempo para os 3(três) Teste: "+ (fimDoProcessamento-inicioDoProcessamentoDosTresTeste));
		System.out.println("\n\n------------------------------Teste List-------------------------\n");			

		//Inicio do teste da List
		tempo= new Date();
		inicioDoProcessamentoDosTresTeste = tempo.getTime();
		
		
		//teste de inicializacao da List
		tempo= new Date();
		inicioDoProcessamento = tempo.getTime();
		
		System.out.println("Teste 1: Inicializacao da estrutura: \n-------");
		System.out.println("Começando...: "+formata.format(tempo));
		for (int i = 0; i < arg.length; i++) 
			list.add(""); 
		
		
		tempo= new Date();
		fimDoProcessamento = tempo.getTime();
		System.out.println("Terminou....: "+formata.format(tempo));
		System.out.println("Tempo gasto para do Teste 1(UM): "+(fimDoProcessamento - inicioDoProcessamento));		
		
		//teste de Atribuicao de um valor aleatorio na List
		//As duas estruturas geram um inteiro aleatorio e um Object
		tempo= new Date();
		inicioDoProcessamento = tempo.getTime();
		
		System.out.println("\nTeste 2: Atribuicao de um valor aleatorio: \n-------");
		System.out.println("Começando...: "+formata.format(tempo));
		for (int i = 0; i < arg.length; i++) {
			valorAleatorio=(int) (Math.random()*1000);
			object =new Object();
			list.set(valorAleatorio,object); 
		}		
		tempo= new Date();
		fimDoProcessamento = tempo.getTime();
		System.out.println("Terminou....: "+formata.format(tempo));
		System.out.println("Tempo gasto para o Teste 2(DOIS): "+(fimDoProcessamento - inicioDoProcessamento));

		//teste de atualizacao de um  valor de uma posicao aleatorio da List
		tempo= new Date();
		inicioDoProcessamento = tempo.getTime();
		
		System.out.println("Teste 3: Atualizacao de um valor de uma posicao aleatorio: \n-------");
		System.out.println("Começando...: "+formata.format(tempo));
		for (int i = 0; i < arg.length; i++) {
			valorAleatorio=(int) (Math.random()*1000);
			list.set(valorAleatorio,"A"); 	
		}		
		tempo= new Date();
		fimDoProcessamento = tempo.getTime();
		
		System.out.println("\nTerminou....: "+formata.format(tempo));	
		System.out.println("Tempo gasto para o Teste 3(TRES): "+(fimDoProcessamento - inicioDoProcessamento));
		System.out.println("\nTempo para os 3(três) Teste: "+ (fimDoProcessamento-inicioDoProcessamentoDosTresTeste));
	}
}

6 Respostas

cassio 26 de jul. de 2006

Um array simples (o seu int[], por exemplo) é sempre mais rápido do que uma estrutura de dados complexa como uma List. A diferença está no fato de que a List pode crescer/decrescer dianâmicamente, enquanto que o array tem um tamanho fixo: uma vez definido este tamanho, para alterá-lo só mesmo redeclarando o array, o que perderia os dados já guardados…

Quanto à memória, acredito que o int[] ocupa menos memória que o List, pois tem uma estrutura mais simples.

Abraço!

Fox_McCloud 26 de jul. de 2006

É isso aí. Pra ajudar a pensar, veja que o objeto List usa vetores internamente, então é como se fosse uma forma indireta de usar vetores sem se preocupar com quanto espaço alocar ou como adicionar mais nós…

Claro que a pessoa que tentar implementar uma lista encadeada usando vetores poderá descobrir que o objeto List fornecido no SDK tem melhor desempenho, uma vez que os algoritmos que utilizam os vetores internamente são otimizados ao máximo.

takeshi10 26 de jul. de 2006

mas para uso geral (sem contar a conversao de int p/ Integer e vice versa), o desempenho de se pegar e colocar items eh mais ou menos igual (exceto nos casos em que um aumento no tamanho do vetor eh necessario)

ZehOliveira 26 de jul. de 2006

Uma ArrayList tem o mesmo desempenho que um array normal, isso é óbvio, um ArrayList nada mais é do que um array encapsulado usando a interface List.

Não dá pra comparar array (int[]) e List já que List é apenas um conceito, não uma implementação. A eficiência depende da forma de implementação (usando array, lista encadeada etc.). Por exemplo, retirar um elemento no meio de uma lista de 1000 objetos é muito mais rápido em uma LinkedList do que em um array ou em uma ArrayList.

Tudo depende da operação que você deseja fazer. Para obter o máximo de eficiência é bom estudar estruturas de dados e ver em quais os casos elas ajudam e quais é melhor escolher outra. Não há uma única estrutura de dados eficiente para todos os casos.

akumaldo 26 de jul. de 2006

ZehOliveira:
Uma ArrayList tem o mesmo desempenho que um array normal, isso é óbvio, um ArrayList nada mais é do que um array encapsulado usando a interface List.

Não dá pra comparar array (int[]) e List já que List é apenas um conceito, não uma implementação. A eficiência depende da forma de implementação (usando array, lista encadeada etc.). Por exemplo, retirar um elemento no meio de uma lista de 1000 objetos é muito mais rápido em uma LinkedList do que em um array ou em uma ArrayList.

Tudo depende da operação que você deseja fazer. Para obter o máximo de eficiência é bom estudar estruturas de dados e ver em quais os casos elas ajudam e quais é melhor escolher outra. Não há uma única estrutura de dados eficiente para todos os casos.

Exatamente…concordo!
tudo depende de quais operações você vai ter que executar nessa sua List…dependendo nem vale a pena mesmo! mas tem oras que precisamos de Collections mais robustas…ou mesmo uma simples array já resolve o problema…

Guilherme_Silveira 26 de jul. de 2006

Completando o que o Ze Oliveira respondeu…

Lembrem-se que a analise de uma estrutura pode ser feita atraves de um benchmark simples e possivelmente irreal (como o dado), ou atraves da analise assintotica do que voce deseja fazer.

Uma arraylist e uma array vai ter O MESMO DESEMPENHO, exatamente igual, em sua analise assintotica em todos os comportamentos.

Ja uma linkedlist e uma array vao ter desempenhos COMPLETAMENTE diferentes dependendo do caso.

Abraco

Guilherme

Criado 26 de julho de 2006

Ultima resposta 26 de jul. de 2006

Respostas 6

Participantes 7

6 Respostas

Topicos relacionados