Re:Otimizando código que inverte uma lista/vector

Para inverter um ArrayList ou Vector, que são estruturas de dados de acesso aleatório (ou seja, o tempo para executar get(i) ou set(i) independe do valor de (i)), você pode usar alguma coisa como:

List<Integer> vet = ...;
for (int i = 0, n = vet.size(); i < n / 2; ++i) {
    Integer tmp = vet.get(n - i - 1);
    vet.set (n - i - 1, vet.get (i));
    vet.set (i, tmp);
}

ou coisa parecida (veja se não errei no “- 1”)

wellington.nogueira:

gomesrod:

O algoritmo não tem problemas, só o que está atrapalhando são esses remove e add . Essas são operações custosas em um arraylist porque causam o deslocamento de todos os elementos subsequentes.

Use set para atribuir os elementos diretamente que a diferença no tempo vai ser enorme!

Sim, eu concordo, os removes e adds são problemáticos mas os gets também não são performáticos.
Porém nem sempre trocar para um Set, que não permite objetos “duplicados”, pode solucionar o problema. Já um ArrayList ou Vector (que implementa List) permitem a “duplicidade”. A idéia é manter o uso de Vector ou ArrayList mas oferecer um código otimizado.

No caso de um ArrayList, get(i) e set(i) são encapsulamentos triviais do acesso a arrays, ou seja, é dificil ser mais performático que isso.

Isso depende da implementação da lista. Se for um arraylist ou vector o get é imediato, já em um linked list pode impactar na performance.

wellington.nogueira:

Porém nem sempre trocar para um Set, que não permite objetos “duplicados”, pode solucionar o problema.

