Estive assistindo uma palestra do Bjarne Stroustrup do GoingNative2012, onde em uma parte da palestra ele diz que vetores sempre são melhores que listas e umas das principais causas é que os caches são muito bons com algo previsível como um Vetor e de fato ele ocupa menos espaço que uma lista.
Vocês concordam com isso?
Uma lista é uma estrutura complexa onde o programador se preocupa com a segurança dos dados, etc…
Um vetor é uma estrutura simples. Normal que tenha bem mais desempenho não!?
Como vetores são geralmente alocados sequencialmente na memória, é possível fazer o uso do princípio da localização espacial ao transferir dados da memória para a cache. O mesmo não ocorre com uma lista já que cada nó seu pode ocupar posições arbitrárias de memória.
Além disso, se um vetor está alocado em um bloco de memória que começa no endereço p e cada posição ocupa k palavras, encontrar a posição i é tão fácil quanto fazer a conta p + k *i. Ou seja, ele é encontrado em tempo constante e mais, cada posição não precisa armazenar o endereço da próxima, como ocorre com as listas.
Melhores em quê?
Acho que essa comparação entra muito no nível de conversa de “Eu uso short no lugar de int para economizar memória”. Só é válido quando você precisa fazer isso para o teu programa rodar decentemente num ambiente muito limitado, ou quando precisa tirar o máximo do máximo do hardware da máquina(como criar um servidor web para atender 10 mil clientes concorrentemente).
Agora para os outros 99.999% dos casos, o custo maior é o salário do desenvolvedor, quanto mais ele conseguir resolver com menor tempo de entrega com a ferramenta genérica que ele tem em mãos, melhor.
Melhor em desempenho e em consumo de memória.
Tomando que a interface de um vetor oferece todas as operações que a lista não entendo a que se referiu Bruno Laturner
Ele quis dizer que esse cara dessa palestra deveria se preocupar em falar algo diferente ao inves de falar a mesma ladainha de sempre e que nao leva a lugar nenhum. Lista é Lista e Vetor é Vetor, uma faz uma coisa que o outro nao faz, simples assim.
[quote=juliocbq]Uma lista é uma estrutura complexa onde o programador se preocupa com a segurança dos dados, etc…
Um vetor é uma estrutura simples. Normal que tenha bem mais desempenho não!?[/quote]
Não entendi bem ao que se refere quanto a segurança dos dados, não tinha conhecimento quanto a isso ainda, fale mais a respeito; iniciei a discussão pois o sempre utilizei listas em condições que deveria dar preferência a inclusões em posições pseudo-aleatórias e pelo que assisti ainda sim as listas não tem reais vantagens por conta da arquitetura atual dos computadores, os computadores atuais não são bons com referências indiretas.
Eis a grande questão o vetor faz tudo que a lista faz, mas de um modo diferente, a curva de complexidade das listas começam a ganhar vantagens por volta dos milhares de elementos, mas conforme o dito ainda nessa ordem as listas perdem para os vetores por conta da arquitetura atual dos computadores e o uso extensivo de cache.
Uhum, porém, imagino o seguinte. Vector implementa List, e a classe Vector é Synchronized, logo, acredito que essa performance não é tão perfeita, pois como é syncro, um acesso multi nela diminui sua performance, esse é o preço de uma classe thread-safe, seria bom esse palestrante mostrar como ele chegou a essa conclusão. Voce pode usar Vetores e Listas de diversas maneiras, e com certeza pra cada caso uma servira de forma especial, queria entender quais os testes ou sei la o que esse cara fez.
Perae, só para entrarmos em consenso, vetores = arrays, listas = listas ligadas?
Estava pensando em arrays e ArrayList.
Falo das estruturas de dados em si, vetores e listas ligadas, o palestrante é o criador da linguagem C++ onde ele fez comparações de computação com as operações básicas de ambas, ele realmente deixa clara a questão do thread-safe, mas também que o uso de múltiplos vetores suportando o trabalho em paralelo ainda é superior.
Em vetor eu consigo pegar um enumeration, na lista consigo pegar um iterator. O que pra mim isso é importante, uma vez que Vector é syncronyzed, eu corro o risco de um objeto esta sendo alterado e em outra thread o mesmo objeto tb estar sendo alterado, o que vai levar a um so lugar: ConcurrenceModificationException, fora que nao tem 100% de certeza que meus dados serao seguramente guardados sem nenhuma perda. No Iterator eu so posso ter uma single-thread, logo nao corro o risco de overwrite no meu objeto, e tb nao corro o risco da execao acima citada. Nao sei como C++ trata esse tipo de coisa.
Pessoal, a discussão é puramente sobre as estruturas de dados, não de alguma implementação específica de qualquer linguagem. David, pode disponibilizar o link da palestra?
Não fazz sentido discutir a estrura sem discutir a implementação.
Se discutir array vs LinkedList é a mesma coisa que discutir ArrayList vs LinkedList e isso já foi feito várias vez aqui no forum.
Não é verdade que os arrays são alocados em espaços de memoria em sequencia. Em java não é assim, embora em outras linguagens seja. Os indices do array em java não são “endereços de memoria” como em outras linguagens.
Logo aqui a plataforma e a linguagem mudam completamente o cenário. O List do C# por exemplo, que é equivalente ao ArrayList tem uma otimização muito diferente porque criar arrays em .net tem custos diferentes que em java. C# nem sequer em um equivalente ao LinkedList do java (tem uma classe LinkedList, mas ela não implementa a interface IList)
Discutir array vs linked sem olha a tecnolocia é apenas discutir se o get(n) é O(n) ou O(1). E se formos por ai, já sabemos que o linkedlist é melhor em certos cenários que o array. Dizer que o array é sempre melhor, é fútil. Porque simplesmente não é verdade.
A discussão chegou ao ponto de envolver enumerations, Vector e iteradores. É óbvio que a afirmação na palestra não envolve nada disso.
Desconhecia essa informação a respeito do Java. Você pode mostrar uma fonte oficial de onde tirou essa informação?
Não conheço nenhuma linguagem em que os indices são endereços de memória. Pode dar um exemplo?
A discussão está um nível abaixo de tudo isso. Envolve-se cache e o princípio de localização espacial. Estamos falando puramente de estruturas de dados armazenadas sequencialmente na memória ou de estruturas de dados que precisam armazenar endereços de memória.
Eu não vi o vídeo completo, não sei se ele falou “sempre”. Falou?
Entao ja começou errado, nao se pode ignorar a implementacao de tais estruturas.
[quote]
sergiotaborda wrote:
Os indices do array em java não são “endereços de memoria” como em outras linguagens.
Não conheço nenhuma linguagem em que os indices são endereços de memória. Pode dar um exemplo? [/quote]
Voce so fez afirmar o que ele disse.
Isso mesmo, por discutir um nivel abaixo da origem se comete alguns equivocos, e cache ? desde quando um método ou uma estrutura de dados implementa um cache ? O principio de cache se remete a um intermediador…
Eu compartilho da mesma opinião do Joshue Bloch. Segue um resumo:
[quote]Item 55 : Otimize criteriosamente
A historia das décadas passadas nos mostram que otimização prematura na verdade é mais propenso a causar danos do que benefícios. O caminho da otimização precoce pode leva-lo a uma solução que ainda não seja rápida, arquiteturalmente ruim e pior de tudo inflexível de difícil evolução. Portanto, não tente criar programas rápidos! Na verdade, foque em criar bons programas, usando todos os conceitos, princípios e abordagem necessários. Se um programa bem arquiteturado não for rápido suficiente, a boa arquitetura já estabelecida permitira que ele seja facilmente otimizado. Não pense em problemas de desempenho enquanto estiver projetando uma solução. Quando terminar a codificação, avalie seu desempenho. Se ele for suficientemente rápido, tudo estará resolvido. Caso contrário, localize a fonte de gargalo usando uma ferramenta de gerador de perfil e trabalhe nas partes relevantes. Repita esse processo conforme necessário, avaliando o desempenho após cada alteração até apresentar um tempo satisfatório.
[/quote]
Veja - http://fernandofranzini.wordpress.com/2012/08/07/java-efetivo-aprenda-realmente-a-programar-java/
[quote=FernandoFranzini]Eu compartilho da mesma opinião do Joshue Bloch. Segue um resumo:
[quote]Item 55 : Otimize criteriosamente
A historia das décadas passadas nos mostram que otimização prematura na verdade é mais propenso a causar danos do que benefícios. O caminho da otimização precoce pode leva-lo a uma solução que ainda não seja rápida, arquiteturalmente ruim e pior de tudo inflexível de difícil evolução. Portanto, não tente criar programas rápidos! Na verdade, foque em criar bons programas, usando todos os conceitos, princípios e abordagem necessários. Se um programa bem arquiteturado não for rápido suficiente, a boa arquitetura já estabelecida permitira que ele seja facilmente otimizado. Não pense em problemas de desempenho enquanto estiver projetando uma solução. Quando terminar a codificação, avalie seu desempenho. Se ele for suficientemente rápido, tudo estará resolvido. Caso contrário, localize a fonte de gargalo usando uma ferramenta de gerador de perfil e trabalhe nas partes relevantes. Repita esse processo conforme necessário, avaliando o desempenho após cada alteração até apresentar um tempo satisfatório.
[/quote]
Veja - http://fernandofranzini.wordpress.com/2012/08/07/java-efetivo-aprenda-realmente-a-programar-java/[/quote]
Penso exatamente assim mano, gostei da sua citação =D
Java é uma especificação. Nada na especificação diz que tem que ser continuo, ou não. Portanto, ha a opção de não ser.
Não é uma fonte oficial, mas é uma fonte com a mesma informação http://stackoverflow.com/questions/12431188/memory-allocation-in-array-of-java
[quote]
Eu não vi o vídeo completo, não sei se ele falou “sempre”. Falou?[/quote]
Se não for “sempre” então a discussão é “pointerless” 
Pois voltamos à velha array vs linked. E todo o mundo sabe que array é bom quando vc sabe o tamanho e tem acesso randômico, e linked no resto dos casos.
Vc vai implementar um stack ou uma fila com array ? não, né ?