Collection

This message was edited 1 time. Last update was at 06/02/2012 13:06:51

ViniGodoy wrote:A remoção durante a iteração também costuma a ser mais rápida no LinkedList.

Nesse caso aqui eu diria muito melhor porque vc nunca paga o preco do SHIFT do ArrayList. Era o meu ponto. Remocao numa LinkedList é mais rápida do que numa ArrayList.

O problema não é a remocao em si, mas ter que encontrar o objeto a ser removido dentro da lista, linearmente, via iteracao.

O fato de eu usar minha própria linkedlist onde os objetos que eu coloco dentro dela SÃO um entry dessa lista, me livra desse problema. Só que para uma java.util.LinkedList que precisa aceitar objetos quaisquer, não há como escapar desse custo de encontrá-los quand se quer removê-los. A não ser que como vc mencionou muito bem, vc já tenha que iterar sobre eles de qualquer jeito...

GUJ Expert Membro desde: 22/03/2005 20:57:48 Mensagens: 3433 Offline

nel wrote:Dá uma lida aqui, faz o favor: http://www.guj.com.br/java/71065-qual-a-diferenca-entre-linkedlist-arraylist-e-vector

Não sou eu quem precisa rever os conceitos nesse caso. O LinkedList só é muito bom para remover o primeiro e último item da lista, não os seus "interiores", porque tem métodos como o removeLast()

Dá uma lida no link que lhe passei e por favor, pesquisa na net e veja a opinião da maioria se eles usam LinkedList quando querem remover objetos do array.
Edit: não só remover mas como manipular um objeto do interior da lista.

Quando você fala que o LinkedList é mais lento em insersão e remoção porque tem que iterar todos os itens vc está falando de remoção e inserção por índice. É preciso que vc diga isto, porque nesse caso sim é mais lento, mas essa utilização não existe na prática.
É extremamente raro que alguém faça remove(i) em listas. Agora,se vc considerar o caso mais comum que é remover durante a iteração com iterator.remove() o linkedlist é mais rápido. Pq ? porque não tem que redimencional o array subjacente à lista porque não ha nenhum.

No mundo das listas ha duas formas de uso, por indice e por iterator. Fazer um for com i e percorrer de X a Y ok. Mas isso é muiiiiittttoooo raro. Normalmente vc quer iterar todos os elementos da lista. Então vc usa iterator ou for extendido.
Ora, usando com índice qualquer classe que implemente RandomAcess será melhor. Logo, ArrayList é melhor quando se usa get(i). Mas no caso padrão em que se usa iterator ambas têm o mesmo resultado. Isto se vc apenas iterar.
Se vc iterar e remover itens enquanto iterar usar ge(i) remove(i) é extremamente falho e usar iterator.remove é muito simples. Logo, vc usa iterator.remove. iterator.remove é mais rápido no linkedlist. E quando digo rápido me refiro a que é O(1) e não O(n).

Quando estamos falando de inserção linkedlist tb é melhor. Isto pq o arraylist tem um custo exponencial quando se incluem itens além do tamanho reservado.

Quando usar um ArrayList ? Apenas quando o tamanho é pre-conhecido , fixo e a iteração não irá invocar iterator.remove.
Quando usar LinkedList ? Quando o tamanho não é conhecido, não é fixo ou a iteração irá invocar iterator.remove.

Quando vc cria um ArrayList sempre passe no construtor o tamanho. Se vc não consegue saber qual o tamanho, então isso significa que 1) vc não leu o codigo com atenção ou 2) deveria usar um linkedlist.

Pense agora na situação em que vc tem uma lista A e quer produzir uma lista B só que alguns elementos de A não estarão em B. Vc cria um for em cima de A e copia para B apenas os elementos que passam no if do filtro.
Ok, mas que tipo de lista será B ?
Podemos dizer que sabemos o tamanho de B ? Não. Mas sabemos que será igual ou menor que o de A. Se criarmos um ArrayLsit nos arriscamos a ficar com um array de varias posições vazias. Então a solução é usar um linkedlist.

