Array

Conceito

Um array é um bloco contíguo de elementos do mesmo tipo e mesmo tamanho. Toda propriedade dele decorre disso.

O endereço do elemento i é base + i * tamanho(T) — uma multiplicação e uma soma. É por isso que acesso por índice é O(1): não há busca, há aritmética.

Da contiguidade também decorrem as limitações:

• inserir/remover no meio é O(n) — não existe espaço entre elementos, então tudo depois precisa deslocar.
• o tamanho é fixo — o bloco vizinho pertence a outra coisa.

Array dinâmico (vector, ArrayList, slice) resolve o tamanho fixo mantendo capacidade maior que o comprimento. Quando enche, aloca um bloco maior e copia tudo. Se o crescimento for geométrico (dobrar, ou ×1,5), inserir no fim é O(1) amortizado; se for aditivo (cap+1), é O(n) amortizado — a escolha do fator é o que faz a estrutura funcionar.

A propriedade que a teoria não menciona e a prática cobra: localidade de cache. A memória não é lida byte a byte, é lida em linhas de cache (tipicamente 64 bytes). Percorrer um array traz vizinhos úteis a cada leitura. É a razão de o array vencer a lista ligada em quase todo benchmark real, inclusive em operações onde a lista é teoricamente melhor.

Em Go

Go é uma das poucas linguagens mainstream que te dá os dois explicitamente, com tipos distintos:

O slice é um header de três campos: ponteiro para o array de trás, len, cap. Isso já foi explorado em 3. Passagem por Valor vs por Referência.

s := make([]int, 3, 10) // len=3, cap=10

Crescimento: até 256 elementos a capacidade dobra. Acima disso, o incremento é cap/4 + 192 elementos, depois arredondado para a classe de tamanho do alocador (Go 1.18+).

O "cresce 1,25× acima de 256" que se repete em toda parte é impreciso: por causa do +192 e do arredondamento, o fator real é ≈2,03× em cap 300, 1,54× em 1.000, 1,33× em 10.000, e só chega a 1,250× perto de 1 milhão. Meça, não confie no número decorado — o exemplo abaixo imprime os fatores reais.

Se você sabe o tamanho final, make([]T, 0, n) elimina todas as realocações — é a otimização de melhor retorno em Go.

Ferramentas: copy(dst, src) (usa memmove, constante mínima), slices.Clone, clear(s), e o idioma s = s[:0] para reusar o array sem realocar.

Bounds check: todo acesso é verificado em runtime — panic: index out of range. O compilador elimina a checagem quando consegue provar que o índice é seguro (bounds check elimination), e é por isso que for i := range s costuma gerar código melhor que for i := 0; i < len(s); i++ com aritmética no índice.

Respostas às perguntas-guia

1. Por que acesso por índice é O(1)? O que a contiguidade em memória tem a ver?

Conceito: porque o endereço é calculado, não procurado: base + i*tamanho. Isso só é possível porque os elementos são contíguos e do mesmo tamanho.

Em Go: vale para [N]T e []T. No slice há uma indireção a mais (ler o ponteiro do header), ainda O(1).

2. O que acontece quando um array dinâmico enche — e por que inserir é O(1) amortizado?

Conceito: aloca um bloco maior, copia, libera o antigo. Amortizado O(1) porque o crescimento é geométrico: cada realocação de custo n é precedida por ~n inserções baratas que a pagam.

Em Go: 2× até 256 elementos, ~1,25× depois. append devolve um novo header — por isso s = append(s, v) e nunca só append(s, v).

3. Por que inserir no meio é O(n)?

Conceito: não há espaço livre entre elementos; abrir espaço significa deslocar todos os posteriores.

Em Go: o idioma é slices.Insert(s, i, v), que faz exatamente esse deslocamento. Se você insere no meio com frequência, a estrutura está errada.

4. Quando localidade de cache faz um array vencer uma estrutura "melhor" no papel?

Conceito: quase sempre que a operação envolve percorrer. Cache miss custa ~100× uma comparação, então a estrutura com melhor localidade ganha mesmo com complexidade pior.

Em Go, isso é agravado porque []*T (slice de ponteiros) espalha os dados pelo heap — você perde a localidade que o slice te daria. []T (slice de valores) mantém tudo contíguo. A diferença entre []Point e []*Point é medível e grande.

Trade-offs

Do conceito:

• Contiguidade compra O(1) e localidade; cobra custo de inserção no meio e realocação.
• Crescimento geométrico compra amortização; cobra memória desperdiçada (até metade da capacidade pode estar vazia) e picos de uso durante a cópia.
• Array de tamanho fixo compra previsibilidade total; cobra flexibilidade.

Em Go:

• Slice é barato de passar e esconde o aliasing do array de trás.
• []T vs []*T é uma decisão de performance real, não estilo: valores dão localidade, ponteiros dão indireção e pressão de GC.
• Não pré-alocar quando você sabe o tamanho é desperdício gratuito.

Exemplo prático

package main

import "fmt"

func main() {
	// array: tamanho no tipo, cópia por valor
	var a [3]int = [3]int{1, 2, 3}
	b := a
	b[0] = 99
	fmt.Println(a, b) // [1 2 3] [99 2 3] — independentes

	// slice: header, cópia rasa
	s := []int{1, 2, 3}
	t := s
	t[0] = 99
	fmt.Println(s, t) // [99 2 3] [99 2 3] — mesmo array

	// crescimento: dobra até 256; acima disso, cap/4+192 arredondado
	var g []int
	anterior := 0
	for i := 0; i < 2000; i++ {
		g = append(g, i)
		if cap(g) != anterior {
			if anterior != 0 && (cap(g) < 300 || cap(g) > 1000) {
				fmt.Printf("len=%-5d cap %d -> %d (fator %.2f)\n",
					len(g), anterior, cap(g), float64(cap(g))/float64(anterior))
			}
			anterior = cap(g)
		}
	}

	// pré-alocar elimina toda realocação
	pre := make([]int, 0, 2000)
	c0 := cap(pre)
	for i := 0; i < 2000; i++ {
		pre = append(pre, i)
	}
	fmt.Println("realocou?", cap(pre) != c0) // false
}

Relacionado

• 3. Lista Ligada — o mesmo contrato sem contiguidade
• 4. Pilha e 5. Fila — construídas sobre array na prática
• 3. Passagem por Valor vs por Referência — semana 1, o header de 24 bytes
• 1. Notação Big-O — de onde vem "amortizado"

Parte de Semana 02 - Estruturas de Dados I · 00 - MOC Fundamentos de Programação