( Draft 2 )Programe voltado a interface, não a implementação

GUJ Master Membro desde: 23/01/2008 11:14:35 Mensagens: 1905 Offline

aleck wrote:

sergiotaborda wrote:
E como eu disse, performance não se mede em milisegundos.

Fale isto quando os usuários reclamarem que o sistema está demorando a responder.

Muito interessante o estudo: http://www.precisejava.com/javaperf/j2se/Collections.htm

Iterating collection:

Iterating collection using all three types of classes ,ArrayList ,Vector and LinkedList gives similar performance because they need not do any extra work they simply iterate one by one. You can use any Iterator . But using ListIterator gives more flexibility than Iterator and Enumeration. You can traverse both sides

This message was edited 1 time. Last update was at 30/07/2009 16:24:30

sergiotaborda wrote:
Ou seja, para add(object) LinkedList é sempre mais eficiente.

Hein? Parece ate que voce nao esta lendo meus comentarios. Se os dois sao tempo constante (amortizado), a eficiencia computacional é a mesma!! Se voce for medir em milisegundos, a ArrayList ganha em todos os casos (relembrando: metodo add adicionando no final). Voce pode rodar os tests por si mesmo (voce rodou?), ou ver inumeros que tem na internet se nao esta convencido:
http://onjava.com/pub/a/onjava/2001/05/30/optimization.html

sergiotaborda wrote:
Só para completar :

