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

Programação Java
#1

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));
	}
}
#2

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!

#3

É 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.

#4

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)

#5

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.

#6

[quote=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.[/quote]

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… :slight_smile:

#7

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

#8