Arquivo Discussoes de Programacao e Tecnologia 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.
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!?
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.
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?
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:
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.
Eu compartilho da mesma opinião do Joshue Bloch. Segue um resumo: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.
Veja - http://fernandofranzini.wordpress.com/2012/08/07/java-efetivo-aprenda-realmente-a-programar-java/
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
Eu não vi o vídeo completo, não sei se ele falou “sempre”. Falou?
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é ?
Que mal há em implementar uma pilha usando um array?
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.
Não tem nada a ver o que você falou. São estruturas diferentes e cada uma tem seu uso distinto. Escrever uma fila onde apenas um vetor resolveria o problema impacta na qualidade do software. Dizer isso que você acabou de postar é não se preocupar com o produto final. Aí sim, o seu salário de programador pode custar o seu emprego.
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.
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
Esse link disse apenas que "na jvm array podem ser contínuos".
É verdade do ponto de vista do desempenho. Se você precisa de processamento linear.
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é ?
A stack do windows xp é um simples vetor de 8mb de memória.
Que mal há em implementar uma pilha usando um array?
Essa coisa de máquina virtual e linguagem orientada a objetos cria efeitos estranhos numa comunidade toda. Existem pessoas que preferem seguir um paradigma mesmo que isso custe a simplicidade de algo. Deixando claro que isso não se aplica ao sergiotaborda.
Efficiency
Both store and select take (deterministic worst case) constant time. Arrays take linear (O(n)) space in the number of elements n that they hold.
In an array with element size k and on a machine with a cache line size of B bytes, iterating through an array of n elements requires the minimum of ceiling(nk/B) cache misses, because its elements occupy contiguous memory locations. This is roughly a factor of B/k better than the number of cache misses needed to access n elements at random memory locations. As a consequence, sequential iteration over an array is noticeably faster in practice than iteration over many other data structures, a property called locality of reference (this does not mean however, that using a perfect hash or trivial hash within the same (local) array, will not be even faster - and achievable in constant time). Libraries provide low-level optimized facilities for copying ranges of memory (such as memcpy) which can be used to move contiguous blocks of array elements significantly faster than can be achieved through individual element access. The speedup of such optimized routines varies by array element size, architecture, and implementation.
Memory-wise, arrays are compact data structures with no per-element overhead. There may be a per-array overhead, e.g. to store index bounds, but this is language-dependent. It can also happen that elements stored in an array require less memory than the same elements stored in individual variables, because several array elements can be stored in a single word; such arrays are often called packed arrays. An extreme (but commonly used) case is the bit array, where every bit represents a single element. A single octet can thus hold up to 256 different combinations of up to 8 different conditions, in the most compact form.
Array accesses with statically predictable access patterns are a major source of data parallelism.
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.
Sérgio, um vetor sempre vai ser contínuo não importa a plataforma(do ponto de visto do programador). É uma "especificação" da estrututa. Algumas operações com vetores podem criar subvetores com endereços não contínuos. Mas a regra é. Vetor -> Contínuo
Ora, é ao contrário. Do ponto de vista do programador, o que ele tem são estruturas com regras. Arrays em java são de tamanho fixo, em VB não. Logo ai, uma estrutura que parecia a mesma, não tem o mesmo desempenho quando vc a usa num algoritmo.
Portanto, no frigir dos ovos sim é relevante a plataforma, as regras da estrutura naquela plataforma e como isso afeta o algortimo.
Isto vai ficar bem claro no java 8 com a introdução de streams de objetos. Parece que faz a mesma coisa que estamos habituados, mas hoje se vc tem uma lista de objetos A e quer fazer uma transformação para uma lista de objetos B vc precisa fazer um for
E vc precisa fazer um for, para cada tratamento que vc for dar a essa lista. Com Steams isto não é necessário. às vezes o for é iliminado completamente. E na maioria dos casos vc converte algoritmos complexo para O(N). em vez de O(k.N) ou O(N^k).
As estrutruas são muito mais importantes do que parece, e por isso que a primeira regra de OO é : use o tipo certo para o trabalho.
Mas as estrutruas não existem no vácuo. Existe toda uma plataforma e um conjunto de regras que precisam ser levadas em consideração. Portanto, sim importa se o array é continuo ou não. Em java muito provavelmente é, porque é uma questão de bom senso e simplicidade, mas isso não é obrigatório. Logo, não é garantido ao programador, que o array seja alocado continuamente na memoria. E o ponto é que, em java, isso é irrelevante. Mas não é irrelevante para a performance.
É como GC. Ele está nas especificação e toda a JVM tem que ter um, mas não necessáriamente eles são se comportar da mesma forma. A especificação não dá quaisquer garantias sobre o comportamento do GC, mas a implementação do GC é virtal para a performance.
Em geral, a performace está associada à real implementação e um pouco à eficiência do algortimo. A eficiencia é unica coisa que vc pode estudar abstratamente e saber que se o algoritmo é O(n) e o outro é O(N^2) , o primeiro é - em tese - melhor. Mas não será mais rápido se precisar de N multiplicações enquanto o outro precisa de N^2 somas.
Exato. “podem ser contínuos”, não é obrigatório Podem também não ser.
Por isso que programar em java e em C não é a mesma coisa. Em C ha preocupações muito mais baixo nível e assumpções que em java não são necessárias.