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

Fala ai Marciao,

Well… existem varios casos a serem analisados, mas te digo o ArrayList e o mais rapido para consultar elementos atraves do indice.

Posso garantir isso, pois realizei varios testes de profiling, e este e o que ocupa menos memoria e tem melhor tempo de resposta.

Abraçaooooo

ccaneta:

Fala ai Marciao,

Well… existem varios casos a serem analisados, mas te digo o ArrayList e o mais rapido para consultar elementos atraves do indice.

Posso garantir isso, pois realizei varios testes de profiling, e este e o que ocupa menos memoria e tem melhor tempo de resposta.
Abraçaooooo

Veja quanto ao Profiling fica um mecanismo que é de pura instrumentação mas não vai ainda em si lhe provar tal tese a não ser que você já tenha isso simulado ou observado em arquiteturas anteriores.

Profiling é o Marketing !!!

Os critérios que ele fala são quando você dá um peso maior à uma característica específica que a implementação provê.

No caso de Lists, o ArrayList tem a melhor performance para selecionar aleatóriamente um elemento, LinkedList é a melhor opção se você for trabalhar pesadamente com inserções no começo ou no final da lista, mas ela é ruim com acessos aleatórios. Vector utilizaria se precisasse de sincronização na lista (ou Collections.synchronizedList). Queues para FIFO, Stacks para LIFO…

Maps e Sets também podemos usar, mas tem usos específicos completamente diferentes.

Teoria, performance, tempo de processador, gasto de memória, propósito, todos são critérios a se considerar.

Bruno Laturner:

Os critérios que ele fala são quando você dá um peso maior à uma característica específica que a implementação provê.

No caso de Lists, o ArrayList tem a melhor performance para selecionar aleatóriamente um elemento, LinkedList é a melhor opção se você for trabalhar pesadamente com inserções no começo ou no final da lista, mas ela é ruim com acessos aleatórios. Vector utilizaria se precisasse de sincronização na lista (ou Collections.synchronizedList). Queues para FIFO, Stacks para LIFO…

Maps e Sets também podemos usar, mas tem usos específicos completamente diferentes.

Teoria, performance, tempo de processador, gasto de memória, propósito, todos são critérios a se considerar.

Agora eu pergunto, como achar o ponto certo ao uso dessas coleções para determinadas parte de seu Framework de sua Arquitetura, e que Design Pattern iria melhor prover resultados combinados com ela.Sera que isso é regra ?

Veja a situação aqui do Tiny Types como gerou um contrasenso ao seu uso, será que temos uma regra ou isso decorre de outras observações

Onde você quer chegar? Mal da pra entender seus posts, leio e não sei se é uma pergunta ou uma afirmação.

Fato! Não consigo entender nada dos posts dele!

Primeiro, é saber qual problema que você tem e o que solução precisa ter para resolvê-lo. Isso tanto em níveis de código, quanto de design, e até na concepção, é comum um cliente só saber que ele tem um desconforto que ele quer resolver, mas não sabe as causas dele. Aí entram as consultorias para ajudá-lo.

Segundo, é leitura para conhecer as possíveis soluções, ou pelo menos ouvir falar delas. O que canso de ver é gente subestimando o Javadoc das APIs do Java.

Sobre usar Design Patterns: Experiência

e o que a falta de experiência faz nesses casos:

RT @AkitaOnRails Design Patterns considered Harmful (for newbies) http://blog.jovan-s.com/2009/07/29/do-not-use-design-patterns-upfront/
http://c2.com/cgi/wiki?DesignPatternsConsideredHarmful
http://developers.slashdot.org/comments.pl?sid=33602&cid=3636102

Bruno Laturner:

Os critérios que ele fala são quando você dá um peso maior à uma característica específica que a implementação provê.

No caso de Lists, o ArrayList tem a melhor performance para selecionar aleatóriamente um elemento, LinkedList é a melhor opção se você for trabalhar pesadamente com inserções no começo ou no final da lista, mas ela é ruim com acessos aleatórios. Vector utilizaria se precisasse de sincronização na lista (ou Collections.synchronizedList). Queues para FIFO, Stacks para LIFO…

Maps e Sets também podemos usar, mas tem usos específicos completamente diferentes.

Teoria, performance, tempo de processador, gasto de memória, propósito, todos são critérios a se considerar.

E depois dizem que otimização permatura é a raiz de todo o mal (balela). A escolha de qual implementação usar para um Lsit ou um Set e até se usar List ou Collection é vital.

só um adendo : LinkedList não é só melhor para inserções no inicio e no final. ele é bom para inserções normais (add) melhor que arraylist.
É raro, excepto em algum algoritmo muito especial ( como sorting) que faça acesso aleatório à lista. E nesse caso LinkedList sempre ganha porque normalmente o que vc quer fazer é adicionar um monte de objetos e depois iterá-los. É aqui que LinkedList é melhor.
Só existe um caso em que ArrayList é preferivel (tirando fora o acesso aleatorio) : quando vc sabe quantos elementos a lista vai ter.

Este codiog

List list = new ArrayList();

é uma má prática.
Se vc sabe quantos elementos vai ter , use

List list = new ArrayList(numerodeElementos);

Se vc não sabe , use LinkeList.

Um caso particular de saber quantos elementos ha é a copia de collecções, por exemplo

Set set = ... 
List list = new ArrayList(set);

Usar ArrayList por padrão é errado. Com as opções que temos hoje em dia, é preciso saber o que estamos fazendo.
Este é um exemplo de que otimização permantura não é problema quando é OO.

