Arrays

Ler o milionésimo valor de um array leva um passo, mas pôr um valor novo na frente do mesmo array move um milhão de valores.

O que é uma estrutura de dados

Um programa que guarda uma lista de nomes, uma fila de trabalhos de impressão ou uma tabela de preços precisa armazenar esses dados em algum lugar, e precisa responder a perguntas sobre eles: qual é o terceiro item, este nome está na lista, qual trabalho vem depois? Uma estrutura de dados é um jeito de guardar dados junto com os métodos que respondem a essas perguntas. O curso 6.006 do MIT separa duas ideias aqui. A interface diz quais operações você pode pedir, como "pegar o item na posição i" ou "acrescentar um item no fim". A estrutura de dados é como essas operações são de fato executadas na memória. Uma interface pode ter várias estruturas de dados por trás, e elas podem diferir enormemente em velocidade.

Este curso conta passos, como o curso de algoritmos, para que duas estruturas possam ser comparadas sem cronômetro. Nesta unidade, um passo é ler ou escrever uma célula de memória. O laboratório abaixo conta os passos para você.

Um bloco de células, lado a lado

Um array guarda os seus valores num bloco contínuo de memória, cada valor numa célula do mesmo tamanho, numerada a partir de 0. É essa disposição que torna os arrays rápidos de ler. Se o bloco começa no endereço s e cada célula ocupa c bytes, então a[i] fica no endereço s + i × c. O computador calcula isso com uma multiplicação e uma adição e pula direto para lá, seja i igual a 3 ou a 3 000 000. As notas do MIT listam "get at(i)" e "set at(i, x)" de um array como Θ(1), o que quer dizer que o custo não cresce com o comprimento.

A mesma disposição deixa lentas as mudanças no meio. Suponha que o array guarde 7, 3, 9, 4, 6 e você queira o 1 na frente. Não há espaço na frente do 7, então todo valor precisa primeiro se mover uma célula para a direita, começando pelo último para nada ser sobrescrito. São 5 movimentos e 1 escrita: 6 passos. Remover o valor da frente é a imagem espelhada: ler o valor e depois mover os outros 4 valores uma célula para a esquerda. Inserir na posição i de um array de n valores custa n − i movimentos mais uma escrita, então a frente é o pior lugar e o fim é o melhor.

Quando o bloco está cheio

Um bloco de memória tem tamanho fixo, então o que acontece quando você acrescenta um valor e todas as células estão ocupadas? O array precisa pedir um bloco novo, maior, e copiar todos os valores para lá antes de poder escrever o novo. No laboratório, fazer push no bloco cheio de 5 custa 5 cópias e 1 escrita. Se o array crescesse só uma célula de cada vez, todo push copiaria tudo, e n pushes custariam cerca de n²/2 cópias.

A solução descrita nas notas do MIT é crescer bastante de uma vez, por exemplo dobrando. Começando da capacidade 1, as cópias acontecem quando o array tem 1, 2, 4, 8 e 16 valores, então 17 pushes custam 1 + 2 + 4 + 8 + 16 = 31 cópias no total, menos de 2 por push. Um push isolado ainda pode ser lento, mas qualquer sequência longa de pushes dá, em média, um custo constante por push. Isso se chama tempo Θ(1) amortizado. Um array de JavaScript se comporta assim visto de fora: o MDN descreve os arrays como redimensionáveis, e push e pop trabalham no fim, que é a ponta barata.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, um passo
a.push(8);              // barato: o fim
a.unshift(1);           // todo valor anda uma célula para a direita
console.log(a.join(" ")); // 1 7 3 9 4 6 8