O linkedList é em geral mais lento que o arraylist quando se usa get(i), excepto quando i= 0 ou i= ultimo elemento.É que o linkedlist é na realidade duplamente linkado. Por causa disto, os metodos get/removeFist e get/removeLast existe no linkedList.
E com eles é possivel criar queues (filas). Arualmente LinkedList tb implement Queue e DeQueue. É a coleção mais versátil que existe.

Em programas reais é incomum que as pessoas usem LinkedList. isto porque elas não sabem usar. Então ArrayList é pau para toda a obra. Ora, de fato, a interface list não deveria ser usada em sistemas reais porque usar get(i) é horrivel.
Contudo em java List tem um significado semântico : elementos repetidos e em ordem. Por causa da semantica sofre o design.
O mais correto é sempre usar Collection (seguindo a regra de : use a interface mais abstrata possivel). Assim vc força todos a usar iterator que é o certo. A coleção pode ter repetidos e estar em uma ordem. Se não estiver use Set.
Desta forma vc elimina o uso de List e por consequência impede que se use get(i). Neste cenário é mais simples escolher as listas, mas ArrayList é normalmente usado porque normalmente a lista tem tamanho fixo e conhecido. Mas , por exemplo, quando vc lê de um ResultSet JDBC quando usar ? LinkedList ( porque mesmo o tamanho sendo fixo, vc não sabe qual é).

Para resolve o dilema várias bibliotecas de collections com o Apache Collections ou o Guava adotam o conceito de Bag. Bag é como uma lista, ou seja permite repetidos e uma certa ordem, mas não permite indexação. Se vc não gostar de usar apenas Collection e Set existe sempre a opção de criar a interface Bag e usá-la nos seus sistemas.

Outro problema que leva ao uso indevido de List são as tags core do jsp que só aceita list. Isto é muito limitativo e acaba forçando que seus business/services/daos retornam List.
A solução aqui é construir sua biblioteca de tags de forma a usar iterator e não get(i) como as tags jsp padrão.

Espero ter ajudado a esclarecer. A discussão toda foi porque uns estavam falando de velocidade de indexação e outros de velocidade em iteração. São coisas diferentes. Mas em sistemas reais a velocidade de indexação é práticamente irrelevante porque se usa muito pouco for com get(i) porque é um anti-pattern.

This message was edited 6 times. Last update was at 07/02/2012 10:42:43

Acho que o problema aí é que mesmo que eu já tenha o objeto a ser removido, eu não tenho como removê-lo sem percorrer a lista inteira atrás dele. Concorda? Seja via remove(indice) ou via remove(object).

E numa linked list, que na verdade é uma double-linked list, tendo algum node da lista fica muito fácil remove-lo. Basta atualizar os ponteiros (node.prev and node.next). Mas no java.util.LinkedList, eu não tenho acesso ao objeto Node, logo tenho que loopar atrás dele.

Mas , por exemplo, quando vc lê de um ResultSet JDBC quando usar ? LinkedList ( porque mesmo o tamanho sendo fixo, vc não sabe qual é).

Foi o que eu falei inicialmente: se vc não sabe quantos elementos vc vai ter que colocar na sua lista, só dá pra ir de LinkedList. Agora se vc sabe de antimão o tamanho (máximo) da sua lista (veja que tamanho != capacidade), então vc pode ir de ArrayList sem problemas. O que o cara pode fazer é pegar um tamanho máximo bem grande para nunca estourar o ArrayList, mas ir de LinkedList nesses casos me parece mais correto, a não ser que vc realmente precisa de indexação no resultado retornado. Quando vc precisa de indexação, só se pode ir de ArrayList.

Então repetindo a minha frase inicial: "Como regra eu só uso ArrayList quando preciso de INDEXAÇÃO ( list.get(3) ) ou QUANDO O TAMANHO DA MINHA LISTA É CONHECIDO NA HORA DA CRIAÇÃO."

Agora se vc precisa de REMOÇÃO de qualquer objeto aleatório da lista (não é o caso de quando vc está iterando), então nem o ArrayList e nem o LinkedList vão prestar. Eu implemento minha própria linked list e faço meus objetos extenderem Node (nao ideal mas funciona que é uma beleza). Fiquei agora curioso para saber qual é a solução padrão que o Java oferece nesse caso, ou seja, qual é a solucao padrão que o Java oferece para linked lists onde eu possa remover qualquer elemento de forma rápida via um list.remove(elemento).