Eu sou mais um ArrayList em cenarios de alto perfomance…

“Este é um exemplo de que otimização permantura não é problema quando é OO”, concordo plenamente com a colocação do Sergio Taborda.

E acredito que linguagens tenha comportamento estratégicos com determinados Design Pattern e no que se refere também ao uso de suas regras, isso pode variar no contexto do FrameWork ou Arquitetura orientada ao Domínio ou Arquitetura orientado a Dados.

Mas o que vem a ser cenários de alta performance, isso se reflete para que padrões de projetos ?

Marcio Duran:

Mas o que vem a ser cenários de alta performance, isso se reflete para que padrões de projetos ?

Fala ai Marciao,

Entao Projetos de alta Perfomance sao aquelas situaçoes em que temos muita pouca memoria disponivel e precisamos de perfomance extrema, e qualquer otimizaçao q possa ser feita para evitar acessos de IO ou mais objetos na HEAP e mais que necessaria.

Como vc ja deve ter vivenciado nos clientes de mercado, as vezes a carga de usuarios referente junto com a má arquitetura projetada para aquela aplicaçao num servidor, podem virar uma verdadeira bomba atomica que ninguem sabe onde arrumar. No final isso vira o famoso Patinho feio!!

por isso, as vezes temos abrir mao de um bom design e projetarmos somente o extremo necessario.

abraçaoooo

Mas você pegaria um projeto legado e sairia indiscriminadamente trocando as ArrayLists por LinkedList?

Rubem Azenha:

sergiotaborda:

E depois dizem que otimização permatura é a raiz de todo o mal (balela). A escolha de qual implementação usar para um Lsit ou um Set e até se usar List ou Collection é vital.

Mas você pegaria um projeto legado e sairia indiscriminadamente trocando as ArrayLists por LinkedList?

Heh, um problema de pegar esses legados é que tem sempre um que inventa de fazer coerção forçada de List para Vector(ou pior, só usar Vector), e quando você quer mudar a implementação, lá vem um ClassCastException.

Se realmente tivesse programado voltado para interfaces, poderia mudar as implementações de boa.

Bruno Laturner:

Se realmente tivesse programado voltado para interfaces, poderia mudar as implementações de boa.

Devemos preferir polimorfismo ao inves de herença ?

Marcio Duran:

Bruno Laturner:

Se realmente tivesse programado voltado para interfaces, poderia mudar as implementações de boa.

Devemos preferir polimorfismo ao inves de herença ?

Devemos preferir as soluções com menor acoplamento.

E antes que alguém pergunte: Existe polimorfismo sem herança?

sergiotaborda:

E depois dizem que otimização permatura é a raiz de todo o mal (balela). A escolha de qual implementação usar para um Lsit ou um Set e até se usar List ou Collection é vital.

Sem duvida, é vital! Mas a graça toda é que, se voce escolher errada a sua implementacao de Set, List ou Collection, voce pode mudar depois com extrema facilidade. Entao (na maioria das vezes) nao precisa tomar extremo cuidado com isso prematuramente (a nao ser que o cara nao programar voltado pra interface, e declarar como ArrayList, ai ele pode se complicar pra trocar depois).

Eu nao acho balela essa frase da otimizacao prematura (vale lembrar que ela inteira é “we should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil”), nem o Hoare (inventor do quicksort, autor do pensamento), nem o Knuth (que popularizou a frase).

Sergio, nos meus testes ArrayList sempre ganhou de performance no .add, mesmo sem definicao do tamanho inicial (com definicao, ela da um coro na linkedlist). E de memoria a ArrayList usa bem menos espaco (4 bytes para cada referencia, a LinkedList usa 12!).

Paulo Silveira:

sergiotaborda:

só um adendo : LinkedList não é só melhor para inserções no inicio e no final. ele é bom para inserções normais (add) melhor que arraylist.

Sergio, nos meus testes ArrayList sempre ganhou de performance no .add, mesmo sem definicao do tamanho inicial (com definicao, ela da um coro na linkedlist). E de memoria a ArrayList usa bem menos espaco (4 bytes para cada referencia, a LinkedList usa 12!).

Como EU havia mencionado no post inicial… ArrayList é a melhor opçao para perfomance!!

sim, tem razao, comparado com LinkedList, pra acesso a indice, ninguem disse o contrario. mas…
http://blog.caelum.com.br/2006/10/04/performance-hashset-em-vez-de-arraylist/

Paulo Silveira:

ccaneta:

Como EU havia mencionado no post inicial… ArrayList é a melhor opçao para perfomance!!

sim, tem razao, comparado com LinkedList, pra acesso a indice, ninguem disse o contrario. mas…
http://blog.caelum.com.br/2006/10/04/performance-hashset-em-vez-de-arraylist/

Collection colecao = new ArrayList();

Para:

:arrow: Collection colecao = new HashSet();

O novo resultado? Incríveis 0,078 ms. 114 vezes mais rápido! "Execução normal ou Test profiling ? "

:arrow: http://www.yourkit.com/

Normal. Mas no profile vai dar a mesma diferenca. Aqui o que ocorre é que computacionalmente o algoritmo é absurdamente melhor. Se voce aumentar os tamanhos, a diferenca sera mais gritante, como 1 milhao de vezes mais rapido.

Apontem seus profiles para este código:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
import java.util.RandomAccess;

public class ComparacaoLinkedListvsArrayList {
	List list = null;

	Random random = new Random();

	int n = 160000;

	int read = 12000;

	int remove = 12000;

	int insert = 20000;