LinkedList, however, is guaranteed to be O(1) for adds and something similarly small for inserts (maybe O(log n)?).
(in http://joust.kano.net/weblog/archives/000066.html)

Esse link que voce citou, o autor mostra que nao conhece muito de analise de algoritmos, pois small inserts na LinkedList tambem é O(1) (e sob hipotese alguma O(logn) como ele chuta e todos nos sabemos que nao é assim). Lista ligada clássica com inserções de O(logn)...? Nao preciso nem falar nada... Cuidado ao ler qualquer coisa por aí.

sergiotaborda wrote:
ArrayList é mais rápido (para poucos elementos) , mas não tem melhor performance. (Se ArrayList fosse melhor que LinkedList sempre, LinkedList seria inutil)

De novo: nao! Sou um cara que gosta bastante teoria, e sei que o tempo cronometrado nao é só o que import, mas aqui nos dois critério ArrayList ou ganha ou empata! Então o que é "nao tem melhor perfomance"? Qual é a sua diferenca para mais rapido e melhor performance? Computacionalmente falando, os dois sao empatados (pela analise do algoritmo, os dois sao O(1) para 1 elemento, amortizado, que é o que vale no fim das contas). Por tempo de relogio, a ArrayList ganha sempre para uma quantidade razoavel de elementos (e acima disso, como no link que passei). Entao nao entendo a insistencia na frase "arraylist nao tem melhor performance" (tem melhor performance em tempo, e a mesma computacionalmente, para o metodo add.

Sobre a inutilidade de LinkedLIst, estamos aqui falando apenas do metodo add, que adiciona no final. LinkedList tem sua utilidade para adicionar no inicio, remover do inicio, e poderia ter para remover/adicionar no meio se voce pudesse manter referencia para os Nodes internos (como ocorre para o .remove() dentro do iterator de LinkedList, que roda em O(1), e na ArrayList em O(n)).

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

Paulo Silveira wrote:

sergiotaborda wrote:
Ou seja, para add(object) LinkedList é sempre mais eficiente.

Hein? Parece ate que voce nao esta lendo meus comentarios. Se os dois sao tempo constante (amortizado), a eficiencia computacional é a mesma!!

Só que não são os dois. Apenas o arraylist é amortizado.

sergio, naquele link que vc passou o cara só fala asneira... alem do fato de um linkedlist nao ter nada de logn, ele anda fala:

Ultimately, the average cost of adding to an ArrayList, as Sun states, is O(n).

o custo MEDIO é O(N)? mto pelo contrario, o custo medio é O(1), amortizado.
o que acontece é que alguma determinada insercao vai ter custo N, mas nao o custo medio de todas as insercoes.

como o paulo falou, é preciso separar a eficiencia computacional dos benchmarks por ai.
nos benchmarks, apos tudo que falaram, espero que ja esteja convencido de que o arraylist eh mais rapido no add.

agora computacionalmente falando, é preciso entender direito o que significa custo amortizado para se entender pq ArrayList#add é O(1) e LinkedList#add tambem é O(1).

o detalhe do arraylist é que ele demora 1 passo para adicionar N-1 elementos. ao adicionar o N-esimo ai sim vamos ter um add que demora N passos. mas como o paulo falou, o crescimento do espaco do arraylist eh exponencial, o q faz com que aquele custo de N passos na N-enesima adicao seja amortizado nas N insercoes. isso faz com que o custo amortizado do add no fim seja O(1), mesmo que algumas insercoes demorem N passos

ou seja, computacionalmente eh o mesmo custo que o linkedlist e na pratica eh mais rapido mesmo

This message was edited 1 time. Last update was at 30/07/2009 16:55:51

Sergio Lopes wrote:
ou seja, computacionalmente eh o mesmo custo que o linkedlist e na pratica eh mais rapido mesmo

pois é, ja falei O(n) vezes isso nessa thread

, mas...

Taborda, consulte o Introduction to Algorithms (aka CLR/CLRS), do Cormen e galerinha do MIT, e la voce vai ver que o tempo é o mesmo, e que a linkedlist nao ganha, diferente do que voce afirmou todas as vezes aqui. So nao vale citar quem fala que insercao em linked list classica é O(logn)....

GUJ Master Membro desde: 23/01/2008 11:14:35 Mensagens: 1905 Offline

é.

Ao executar este programa, o resultado deve ser algo parecido com isto:

Resultado tempo gasto ArrayList = 4859

Resultado tempo gasto LinkedList = 125

This message was edited 1 time. Last update was at 30/07/2009 18:08:42

Sim duran, como todos falaram aqui, e ninguem discordou, a LinkedList é bem mair rapida que a ArrayList para se adicionar no comeco. Ela é O(1), e a ArrayList é O(n) (poderia ser O(1) se tivessem implementado como lista circular, uma pena). Se voce dobrar o tamanho do seu teste, vera que essa diferenca nao ficara so de 40x mais lenta, vai ficar por volta de 80x mais lenta, 160x mais lenta, etc... uma relacao quadratica.

Alias, o que voce fez é um exercicio do nosso FJ11, mostramos isso pros alunos, desde o basico, pra saber que decidir a implementacao pode impactar bastante numa decisao

Ou seja sergiotaborda está claramente errado.
Pode admitir. Errar é humano, não precisa se envergonhar. O pior é querer ficar insistindo no erro.

Duran, o seu teste insere no começo: lista.add(0, elemento). A discussão é sobre a inserção no fim da lista: lista.add(elemento).

GUJ Master Membro desde: 23/01/2008 11:14:35 Mensagens: 1905 Offline

Fabio Kung wrote:Ou seja sergiotaborda está claramente errado.
Pode admitir. Errar é humano, não precisa se envergonhar. O pior é querer ficar insistindo no erro.

Duran, o seu teste insere no começo: lista.add(0, elemento). A discussão é sobre a inserção no fim da lista: lista.add(elemento).

é.

Estamos discutindo o performático em vista de fatores que combinem melhor resultado, não se pode limitar questão de perfomance nessa ótica de uma situação isolada referente ao algoritmo, é como eu lhe pergunta-se poderia usar ArryList em multi-thread, se sim, é mais adequado do que LinkedList ? Poderia fazer a demonstração nessa implementação.

Marcio Duran wrote:Estamos discutindo o performático em vista de fatores que combinem melhor resultado, não se pode limitar questão de perfomance nessa ótica de uma situação isolada referente ao algoritmo

Tem razão. E já foi dito nesse tópico algumas vezes que a melhor escolha vai depender do uso e necessidade.

Mas nesta discussão específica o ponto foi a afirmação de LinkedList ser "mais performático" para a operação add(elemento). O que claramente não é verdade, como mostrado pelo Paulo.

GUJ Master Membro desde: 23/01/2008 11:14:35 Mensagens: 1905 Offline

Fabio Kung wrote:
Tem razão. E já foi dito nesse tópico algumas vezes que a melhor escolha vai depender do uso e necessidade.

Veja aqui você concorda.

Mas nesta discussão específica o ponto foi a afirmação de LinkedList ser "mais performático" para a operação add(elemento). O que claramente não é verdade, como mostrado pelo Paulo.

E aqui você não prova a Versatilidade ao proposito de coleção e seu uso, não podemos falar de Objeto isoladamente sua funcionalidade e proposito nunca será para um termo específico mas no que faz ser o sentido de o que é objeto "estado e comportamento".Ainda estou esperando a implementação para multi-Thread em ArrayList e em que contexto agora você vai querer defender sua tese.

Marcio Duran wrote:Ainda estou esperando a implementação para multi-Thread em ArrayList

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/CopyOnWriteArrayList.html

Desculpa, mas o resto não consegui entender.

This message was edited 1 time. Last update was at 30/07/2009 20:59:02

Marcio Duran wrote:

Fabio Kung wrote:
Duran, o seu teste insere no começo: lista.add(0, elemento). A discussão é sobre a inserção no fim da lista: lista.add(elemento).

é

Estamos discutindo o performático em vista de fatores que combinem melhor resultado, não se pode limitar questão de perfomance

Sem duvida, é muito importante tambem discutirmos os outros metodos. O kung so quis afirmar que, como foi falado diversas vezes nessa thread, para o método add() que adiciona no final da lista, a ArrayList possui melhor performance que a LinkedList na prática e eficiência computacional igual na teoria (análise amortizada de pior caso). Ai voce postou uma comparacao de outro metodo, e pessoas poderiam ficar confusas achando que voce estaria falando do mesmo caso (metodo add no final).

GUJ Master Membro desde: 23/01/2008 11:14:35 Mensagens: 1905 Offline

Fabio Kung wrote:

Marcio Duran wrote:Ainda estou esperando a implementação para multi-Thread em ArrayList

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/CopyOnWriteArrayList.html
Desculpa, mas o resto não consegui entender.

é

"Perdão eu realmente não fui tão claro !!!"

Tese por algoritmo ou ao que estamos querendo dizer "Arquitetura e Design de Software" Uma visão sobre a plataforma Java

Essa a minha versão para LinkedList situação Multi-Theard

Desculpa, não entendi o seu exemplo.

GUJ Master Membro desde: 23/01/2008 11:14:35 Mensagens: 1905 Offline

Paulo Silveira wrote:

Marcio Duran wrote:

Fabio Kung wrote:
Duran, o seu teste insere no começo: lista.add(0, elemento). A discussão é sobre a inserção no fim da lista: lista.add(elemento).

é

Estamos discutindo o performático em vista de fatores que combinem melhor resultado, não se pode limitar questão de perfomance

Sem duvida, é muito importante tambem discutirmos os outros metodos. O kung so quis afirmar que, como foi falado diversas vezes nessa thread, para o método add() que adiciona no final da lista, a ArrayList possui melhor performance que a LinkedList na prática e eficiência computacional igual na teoria (análise amortizada de pior caso). Ai voce postou uma comparacao de outro metodo, e pessoas poderiam ficar confusas achando que voce estaria falando do mesmo caso (metodo add no final).

"Trecho de sua Obra".

"Receber ArrayList como argumento faz sentido em pouquíssimos casos: raramente precisamos que uma coleção seja tão específica assim. Receber aqui um List provavelmente basta para o nosso método, e permite que o código invocador passe outras coleções como argumento. Podemos ir além, e receber Collection ou ainda Iterable, caso nossa necessidade seja apenas percorrer a lista"

O assunto tem que decorrer sobre o que é arquitetura e ao que percebemos a usar, e não de forma especifica o determinado algoritmo mas o que se combina e faz sentido o seu melhor uso pela a coleção em pró até de um Design Pattern em função a gerencia de objetos.

Vamos entender Coleção em vista de arquitetura e não especificar o que tende a ser outras interpretações ao seu melhor uso.

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