Faça o seu teste de performance assim e veja a diferença: private static Vector<Integer> revertUsingGet(Vector<Integer> vet) { for(int j = 0; j < vet.size() / 2; ++j) { Integer first = vet.get(j); int lastIndex = vet.size() - 1 - j; Integer last = vet.get(lastIndex); // vet.remove(j); // vet.add(j, last); // vet.remove(lastIndex); // vet.add(lastIndex, first); vet.set(j, last); vet.set(lastIndex, first); } return vet; }

public static void reverse2(Vector<Integer> v) {
		Integer[] in = new Integer[v.size()];
		in = v.toArray(in);

		v.clear();

		int i = 1;
		while (i <= (in.length / 2)) {
			int firsts = in[i - 1];
			int lasts = in[in.length - i];
			in[i - 1] = lasts;
			in[in.length - i] = firsts;
			i++;
		}
		
		for (int j = 0; j < in.length; j++) {
			v.add(in[j]);
		}
	}

este executou no intervalo [17, 25]ms.

diegohsi:

public static void reverse2(Vector<Integer> v) {
		Integer[] in = new Integer[v.size()];
		in = v.toArray(in);

		v.clear();

		int i = 1;
		while (i <= (in.length / 2)) {
			int firsts = in[i - 1];
			int lasts = in[in.length - i];
			in[i - 1] = lasts;
			in[in.length - i] = firsts;
			i++;
		}
		
		for (int j = 0; j < in.length; j++) {
			v.add(in[j]);
		}
	}

este executou no intervalo [17, 25]ms.

Vai executar ainda mais rápido se não der clear no vetor e retornar um novo vector com a ordem invertida.
O clear é necessário se usarmos interfaces como entrada como faz o Collections, mas no caso que sabemos a instancia, não ha necessidade.
Outro ponto é que Vector tem todos os seus métodos sincronizados, logo, usar array puro é mais rápido que get/set. (embora a jvm modernas quase removam esse sincronismo)

Para quem quer inverter qualquer list o algortimo tem que ser mais esperto. Ele deve checar se o objeto implementa RandomAccess para saber se pode usar get/set com velocidade aceitável. LinkedList, por exemplo não implementa isto.
Mas ela implementa algo melhor : iterador reverso. Portanto, para linked list poderiamos usar o iterador reverso e preencher uma nova lista.
Mas por causa do polimormismo a melhor opção ainda é usar um array.
assim

public static void reversePolimorfic(List<T> list) {


		Object[] array = new Object[list.size()];
                int i = list.size();
                for (T t : list ){
                      array [--i] = t; // já faz a inversão
               }                

		list.clear();

		for (int j = 0; j < array.length; j++) {
			list.add((T) array[j]);
		}
	}

Este algoritmo faz 1 laço a menos que o anterior. Poderiamos fazer dois laços a menos usando iterator no primeiro laço e invocando remove. Isso já faria o clear enquanto inverte. Só não sei se isso afetaria a performance pois não sei se o arraylist iria reagir com cóipas do array interno (acho que não). Estas seriam algumas alterações que poderiam tentar...

Se não tiver que retornar o mesmo objeto que entrou, uma alternativa é retornar um proxy que faça a lista parecer invertida.

Eu tinha pensando nesta ideia, mas só funcionaria se o objeto implementar RandomAccess. Para LinkedList seria o caos.
claro que estou imaginando simplesmente fazer uma conta que quando o cara pedir get(i) por baixo dos panos faz get(this.length - 1 - i)

Se fosse só o iterator seria mais simples, pois o linkedlist já tem um iterador invertido, mas ai teriamos que gazer o get(i) usar o iterador, o que não parece correto…

No fingir dos ovos não sei se a ideia do proxy realmente funcionaria a contento. Embora seja a mais elegante.

Collections.reverse(vector);

private static Vector<Integer> revertUsingGet(Vector<Integer> vet) {
		for(int j = 0; j < vet.size() / 2; ++j) {
			Integer first = vet.get(j);
			int lastIndex = vet.size() - 1 - j;
			Integer last = vet.get(lastIndex);
			vet.remove(j);
			vet.add(j, last);
			vet.remove(lastIndex);
			vet.add(lastIndex, first);
			
		}
		return vet;
	}

Vector<Integer> vet = new Vector<Integer>();
		for (int i = 0; i < 100000; i++) {
			vet.add(i);
		}

Gostaria de ver o mesmo resultado, porém otimizado (algo mais próximo ao reverse da classe Collections).

PS:
1- Eu já fiz minha otimização mas não vou postar para não influenciar a decisão de ninguém ;)
2- Use valores menores na entrada (ex.: 10 ao invés de 100000) para facilitar testes.
3- Usei vector pois era a classe utilizada, mas poderia ser um ArrayList.

gomesrod:

O algoritmo não tem problemas, só o que está atrapalhando são esses remove e add . Essas são operações custosas em um arraylist porque causam o deslocamento de todos os elementos subsequentes.

Use set para atribuir os elementos diretamente que a diferença no tempo vai ser enorme!

@gomesrod eu tinha entendido errado o que você disse.

Realmente, o método set oferece a velocidade necessária (as vezes me esqueço de alguns métodos como esse devido a rotina de usar add/remove) hehe

Como não me lembrava desse método, usei um outro caminho que mostrou-se quase tão bom quanto o uso do método set que foi alterar diretamente o array e realimentá-lo na lista.

Integer[] vetArray = new Integer[vet.size()];
		vet.toArray(vetArray);
		
		int size = vet.size();
		int midPoint = size / 2;
		for(int j = 0; j < midPoint; ++j) {
			Integer first = vetArray[j];
			int lastIndex = size - 1 - j;
			Integer last = vetArray[lastIndex];
			vetArray[j] = last;
			vetArray[lastIndex] = first;
		}
		
		vet.clear();
		for (Integer integer : vetArray) {
			vet.add(integer);
		}
		
		return vet;

vet.clear();
		for (Integer integer : vetArray) {
			vet.add(integer);
		}

sergiotaborda:

public static void reversePolimorfic(List<T> list) {


		Object[] array = new Object[list.size()];
                int i = list.size();
                for (T t : list ){
                      array [--i] = t; // já faz a inversão
               }                

		list.clear();

		for (int j = 0; j < array.length; j++) {
			list.add((T) array[j]);
		}
	}

Este algoritmo faz 1 laço a menos que o anterior. Poderiamos fazer dois laços a menos usando iterator no primeiro laço e invocando remove. Isso já faria o clear enquanto inverte. Só não sei se isso afetaria a performance pois não sei se o arraylist iria reagir com cóipas do array interno (acho que não). Estas seriam algumas alterações que poderiam tentar...

for (Iterator<T> iterator = list.iterator(); iterator.hasNext();) {
				T t = iterator.next();
				array[--i] = t; // já faz a inversão
				iterator.remove();
			}