Que mal há em implementar uma pilha usando um array?
[quote=Bruno Laturner]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.[/quote]
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.
[quote=sergiotaborda]
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. [/quote]
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
[quote=sergiotaborda]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]
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.
[quote=sergiotaborda]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é ?[/quote]
A stack do windows xp é um simples vetor de 8mb de memória.
[quote=rodrigo.bossini]
Que mal há em implementar uma pilha usando um array?[/quote]
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
[quote=wiki]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.[/quote]
[quote=juliocbq][quote=sergiotaborda]
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. [/quote]
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
[/quote]
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.