Bem, estou desenvolvendo um navegador (GUI) com os botões de “primeiro”, “próximo”, “anterior” e “último”.
Qual classe (se existir) da API que possui os métodos necessários para navegação (tipo “first()”, “next()”, “previous()” e “last()”)? :-o
http://java.sun.com/j2se/1.4.2/docs/api/java/util/LinkedList.html
Se for iterar pela lista, faça um favor para sua ram utilizando Iterators, e não um for … size().
[quote=LIPE]
Se for iterar pela lista, faça um favor para sua ram utilizando Iterators, e não um for … size().[/quote]
Há algum artigo que me prove isso?
*não estou duvidando, apenas por aprendizado.
**eu uso for .size() :lol:
valeu! até mais…
Bem, aprendi a razão disso na palestra do Guilherme Silveira :thumbup:
Basicamente cada List provê uma implementação diferente sobre a maneira em que os objetos são guardados.
Por exemplo o ArrayList guarda os objetos dentro de um array comum de objetos. Portanto é muito simples fazer um list.get( 13 ), pois internamente ela fará return array[ 13 ]. Mas se fosse necessário inserir um objeto na posição 0 do array, internamente seria necessário realocar todas as instâncias para numa nova posição.
No caso da LinkedList, a implementação é diferente, fazendo com que seja muito simples inserir um objeto no topo ou no fim, porém, para pegar um objeto numa posição específica é bem mais lento.
Por esse motivo que todas as Collections implementam Iterator. Ao pedir este objeto para a coleção, ela retornara um objeto que sabe a melhor maneira possível para iterar sobre todos os objetos nela contidos.
Para o usuário do Iterator, tanto faz como ele funciona internamente, mas utilizá-lo ao inver do for … size() pode ser crítico ao mudar a implementação da Collection.
Um exemplo:
public void itera( List list )
{
for( int i = 0; i < list.size(); i++ )
System.out,.println( list.get( i ) );
}
public void test()
{
List list = new ArrayList();
for( int i = 0; i < 500000; i++ )
list.add( new Object() );
itera( list );
}
Esse processo ocorreria com uma certa tranquilidade. Mas caso o método test fizesse isto:
public void test()
{
List list = new LinkedList();
for( int i = 0; i < 500000; i++ )
list.add( new Object() );
itera( list );
}
Seu pc iria explodir
Você pode baixar os arquivos da palestra (cujos exemplos acima be baseei completamente) aqui:
http://www.guj.com.br/posts/list/20765.java
unnhh … massa mesmo essas dicas!!!..
estava estudando justamente isso aqui hoje …
Na verdade o LinkedList utiliza o algoritmo de ListaDuplamenteEncadeada,
e só vai ser util caso vc precise acessar , incluir , remover , elementos das pontas , inicio e fim da lista …
Vou dar uma olhada nesse material da palestra!!!
valeu mesmo cara pela dica… estava procurando um material desse…
isso que faz a diferenca em grandes aplicacoes !!! rsrsrs!!!
Essa galera do GUJ bota pra la!!!
rodei ate aqui um exemplo…
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class Class1 {
public Class1() {
}
public static void main(String[] args) {
ArrayList c1 = new ArrayList();
LinkedList c2 = new LinkedList();
for (int i=0; i<1000; i++){
c1.add(new Integer(i));
c2.add(new Integer(i));
}
double l1 = System.currentTimeMillis();
for(int i=0;i<60000;i++){
c1.add(0, new Integer(i)) ;
}
double l2 = System.currentTimeMillis() - l1;
double tempo = l2/1000;
System.out.println("tempo do ArrayList: " + tempo + " s");
l1 = System.currentTimeMillis();
for(int i=0;i<60000;i++){
c2.add(0, new Integer(i)) ;
}
l2 = System.currentTimeMillis() - l1;
tempo = l2/1000;
System.out.println("tempo do LinkedList: " + tempo + " s");
}
}
Saida:
tempo do ArrayList: 7.11 s
tempo do LinkedList: 0.21 s
Eu andei lendo uns artigos no OnJava sobre coleções e os testes feitos mostram que em muito poucos casos a LinkedList é melhor que um ArrayList, inclusive nos casos em a melhora seria esperada. Na dúvida acabei rodando uns testes por conta própria (na 1.4, preciso refazer na 1.5) e confirmei que o desempenho da LinkedList é mesmo inferior ao do ArrayList e mesmo quando é superior a diferença não é significativa.
ahh … de uma pesquisada sobre ListIterator … vc pode navegar pra frente e pra tras…
ArrayList e LinkedList nao sao iguais. Possuem tempos diferentes e algoritmos diferentes.
Exemplo:
Tente adicionar 50000 objetos na posicao zero de uma arraylist. Cronometre o tempo
Faca o mesmo com linkedlist.
Resultado: linked list ganha
Tente fazer um for(int i=0;i<10000;i++) e chamar get(i) em uma linkedlist
Faca o mesmo para uma arraylist
Resultado: array list ganha
Resultado final:
Dependendo do que voce vai fazer a escolha de ArrayList ou LinkedList faz o seu programa funcionar o nao. Como o proprio Lipe comentou, voces podem encontrar o ppt da apresentacao com exemplos muito legais e explicacoes teorias: nao se iludam, a escolha do algoritmo nao eh facil e FAZ TODA A DIFERENCA
Fcmartis, se voce se preocupa com pilha, fila etc, a discussao de arraylist cai como uma luva pois eh quando linkedlist pode ser MILHOES de vezes mais rapido (sem exagero).
Att
Guilherme
[quote=gui][quote=LIPE]
Se for iterar pela lista, faça um favor para sua ram utilizando Iterators, e não um for … size().[/quote]
Há algum artigo que me prove isso?
*não estou duvidando, apenas por aprendizado.
**eu uso for .size() :lol:
valeu! até mais… :D[/quote]
Qualquer livro que ensine lista ligada e arrays, ou curso de analise de algoritmos em faculdade mostra que o tempo esperado de iteracao em:
lista ligada: O(N*N)
arraylist: O(N)
Tem o site do www.ime.usp.br/~pf com informacoes na area
Att
Guilherme Silveira
Nota importante a todos: se você tem um método que roda esporadicamente, fora de um loop, em que você precisa criar uma List e adicionar um punhado de itens, use a primeira implementação que vier à sua cabeça :mrgreen:
Parece brincadeira, mas não é. Não vai fazer como o povo que cria String com StringBuffer (e agora StringBuilder) pra concatenar duas Strings. Legibilidade sempre que possível.
Tudo isso que foi comentado aqui é realmente importante para quando você precisar de performance. Nos outros casos, seja consistente e use sempre a mesma forma de fazer as coisas, até para que alguém no futuro não pare para ler seu código e ache que tem algo relevante naquele método porque usa LinkedList ao invés de ArrayList…
boa Michael,
tentando concatenar com a sua ideia:
Se voce por algum motivo precisa escolher uma implementacao nao comum (como o caso de algoritmos especificos) por causa de performance em um caso especifico, COMENTE ou DOCUMENTE porque voce fez tal escolha…
Abraco
Guilherme
ps: tambem odeio o caso do stringbuffer em metodo bobo