JWizard Membro desde: 01/10/2009 13:51:10 Mensagens: 2364 Offline

Essas são questão que me afligem, na verdade.

Eu trabalho com JEE, pois meu foco são sistemas WEB. Isso envolve EJB e bla bla bla. Ok. Me expressei mal e acabei gerando discussão com o saoj sendo que percebo que ambos estavam discutindo pontos de vista um pouco diferentes. O meu problema nisso, é que grande parte das listas que crio são enviadas para a página, ou seja, existe uma tabela de objetos em que o usuário final pode simplesmente "brincar" nela. Pode remover a posição, 10, 10, 1000 ou qualquer uma. Por conhecer que o LinkedList é mais lento para remoções por índice (get(i)) procuro usar o ArrayList, todavia, em listas que não há a participação direta do usuário final, uso o LinkedList.

sergiotaborda wrote:Mas em sistemas reais a velocidade de indexação é práticamente irrelevante porque se usa muito pouco for com get(i) porque é um anti-pattern.

Se é um anti-pattern, qual seria a solução ideal? Ou a mais correta para uma situação como citei? Acredito que o iterator e um equals não seja, até porque, eu teria de sobrescrever o equals() no meu objeto (não estou dizendo que isso é um problema!) para que o mesmo faça a forma correta. Digo pois, 99% do casos, sei o índice que o usuário final selecionou lá na página web e o mesmo é enviado para lado do servidor, onde simplesmente, aplico o remove(i). Quando pode enviar uma lista para o lado servidor, bom, ai eu simplesmente itero sobre ele. Para finalizar e seria opinião de todos, o meu costume é foreach e não iterator, em tudo, incluindo remove (menos quando tenho de remover um objeto da própria lista, obviamente). Estou fazendo bobagem? Ou o iterator só terá uma diferença significativa em relação ao remove?

Abraços a todos.

GUJ Expert Membro desde: 22/03/2005 20:57:48 Mensagens: 3433 Offline

nel wrote:Essas são questão que me afligem, na verdade.

Eu trabalho com JEE, pois meu foco são sistemas WEB. Isso envolve EJB e bla bla bla. Ok. Me expressei mal e acabei gerando discussão com o saoj sendo que percebo que ambos estavam discutindo pontos de vista um pouco diferentes. O meu problema nisso, é que grande parte das listas que crio são enviadas para a página, ou seja, existe uma tabela de objetos em que o usuário final pode simplesmente "brincar" nela. Pode remover a posição, 10, 10, 1000 ou qualquer uma. Por conhecer que o LinkedList é mais lento para remoções por índice (get(i)) procuro usar o ArrayList, todavia, em listas que não há a participação direta do usuário final, uso o LinkedList.

Este mecanismo é um pouco estranho. Vc usa o numero da linha da tabela para corresponder com a lista do lado do servidor. Normalmente se requer que os objetos tenham alguma identidade que os distingua uns dos outros, como um id de banco. E é o id e não o indice que é passado ao servidor.
Veja que para a remoção de um único objeto não é certo qual é melhor. O linkedlist é O(i) e o arraylist é O(n-i) já que o primeiro tem que iterar i vezes , mas a remoção é O(1) e o segundo encontrar o item é O(1) , mas tem que fazer o shift que é O(n-i) (não tenho a certeza deste aqui por não sei exactamente qual é a performance do System.arraycopy)

sergiotaborda wrote:Mas em sistemas reais a velocidade de indexação é práticamente irrelevante porque se usa muito pouco for com get(i) porque é um anti-pattern.

Se é um anti-pattern, qual seria a solução ideal? Ou a mais correta para uma situação como citei?

É dificil dizer sem saber o que vc está fazendo, mas eu nunca tinha visto essa forma de trabalhar antes.
Normalmente se usa um mecanismo de filtro ( como o que vai ser incorporado no java 8 para todas as classes de coleção). A ideia é ter uma interface Filter com um método que retorna booleano.
Ai iteramos a lista, se o filtro acusa false, removemos o item com iterator.remove
Como o Filter é uma classe podemos implementar como quisermos. Normalmente se comparar o código ou se usa o equals. Mas nunca o index porque esta é uma tecnica genérica aplicável a qualquer Iterable cujo iterador permita remoção.