	int remLast = 12000;

	long before, after;

	public ComparacaoLinkedListvsArrayList(List impl) {
		list = impl;
	}

	public void run() {
		System.out.println("List type: " + list.getClass().getName());

		System.out.print("Creating a list of " + n + " positions: ");
		before = System.currentTimeMillis();
		// Add objects to the list.
		for (int i = 0; i < n; i++) {
			list.add(new String());
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");

		// Read random positions
		System.out.print("Accessing " + read + " random positions: ");
		before = System.currentTimeMillis();
		for (int i = 0; i < read; i++) {
			list.get(getRandomNumber());
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");

		// Remove random positions
		System.out.print("Remove " + remove + " random positions: ");
		before = System.currentTimeMillis();
		for (int i = 0; i < remove; i++) {
			list.remove(getRandomNumber());
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");

		// Insert objects into random positions
		System.out.print("Insert " + insert + " objects into random positions: ");
		before = System.currentTimeMillis();
		for (int i = 0; i < insert; i++) {
			list.add(getRandomNumber(), new String());
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");

		// Insert objects into middle positions
		int pos = 2000;
		System.out.print("Insert " + insert + " objects into middle positions: ");
		if (list instanceof RandomAccess) {
			before = System.currentTimeMillis();
			for (int j = pos; j < ((pos + insert) < list.size() ? (pos + insert) : list.size()); j++) {
				list.add(j, new String());
			}
			after = System.currentTimeMillis();
		} else {
			before = System.currentTimeMillis();
			ListIterator li = (ListIterator) list.iterator();
			for (int j = pos; j < ((pos + insert) < list.size() ? (pos + insert) : list.size()); j++) {
				li.next();
				li.add(new String());
			}
			after = System.currentTimeMillis();
		}
		System.out.println((after - before) + "ms");

		// Insert objects into initial position
		System.out.print("Insert " + insert + " objects into initial position: ");
		before = System.currentTimeMillis();
		for (int i = 0; i < insert; i++) {
			list.add(0, new String());
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");

		// Insert objects into last position
		System.out.print("Insert " + insert + " objects into last position: ");
		before = System.currentTimeMillis();
		for (int i = 0; i < insert; i++) {
			list.add(list.size(), new String());
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");

		// Remove last position objects
		System.out.print("Remove " + remLast + " objects from the last position: ");
		before = System.currentTimeMillis();
		for (int i = 0; i < remLast; i++) {
			list.remove(list.size() - 1);
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");

		// Remove initial position objects
		System.out.print("Remove " + remove + " objects from the initial position: ");
		before = System.currentTimeMillis();
		for (int i = 0; i < remove; i++) {
			list.remove(0);
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");

		// Insert objects into middle positions
		System.out.print("Insert " + insert + " objects into middle positions: ");
		if (list instanceof RandomAccess) {
			before = System.currentTimeMillis();
			for (int j = pos; j < ((pos + insert) < list.size() ? (pos + insert) : list.size()); j++) {
				list.remove(j);
			}
			after = System.currentTimeMillis();
		} else {
			before = System.currentTimeMillis();
			ListIterator li = (ListIterator) list.iterator();
			for (int j = pos; j < ((pos + insert) < list.size() ? (pos + insert) : list.size()); j++) {
				li.next();
				li.remove();
			}
			after = System.currentTimeMillis();
		}
		System.out.println((after - before) + "ms");

		// Read all objects sequentially
		System.out.print("Read all " + list.size() + " objects sequentially: ");
		before = System.currentTimeMillis();
		ListIterator it = list.listIterator();
		while (it.hasNext()) {
			it.next();
		}
		after = System.currentTimeMillis();
		System.out.println((after - before) + "ms");
	}

	private int getRandomNumber() {
		return random.nextInt(list.size() - 1) + 1;
	}

	public static void main(String[] args) {
		ComparacaoLinkedListvsArrayList lp = new ComparacaoLinkedListvsArrayList(new ArrayList());
		lp.run();
		for (int i = 0; i < 3; i++)
			System.out.println("");
		lp = new ComparacaoLinkedListvsArrayList(new LinkedList());
		lp.run();
	}
}

Rubem Azenha:

sergiotaborda:

E depois dizem que otimização permatura é a raiz de todo o mal (balela). A escolha de qual implementação usar para um Lsit ou um Set e até se usar List ou Collection é vital.

Mas você pegaria um projeto legado e sairia indiscriminadamente trocando as ArrayLists por LinkedList?

Legado é legado. Modelagem OO, é , quase que por definição, para software novo.

Vc pode fazer arquologia de software, mas é complexo e não merece o trabalho a menos que haja algum problema para resolver.

Paulo Silveira:

sergiotaborda:

E depois dizem que otimização permatura é a raiz de todo o mal (balela). A escolha de qual implementação usar para um Lsit ou um Set e até se usar List ou Collection é vital.

Sem duvida, é vital! Mas a graça toda é que, se voce escolher errada a sua implementacao de Set, List ou Collection, voce pode mudar depois com extrema facilidade.

Não, não pode. Mudar de Collection para Set até que dá ( já que set tem o mesmo contrato) , mas de List para os outros ou dos outros para list, não.
Set = unico elemento
List = várias copias
colection = tanto me faz.

A interface sempre deve ser collection. Set apenas se não existirem repetidos e tem que haver uma muito boa razão para ser List (já que repetidos é raro)

Agora, mudar ArrayList para LinkedList ou CopyOnWriteArrayList, ai tudo bem.

Mas só porque vc pode mudar depois, não quer dizer que seu codigo inicial tem que ser mal cuidado. Afinal quantas vezes vc quer reescrever o mesm o codigo? eu não gosto de fazer isso, então aponto para reescrita zero.

Quanto à performance.
Comparar Set com list é simplesmente absurdo qq que seja a implementação. É como dizer que um Map é mais rápido que String.
ArrayList só é mais rápido se existirem poucos rearranjos do array interno. O arraylist padrão tem 10 itens de tamanho. se vc adicionar muitos itens o tempo não é constante, no linkedlist é. Performance não se mede em milisegundos.

Claro que se vc tiver esse numero de elementos está na hora de usar FastLane de qq fora… o ponto q que me referi é que LinkedList não é só apenas para adicionar no fim e no principio já que addLast é igual a add.

sergiotaborda:

Paulo Silveira:

sergiotaborda:

E depois dizem que otimização permatura é a raiz de todo o mal (balela). A escolha de qual implementação usar para um Lsit ou um Set e até se usar List ou Collection é vital.

Sem duvida, é vital! Mas a graça toda é que, se voce escolher errada a sua implementacao de Set, List ou Collection, voce pode mudar depois com extrema facilidade.

Não, não pode. Mudar de Collection para Set até que dá ( já que set tem o mesmo contrato) , mas de List para os outros ou dos outros para list, não.

Por favor Sergio, cuidado ao me citar, estamos falando de mudar IMPLEMENTACOES, nao INTERFACE (releia minha frase, eu falei “se voce escolher errada a sua IMPLEMENTACAO”, e nao interface. É obvio e bem basico que de List para Set voce vai ter problemas, e eu NAO falei isso.

Em ambos os casos o tempo é computacionalmente constante (O(1)). O que acontece é que no arraylist pode ser invocado o ensureCapacity, que roda em tempo O(n), mas amortizadamente o tempo é constante, ja que o ensureCapacity é invocado cada vez mais raramente (expansao exponencial de array). Alias, acabo de ver que isso esta escrito ate mesmo no javadoc. “The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.”. Se voce rodar o teste que postaram aqui, vai ver que na pratica arraylist tambem é mais rapida, mesmo sem o tamanho inicial, para o add no final.

Paulo Silveira:

Em ambos os casos o tempo é computacionalmente constante (O(1)). O que acontece é que no arraylist pode ser invocado o ensureCapacity, que roda em tempo O(n), mas amortizadamente o tempo é constante, ja que o ensureCapacity é invocado cada vez mais raramente (expansao exponencial de array). Alias, acabo de ver que isso esta escrito ate mesmo no javadoc. “The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.”. Se voce rodar o teste que postaram aqui, vai ver que na pratica arraylist tambem é mais rapida, mesmo sem o tamanho inicial, para o add no final.

Já que estamos tendo cuidado na citação: eu não disse que era constante para arraylist. Eu disse que era para LinkedList.
O javadoc que citou é para ArryList. O Javadoc de LinkedList não fala qual é a porpoção para LinkedList. Mas , conjecturanto o obvio, é O(1) Como vc mesmo falou O(1) é o normal. ArrayList só é O(n) por causa do ensureCapacity.

Ou seja, para add(object) LinkedList é sempre mais eficiente. E como eu disse, performance não se mede em milisegundos.
Acontece que para poucos objetos ( tb já disse isto) o tempo vai se quase o mesmo para ambos. A diferença só aparece para muitos objetos. Mas nesse ( tb já disse isto) vc não vai usar nenhum Collection, portanto o problema não se coloca.

Só para completar :

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

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

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

[quote=aleck]Apontem seus profiles para este código:

(...)

Belo teste hein, derrubou um ou dois mitos sobre a performance de cada um. Não esperava que os arrays fossem melhores nas operações no final, mas o Paulo deu uma boa razão. Acesso sequencial estão praticamente iguais (dá pra ver a diferença de meio milisegundo usando o System.nanoTime).

aleck:

sergiotaborda:

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. 8)

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

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

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

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í.

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)).

Paulo Silveira:

sergiotaborda:

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:

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

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)…

import java.util.*;

    public class ListDemo2 {
        static final int N = 50000;

        // time how long it takes to add 
        // N objects to a list

        static long timeList(List lst) {
            long start = System.currentTimeMillis();

            Object obj = new Object();

            for (int i = 0; i < N; i++) {
                lst.add(0, obj);
            }

            return System.currentTimeMillis() - start;
        }

        public static void main(String args[]) {

            // do timing for ArrayList

            System.out.println(
                "time for ArrayList = " +
                timeList(new ArrayList()));

            // do timing for LinkedList

            System.out.println(
                "time for LinkedList = " +
                timeList(new LinkedList()));
        }
    }

Resultado tempo gasto ArrayList = 4859

Resultado tempo gasto LinkedList = 125

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).

Fabio Kung:

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.

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.

Fabio Kung:

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.

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

Desculpa, mas o resto não consegui entender.

Marcio Duran:

Fabio Kung:

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).

Fabio Kung:

Marcio Duran:

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

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

class PrepareProduction implements Runnable {
  private final List<String> queue;

  PrepareProduction(List<String> q) {
    queue = q;
  }

  public void run() {
    queue.add("1");
    queue.add("done");
  }
}

class DoProduction implements Runnable {
  private final List<String> queue;

  DoProduction(List<String> q) {
    queue = q;
  }

  public void run() {
    String value = queue.remove(0);
    while (!value.equals("*")) {
      System.out.println(value);
      value = queue.remove(0);
    }
  }
}

public class Main {
  public static void main(String[] args) throws Exception {
    List q = Collections.synchronizedList(new LinkedList<String>());
    Thread p1 = new Thread(new PrepareProduction(q));
    Thread c1 = new Thread(new DoProduction(q));
    p1.start();
    c1.start();
    p1.join();
    c1.join();
  }
}

Desculpa, não entendi o seu exemplo.

Paulo Silveira:

Marcio Duran:

Fabio Kung:

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).

“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.

oi duran, realmente ja fugimos do topico… era pra falar de design e estamos falando de algoritmos. acabamos levando seu topico pra outro lado, mas é que ficou divertido o assunto.

Olá!

Já tive alguns problemas pegando código pronto, em que praticamente tudo foi feito com List… acho que foi a escolha default do desenvolvedor e na situação, unicidade provavelmente não era sua prioridade. Em muitas partes havia código que iterava na lista inteira e verificava a unicidade dos elementos, removendo os duplicados. Eu corrigi um outro problema ali perto e resolvi refatorar o código, arrumando o equals/hashCode dos elementos e substituindo quase tudo pra Set (quase porque tinham certos códigos que eu não me arriscaria a mexer, trocar tipo de retorno, argumentos de métodos, por exemplo). O que me ajudou muito, foi o fato das collections serem “Wrappers” de Collection. Portanto não era raro trechos como:

conjunto = new HashSet(metodoQueRetornaAListaAntigaQueEuNaoToAfimDeMexer());

Nesse caso, o desenvolvedor que criou o código podia ter dado mais importância a análise do problema que ele deveria resolver e escolher a melhor opção para cada caso. Ou então, se ele tivesse trabalhado sempre com o maior nível (Collection) eu conseguiria fazer esse tipo de alteração de maneira transparente.

Abraços

Fabio Kung:

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

não posso admitir o que não é verdade.

O paulo escreveu

Ok, então se eu der addFirst ou add(0, obj) tenho O(1) em linked e O(n) em array.
Ok, agora tendo isso por base, explique a diferença de performance entre addFirst e addLast para linked list.
Nenhuma. Em addFirst o nodo cabeça é substiuido por um novo nodo e o novo cabeça é atribuido como cauda do novo novo.
NO addLast é feio ao contrário. Mas a operação em si é a mesma (criar um nodo e atribuir 2 variáveis) Isto não depende de quantos elemento existem na lista e portanto sempre terá performance O(1) .

Portanto, linkedlsit SEMPRE tem performance O(1) para insersções no fim ou no principio. Não importa em qual ponta é feita a alteração.

Agora, compare add(obj) de ambos.
Para linked list é dado um addLast() (ver javadoc) logo a performance de add() para linked list é O(1) tb.
Mas para array list a performance de add() é O(n) . Veja o javadoc. Está la´escrito explicitamente. Não estou inventando nada aqui.

Portanto, para o add() que é o mais usado, LinkeList é melhor.

Quando e que linked lsit não é melhor ? Quando usa add(i, obj) ou remove(i) ou get(i). Qualquer método que use o indice , linked é pior.
Mas para o add() normal linked é melhor.

O que o cara fala no link é isto mesmo. Esse negocio de média é treta. Às vezes parece que vcs não entendem inglês e ficam-se apegando às palavras.
O que ele quer dizer, e é isso que interessa é o seguinte :
Quando o array interno do array list suporta mais um elemento, o elemento é inserido e pornto. Isso é O(1) porque não depende de quantos elementos existem no array. Até aqui, é a mesma coisa que o linked list.

( o detalhes é que colocar o objet no array é muito mais rápido que criar o objeto de novo no linked list e fazer o swap, e por isso que dá menos milisegundos)

Bom, então mas e o que acotece quando o array não é suficiente ?
um novo array maior é criado e o antigo copiado para este (ensureCapacity) e depois a operação original é feita.
Esta copia depende do numero de elementos que já estão no array (n) e portanto é uma operação O(n).

Portanto, no compto final ( é isso que o cara quiz dizer com “average”), o método é composto por um O(1) e um O(n). Como saberão da metamática a composição é O(n). Logo, embora a maior parte das vezes seja O(1) e mais rápido (em milsegundos ) que LinkedList, no caso geral (um trilhão de objetos) a performance cai para O(n).

O ponto é que copiar um array, embora O(n) é uma operação rápida para n pequeno. Quando n aumenta o tempo tb aumenta contráriamente ao do Linked List que demora um pouco mais para ocaso simples, mas demora sempre o mesmo tempo idepenente de n.

LinkeList tem ainda outra vantagem ,por conter mais do que Integer.Max_VaLue/ 2. Que é imenso.

Lá no link até tem o codigo fonte dos dois. Mas vc podem procurar o original e ver.
Vc estão confundindo a classificação O() como rapidez. São duas coisas diferentes!

Agora, se entenderam , entenderam.
Se não entenderam , continuem usando ArrayList em todo o lugar.

O problema não é meu.

Voce so esta falando o que ja falamos aqui, quando eu falei do ensureCapacity mais pra frente. O que vale é o amortizado! Ou voce usa sempre uma arraylsit so para adicionar um unico elemento quando ele tem 10 * 2?n elementos. amortizadamente, que é o que vale no final, é O(1), como ja falamos, e como esta explicitamente escrito no javadoc:

e no wikipedia, vamos pegar o exemplo mais simples de analise amortizada:

Sergio, de verdade, leia o Cormen, voce vai ver que o add(i,obj) e remove(i) da lista ligada tem a MESMA performance computacional que a ArrayList (O(n) para ambas no caso de nao ter ponteiro para o nó interno a estrutura de dados, como é o caso do java)), ja que ela tera de percorrer a lista até chegar ao iésimo elemento, e a ArrayList tera de “empurrar” (copiar) todos os elementos para frente. Voce de novo falou algo completamente errado de analise de algoritmos. O unico que voce tem razao é o get(i). Voce tem um artigo no seu site sobre coleções e não sabe que o remove(i) e add(i, obj) da LinkedList tem a mesma performance computacional que da ArrayList. Nao é só porque ArrayList tem acesso aleatório pelo indice que ela é mais rapida em todos os métodos que o envolvem, pesquise mais (lendo o código fonte da ArrayList voce vai perceber o shift de posicoes).

NUNCA!!! Muito pelo contrario, a performance amortizada (que seria a average, como falaram na wikipedia) de uma inserção é O(1) na média do caso geral! Esta claro que voce nunca passou por uma literatura de analise de algoritmos, amortização e performance. Isso que é a analise amortizada e voce demonstra mais uma vez nao conhecer. Insira 1 trilhao de objetos na ArrayList (nao cabe, mas ok) e vai ver que ela é mais rapida que LinkedList (rapida de tempo, igual de performance computacional). Voce continua se baseando em citar um cara que fala de insercoes em listas ligadas classicas em custo O(logn), é um absurdo… por favor, cite alguma referencia mais forte, como o Cormen, o Sedgewick ou o Knuth.

Comentario desnecessario e sem sentido algum. Ate parece que voce vai ter uma lista ligada com 2 bilhoes de elementos, e gastar 24 giga ram so com os 3 ponteiros que cada nó usa, sem contar com os objetos (vai me falar que voce trabalha com sistemas assim?). Entao “tem ainda outra vantagem” fica como? Voce realmente esta tentando fugir para outros argumentos que nao vem ao caso. E corrigindo novamente, o maximo de ArrayList não é Integer.MAX_VALUE/2, e sim Integer.MAX_VALUE.

Um senior tem coragem de reconhecer o erro. Eu sempre falo que o bom programador reconhece seu erro. Mas, “cada um é cada um”

é, definitivamente sem vc parar para entender custo amortizado nao tem discussao mais.
to fora…

PS. só pra registrar pra posteridade e futuros gujeiros que caiam aqui: o taborda está absurdamente errado, o ArrayList#add(obj) é O(1) no tempo amortizado, igual ao LinkedList e ainda mais rapido na pratica. E o javadoc concorda com a gente

ahehaua vou começar a pedir desculpas por discordar das pessoas aqui…

Sergio Lopes:

PS. só pra registrar pra posteridade e futuros gujeiros que caiam aqui: o taborda está absurdamente errado, o ArrayList#add(obj) é O(1) no tempo amortizado, igual ao LinkedList e ainda mais rapido na pratica. E o javadoc concorda com a gente

E tambem pra ficar registrado, add(i, obj) e remove(i) são O(n) tanto pra LinkedList quanto para ArrayList.

E quem quiser ver mais, pode ler no Cormen, ou até mesmo no Java Generics, livro escrito por um dos autores das colecoes do java.util.

Aqui tem um resumo:
http://www.coderfriendly.com/2009/05/12/java-collections-cheatsheet/

mostrando que inserir no fim da ArrayList é O(1). e o livro mostra que inserir no meio ou remover do meio, numa ArrayList e numa LinkedList é o mesmo tempo, diferente do que o Taborda afirmou categoricamente.

Não será sempre que empurra. Apenas quando existem elementos além de i.
Essa é a diferença. Da mesma forma que no add ele só precisa copiar quando o array é pequeno.

Mas o Linked SEMPRE tem que percorrer a cadeia até i.
Linked tem O(i) ( não de n) e Array tem O(n) por causa da copia. Mas o mais comum é não haver essa copia, tal como no add ou ela ter poucos elementos. E se vc programar direito - que é disso que estou falando - O(n) nem nunca acontece em arraylist pq vc nunca fará a cópia.

No caso comum do software de paradia do dia a dia , ArrayLsit é mais rápido (executa em menos milisegundos) porque o custo só aparece quando ha muitos elementos contidos no array e o tamanho final é desconhecido .

Nos meus programas é raro que eu não saiba quanto vai ser o tamanho final e sempre inicializo com ArrayList(tamanhoFinal). Assim nunca haverá ensureCapacity e o funcionamento sempre será independente do numero de elementos. Como já disse tb não é comum usar o get(i) ou add(i,obj).
Portanto, na maioria das vezes utilizo o ArrayList porque nestas consições ele é o mais eficaz*.

(* porque nunca itero usando o idioma for (int i ) , sempre com iterator ou extended for, e nunca uso get(i) ou outros métodos que dependem do indice.)

Agora, na condição de não saber o tamanho final, uso LinkedList. Isto é para me precaver já que eu não sei quantos ensureCapacity precisam ser executados durante o carregamento. Acontece que esta situação é rara. Se eu não sei quantos são, eu primeiro vou saber. No carregamento de dados de banco, por exemplo, é sempre possivel fazer um count. Só que, para carregamento de banco não uso Collection. Uso fastlaneReader e ai o problema nem sequer se coloca. Em outras situações é possivel estimar o tamnho final e minimizar a chamada a ensureCapacity() colocando um numero que não sendo o final é muito proximo, e portanto diminui a chance de ensureCapacitty ser chamado.
Só sobra uma ocasião em que ainda não sei o tamanho final : listeners. Mas ai existe o CopyOnWriteArrayList ( ou …ArraySet conforme a duplicidade).

Moral da historia ( que vcs ainda não entenderam ) :

• ArrayList é para ser usado com o construtor que informa o tamanho final. Sempre! É isso que garante que ele sempre será mais rápido que as outras implementações.
• Rapidez se mede em segundos , performance se mede em numero de instruções e se caracteriza com o famoso O(dealgumacoisa).

Alguns algoritmos que têm eficacia maior ( melhor O) mas não são usados no caso geral porque as instruções em causa são mais lentas. ( ou seja, o algoritmo faz menos intruções, mas as que faz são mais lentas, logo, no copto geral, o algoritmo é pior que outro que tem mais instruções e mais rápidas)

São duas dimensões que é preciso considerer do algoritmo. E elas não são proporcionais!

Vcs estão dizendo que ArrayList tem melhor performance porque é mais rápido. Isso é conversa para enganar trouxa. Uma coisa não é proporcional à outra. Não é assim tão dificil de entender.

• ArrayList é mais rápido que LinkedList. Sim. Mas não tem melhor performance!
• A performance de add, addFirst e addLast para LinkedList é a mesma! portanto dizer que linked só deve ser usado para adicionar no inicio é mais conversa para enganar trouxa. Acho que vc não entendem a propriedade transitiva Se add=addLast e f(addFirst) = f(addLast ) => f(addFirst) = f(add)
  Para ser coerente vcs têm que entender que a performance de todos os add não indexados de Linked é a mesma e por isso que ele é util . Não estamos falando na rapidez!

Se vc usa ArrayList(tamanho) otimo. Não ha problema nenhum em usar ArrayList. Só não me diga que ArrayLis() - sem tamanho - tem melhor performance que LinkeList() para inserção com add que não é verdade. A prova está no javadoc e no proprio codigo fonte! Contra fatos não ha argumentos.

A performance de ArrayList depende do numero de elementos nele e vc só pode afirmar que é mais ou menos performático em casos particulares tendo em vista o numero de elementos. E nesse caso vc usa ArrayList(tamanho) para começo de conversa.
Ou seja, não ha desculpa para usar

List list = new ArrayList() ;

Não pode ser assim tão dificil entender isto.
Se ainda não está convencido leia Efective Java segunda edição.

Se vc não sabe o que é um paragrafo - ou gosta de ataque add hominem - realmente não tem.
As palavras chave são "tem ainda outra vantagem" . E o ponto é reforçar que LinkedList tem vantagens sobre ArrayList.
Pela vossa argumentação ArrayList é melhor que Linked para add() sempre. O meu ponto é que não é sempre.

Daqui só posso inferir que vcs são todos juniors. Ninguem sabe a diferença entre performance e rapidez e ninguem sabe fazer a analise de perfornance a partir do codigo fonte ! Pipor que isso, acham que não estão errados e toda esta conversa é divertida e não têm vergonha se ensinar coisas erradas a todo o GUJ. Existem pessoas inesperientes lendo. E se elas forem na vossa conversa … sim, ainda bem que cada um é cada um.

???

Eu disse, na outra pagina, e mais diversas vezes que:

Por favor, peço mais uma vez, nao coloque palavras na minha boca, faca citacoes. Voce usa a palavra “rapidez” para computação, que ninguem aqui usou, e evita eficiência computacional, para falar um monte de abobrinhas, como essa:

Como i pode ser n, O(i) = O(n). Ja que voce mostra não saber, vou dar a dica, a notação O é a analise do pior caso. é que voce nao percebe, mas fica nitido que voce está aprendendo a notação O() agora, e cometendo os erros que todo estudante de computação faz na faculdade nesse início. é normal, também achava .

leia um pouco do big-O-notation, ja que voce deixou claro que nao sabe do que esta falando depois dessa frase, e ainda quer discutir analise de algoritmos aqui. Aconselho o Cormen para uma boa introodução. Junior é falar do que não sabe com arrogancia e pretensão.

Diz isso pro usuário do software. Ou para o seu líder de projetos. Será que pra eles não vai ser assim tão difícil entender?

Fiquei realmente traumatizado com essa frase. Pra voce ver mais claro seu erro a array tem O(n-i) pois empurra os elementos do final. E, se voce estudar um pouco, vai descobrir que O(i) = O(n-i) = O(n) para i nao constante.

Vamos citar alguns livros pra ver se te ajuda:
http://books.google.com.br/books?id=gCAbDb0u7b0C&pg=PA49&lpg=PA49&dq=array+insertion+remove+big+O+notation&source=bl&ots=UXjJ3AQMCV&sig=9eymxkuB7MWnkGVX3fulvcRzpDE&hl=en&ei=0y5zSoWwK4r4Nb3xqLEM&sa=X&oi=book_result&ct=result&resnum=1#v=onepage&q=&f=false

Inserting in the array based implementation and inserting in the linked implementation is both O(1). Deletion in both implementations is O(Length)

Ficou claro? No Cormen tem a mesma coisa, 100x mais detalhado, falando dos casos especificos de adicionar no comeco, no meio, no fim, com acesso aos nodes internos, sem acesso, etc. De onde me baseio para a argumentacao aqui.

logo, eficiencia computacional iguais (obviamente tempo de velocidade diferentes no cronometro).

Mande citacoes de livros pra embasar suas estranhas teorias de analise de algoritmo, onde O(i) é diferente de O(n) para i nao-constante.

Paulo Silveira:

sergiotaborda:

Vcs estão dizendo que ArrayList tem melhor performance porque é mais rápido.

???

Eu disse, na outra pagina, e mais diversas vezes que:

Por favor, peço mais uma vez, nao coloque palavras na minha boca, faca citacoes. Voce usa a palavra “rapidez” para computação, que ninguem aqui usou, e evita eficiência computacional, para falar um monte de abobrinhas, como essa:

Como i pode ser n, O(i) = O(n). Ja que voce mostra não saber, vou dar a dica, a notação O é a analise do pior caso. é que voce nao percebe, mas fica nitido que voce está aprendendo a notação O() agora, e cometendo os erros que todo estudante de computação faz na faculdade nesse início. é normal, também achava .

Vcs são incriveis. Não entendem protuguês ( nem inglês) , torcam tudo , ficam fazendo ataques ad hominem , porque não têm como argumentar contra e mal interpretam o texto de propósito só para ser o ultimo a falar.

n é o numero de elementos na coleção. i é a posição. i não pode ser n. ( no máximo pode ser n-1, mas ok, isso não interessa aqui).
Quando vc faz remove(n) o linked list não itera do principio até n. ele começa pelo fim !!! logo ele não iterou coisa nenhuma
no máximo ele itera n/2.

Sim, matemáticamente O(n/2) = O(n), mas esse não é o ponto.
O ponto é que depende do indice que vc procura e não de quantos elementos tem na lista remove(0) é o mesmo que removeFirst() e removeLast() é o mesmo que remove(n). Para que LinkeList seja util a performance destes métodos com este parametros têm que ser igual. Esse é todo o ponto de ter uma lista duplamente encadeada.

Não preciso saber de nada além de inglês para ler o javadoc , nem nada além de java para ler os fontes das duas classes.
Quem tb souber vai chegar na mesma conclusão. Não é arrogancia nem pretensão dizer o que é correto. arrogancia é estar enganado e continuar batendo no problema. Eu sei que não estoi enganado, tenho o javadoc e o codigo para provar tudo o que eu disse. Tenho até os testes de rapidez que muitos já fizerem. Fatos.
No campo da literatura tem o Effective Java, que trata directamente este assunto. E no campo teorico sei a diferença entre rapidez e performance e a analise lógica.
Eu não tenho culpa do que sei. Tenho responsabilidade em transmitir o que sei. E não fico transmitindo coisa errada por ai. Poderia citar exemplos do que é coisa errada transmitida pelos senhores que dizem que estou errado. Vocês já fizeram uma declaração publica do vossos erros ? erros que confundem muita genta até hoje … eu estouha anos emendando o problema que vcs causaram e não me queixo.

Menos frescura e mais profissionalismo.
Se vc me considera junior, ignore o que eu digo. Se está preocupado com o eu digo de errado. Corriga. Mas corriga o que eu disse e não a mim.

O problema é que vcs não conseguiram corrigir o que eu disse e partem para o ataque pessoal. Isso que é triste.

Ja me arrependo de ter colaborado consigo na segunda-feira.
Tava melhor quando eu deixava vcs enganar as criancinhas… enganem-as então.

bem, tinha pedido testes aqui, mas eu encerro minha participacao, deixando claro que considero muito o taborda em design e arquitetura, mas nao concordo com ele nessa thread em especifico (pra ficar claro que nao é ad hominem), onde fala da notacao O.

Calma ai , antes de você encerrar tal participação para o tópico é necessário agradecer ao Sergio Taborda por extraordinária colaboração e produção de informação ao GUJ, muitas pessoas iriam ter que recorrer a muitas literaturas para ter essa rica e magnifico embate de idéias.

Não concordar faz parte, e é o que acrescenta para chegarmos todos juntos aqui, no que vale para todos, aprender com os mais experientes e grandes profissionais, eu considero a todos assim como eu quero que todos me considerem.

Obrigado a todos,

Quero agradecer a Todos e em especial ao grande amigo, Sergio Taborda.

Pois é, eu confesso que tive de recorrer a muita literatura (TAOCP, CLR, Introduction to Algorithms) para saber bem que add(obj, i) e remove(i) de arraylist e linkedlist é O(n) (isso é, linkedlist nao é pior computacionalmente), tem gente que nem precisou de literatura, bastou olhar o codigo, e mesmo sem parecer conhecer da notacao O, chegou a conclusoes diferentes de qualquer livro de ciencia da computacao.

Sem duvida Duran. Faz parte. E que quem le que tire suas conclusoes e faca sua propria pesquisa, assim como voce mesmo fez seus testes. Esta de parabens.

E agradeco a voce, e peco perdao de ter desviado o topico para teoria da computacao, em vez de design e interfaces.

Sem duvida Duran. Faz parte. E que quem le que tire suas conclusoes e faca sua propria pesquisa, assim como voce mesmo fez seus testes. Esta de parabens.

E agradeco a voce, e peco perdao de ter desviado o topico para teoria da computacao, em vez de design e interfaces.

Precisamos de todos, e novamente quero agradecer vossas colaborações, “também não esqueci dos livros que vou indicar na comunidade Java livros”

É isso ai !!!,
abraços a todos

E o pior é que parece que todos aqui, incusive eu e o Taborda, concordamos com o inicio da discussao, que é a de interfacear e usar o tipo mais generico (qdo possivel) e nunca usar diretamente a implementacao. ai o topico degringolou por minha culpa, faço o mea culpa novamente.

Não seria uma boa mudar o nome do tópico, pra refletir melhor o que foi discutido aqui.