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!
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”) 
[quote=wellington.nogueira][quote=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![/quote]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.[/quote]
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.
[quote=wellington.nogueira]
Porém nem sempre trocar para um Set, que não permite objetos “duplicados”, pode solucionar o problema.[/quote]
Hehe eu não disse para trocar a lista por um Set, disse para usar o método lista.set(index, value) - que é uma operação instantânea - ao invés de remover o elemento e adicionar outro no lugar - o que torna necessário que a lista se reorganize duas vezes apenas para trocar um valor.
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.
[quote=diegohsi][code]
public static void reverse2(Vector 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]);
}
}
[/code]
este executou no intervalo [17, 25]ms.[/quote]
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.
A um tempo atrás apareceu um tópico sobre inverter um vector ( http://www.guj.com.br/java/294926-inverter-um-vector ).
Sugeriram o uso de Collections.reverse(vector);Mas, como isso deve ser um exercício, a resposta correta não deveria ser esta.
Baseado no tópico escrevi o seguinte código:
[code] private static Vector revertUsingGet(Vector 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;
}[/code] porém [b]não[/b] é performático.
A entrada de dados que estou usando é:Vector<Integer> vet = new Vector<Integer>();
for (int i = 0; i < 100000; i++) {
vet.add(i);
} está levando um tempo entre 8 e 9 segundos para resolver. O reverse do Collections leva em torno de 25 milisegundos.
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.
[quote=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![/quote]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.
@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.
[code] 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;[/code]
O trecho abaixo demonstrou-se um pequeno gargalo em comparação com o uso direto do set. vet.clear();
for (Integer integer : vetArray) {
vet.add(integer);
}
[quote=sergiotaborda][code]
public static void reversePolimorfic(List 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]);
}
}
[/code]
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…
[/quote]
Usando o remove do iterator só foi eficiente usando LinkedList. Usando ArrayList ou mesmo Vector, houve perda na performance.
for (Iterator<T> iterator = list.iterator(); iterator.hasNext();) {
T t = iterator.next();
array[--i] = t; // já faz a inversão
iterator.remove();
}