Se vc tem esse caso de uso que usa o index e realmente vc vê isso como a forma certa, então realmente usar remove(i) é a melhor opção , no seu caso.

(...), o meu costume é foreach e não iterator, em tudo, incluindo remove (menos quando tenho de remover um objeto da própria lista, obviamente). Estou fazendo bobagem? Ou o iterator só terá uma diferença significativa em relação ao remove?

Atualmente (java 5 em diante) foreach é a forma certa de iterar. Nada de while nem for com iterator. A única exceção, vc está certo, é quando vc quer usar o iterator.remove.

Respondendo ao saoj , eu não costumo usar remove nunca nos meus projetos. É muito raro. mas quando preciso normalmente está envolvido algum processo iterativo ( como copiar ou filtrar uma lista). E nesse caso sempre uso iterator.remove. Não tenho que implementar nenhum objeto novo.
Quando quero trabalhar como algoritmos mais complexo normalmente uso Map. Em que a chave do mapa é o objeto que irá servir para encontra o outro. E ai usar remove(key) é rápido no HashMap. Se o objeto é a sua ppr chave , uso Set. O set usa um map por detrás dos panos, então dá no mesmo. Por outro lado, se vc está interessado em remover algo, normalmente não trabalha com repetidos e o Set é mais eficiente.

Remove diretamente de listas, realmente não posso opinar muito porque não uso. E não vejo necessidade.

This message was edited 2 times. Last update was at 08/02/2012 14:16:22

Remove diretamente de listas, realmente não posso opinar muito porque não uso. E não vejo necessidade.

Boa resposta. Concordo com o que vc falou sobre usar a chave primária do objeto ao invés do índice na lista.

Sobre a necessidade de remover, me recomendaram o LinkedHashSet ou o LinkedHashMultiset do Guava se eu precisar de objetos duplicados na lista.

Excluindo o problema dos objetos duplicados, realmente o que eu queria parece ser um SET ordenado por insercão, ou seja, um SET com uma lista encadeada internamente para manter a ordem. Daí obviamente quando vc remove do set ele vai direto nos ponteiros do elemento e remove ele da lista interna tb. Sem ser louco de loopar...

JWizard Membro desde: 01/10/2009 13:51:10 Mensagens: 2364 Offline

Entendo.

Basicamente, as tecnologias WEB permitem que eu trabalhe diretamente com o objeto retornado pelo lado servidor. Há poucas situações em que uso o índice para remover apenas da lista, get(i), pois 90% (senão mais) envio diretamente o objeto ao lado servidor, ao menos, o seu respectivo ID. Normalmente, essas listas representam dados populados diretamente no banco, portanto, removeu da lista, remove-se do banco e não trabalha com o remove(i).

A dúvida foi ali pois se encaixava ainda nos 10%. De qualquer forma, vou começar a reavaliar o código que ainda usa o índice e se realmente é necessário.
Grato por todas as opiniões e esclarecimentos.

nel wrote:Entendo.

Basicamente, as tecnologias WEB permitem que eu trabalhe diretamente com o objeto retornado pelo lado servidor. Há poucas situações em que uso o índice para remover apenas da lista, get(i), pois 90% (senão mais) envio diretamente o objeto ao lado servidor, ao menos, o seu respectivo ID. Normalmente, essas listas representam dados populados diretamente no banco, portanto, removeu da lista, remove-se do banco e não trabalha com o remove(i).

A dúvida foi ali pois se encaixava ainda nos 10%. De qualquer forma, vou começar a reavaliar o código que ainda usa o índice e se realmente é necessário.
Grato por todas as opiniões e esclarecimentos.

O que vc pode fazer é:

Ao invés de ter um ArrayList por índice, vc pode ter um LinkedHashMap por *id do banco*. Acho que dá no mesmo mas fica mais organizado e com uma performance melhor. Claro que essa diferenca de performance vai ser totalmente irrelevante para a sua aplicacao, mas acho que fica mais consistente usar id do banco em tudo. Mas isso é um chute sem conhecer muito bem o seu caso específico.

Notícias, artigos e o maior fórum brasileiro sobre Java