Arrays & Strings
O que são Arrays? (Explicação Completa)
Arrays são blocos de memória contínuos que armazenam elementos do mesmo tipo. Pense neles como fileiras de gavetas numeradas:
ARRAYS SÃO COMO GAVETAS EM FILEIRA
Gaveteiro (Memória RAM):
[0] [1] [2] [3] [4] [5] [6] [7] ...
↑
Cada gaveta tem um número (índice)
Características importantes:
• Todas as gavetas têm o MESMO tamanho
• Você sabe exatamente onde cada gaveta está (número = posição)
• Para acessar a gaveta 5, você vai direto lá — sem procurar!
Por que o mesmo tamanho? Porque assim a CPU pode calcular a posição exata de qualquer elemento instantaneamente. Se cada gaveta tivesse tamanho diferente, teria que verificar cada uma até encontrar.
Como Arrays Funcionam na Memória RAM
Quando você escreve int arr[5] = {10, 20, 30, 40, 50}, o sistema faz o seguinte:
PASSO 1: Entender os tipos de dados
TIPO TAMANHO POR QUE?
byte 1 byte 8 bits = 0 a 255
short 2 bytes +/- 32.000
int 4 bytes +/- 2.1 bilhões (2³² valores)
long 8 bytes +/- 9.2 sextilhões (2⁶⁴ valores)
float 4 bytes IEEE 754 single precision
double 8 bytes IEEE 754 double precision
char 2 bytes Unicode (pode representar qualquer letra)
boolean 1 byte true ou false
reference 8 bytes Endereço de memória (em sistemas 64-bit)
PASSO 2: Calcular o espaço necessário
int arr[5] = {10, 20, 30, 40, 50}
↑
Um int ocupa 4 bytes (veja a tabela acima!)
5 elementos × 4 bytes = 20 bytes de memória alocados
PASSO 3: Visualizar na memória RAM
Quando o programa executa "int arr[5] = {10, 20, 30, 40, 50}":
MEMÓRIA RAM (256 GB de exemplo)
Endereço 0x1000 0x1004 0x1008 0x100C 0x1010 ...
Valor 10 20 30 40 50
(4B) (4B) (4B) (4B) (4B)
[0] [1] [2] [3] [4]
Por que 0x1000, 0x1004, 0x1008...?
↑ ↑
0x1000 é o endereço do PRIMEIRO elemento.
Cada int ocupa 4 bytes, então:
• arr[0] está em 0x1000 (endereço base)
• arr[1] está em 0x1000 + 4 = 0x1004
• arr[2] está em 0x1000 + 8 = 0x1008
• arr[3] está em 0x1000 + 12 = 0x100C
• arr[4] está em 0x1000 + 16 = 0x1010
A fórmula mágica: Para acessar arr[i], a CPU calcula: endereço = endereço_base + (i × tamanho_do_elemento)
Exemplo: Acessar arr[3]
endereço = 0x1000 + (3 × 4)
= 0x1000 + 12
= 0x100C ← Vá direto para este endereço!
Resultado: 40
Isso é O(1) — tempo CONSTANTE, não importa se o array tem 5 ou 5 milhões
de elementos. A CPU faz apenas UMA multiplicação e UMA soma!
Por Que "int" Tem 4 Bytes? (Aprofundamento)
Esta é uma das perguntas mais importantes que você pode fazer!
Um "int" (integer) representa números inteiros. Quantos valores diferentes
um int pode representar?
4 bytes = 32 bits = 2³² combinações possíveis = 4.294.967.296 valores
32 BITS = 2³² = 4.294.967.296 VALORES
Se usarmos apenas positivos (sem sinal):
Range: 0 até 4.294.967.295
Se usarmos positivos E negativos (com sinal, o mais comum):
Range: -2.147.483.648 até +2.147.483.647
Como funciona o "sinal"?
O primeiro bit indica se é positivo ou negativo:
01111111111111111111111111111111 = +2.147.483.647 (maior valor)
10000000000000000000000000000000 = -2.147.483.648 (menor valor)
↑
Este bit indica sinal (0 = positivo, 1 = negativo)
Por que não 3 bytes (24 bits)?
• 24 bits = 16.777.216 valores (apenas 16 milhões)
• Não é "redondo" para potências de 2 de forma eficiente
Por que não 8 bytes (64 bits)?
• Seria possível, mas desperdiçaria RAM
• A maioria dos programas não precisa de números tão grandes
• Padrão histórico da IBM: 4 bytes se tornou universal
Cache-Friendly: Por Que Arrays São Rápidos? (Deep Dive)
CPUs modernas têm memória cache — uma RAM ultra-rápida mas pequena integrada no processador. Entenda por que isso muda tudo:
HIERARQUIA DE MEMÓRIA DO SEU COMPUTADOR
Registradores da CPU (dentro do processador):
RAX 64 bits = 8 bytes — Acesso em ~0.3 nanosegundos (ns)
RBX Super rápido, mas muuuito pequeno!
RCX
↓
L1 Cache (por):
~32 KB por core Acesso em ~1 nanosegundo
Muuuito rápido, mas só cabe 32 KB!
↓
L2 Cache (por):
~256 KB por core Acesso em ~4 nanosegundos
Um pouco maior, um pouco mais lento
↓
L3 Cache (compartilhado):
~8-32 MB total Acesso em ~15 nanosegundos
Compartilhado entre todos os cores
↓
RAM (Memória Principal):
8-64 GB Acesso em ~100 nanosegundos
100x mais lento que L1!
↓
SSD:
1-4 TB Acesso em ~100.000 nanosegundos
1000x mais lento que RAM!
REGRA DE OURO: Cada nível é ~10x mais lento, mas ~10x maior!
Cache Lines: O Segredo da Velocidade
CPUs não buscam byte por byte da RAM. Elas buscam blocos de 64 bytes de uma vez. Esses blocos se chamam "cache lines".
O QUE É UMA CACHE LINE?
Quando a CPU precisa de 1 byte da RAM, ela carrega 64 bytes consecutivos!
Memória RAM:
bytebytebytebytebytebytebytebyte.....................
0 1 2 3 4 5 6 7 8 9 10 11 12 13
← 64 BYTES → ← PRÓXIMA CACHE LINE →
Se você acessa byte 0, a CPU carrega bytes 0-63 de uma vez!
POR QUE 64 BYTES?
• Experimentos empíricos mostram que 64 bytes é o "sweet spot"
• Maior = mais desperdício (dados não usados)
• Menor = mais overhead (mais requisições à RAM)
• É o padrão da indústria desde 2010 aproximadamente
EXEMPLO PRÁTICO: Acessando um array de inteiros
int arr[1000] = { ... }; // 1000 inteiros = 4000 bytes
// Loop que percorre o array sequencialmente:
for (int i = 0; i < 1000; i++) {
process(arr[i]);
}
O que acontece na CPU?
Iteração 1: Acessa arr[0]
1. CPU calcula: endereço = 0x1000 + (0 × 4) = 0x1000
2. Verifica L1 cache → NÃO ESTÁ AQUI (cache miss)
3. Verifica L2 cache → NÃO ESTÁ AQUI
4. Verifica L3 cache → NÃO ESTÁ AQUI
5. VAI ATÉ A RAM → Busca bytes 0x1000 a 0x103F (64 bytes = 16 ints!)
6. Carrega para L1 cache
7. Retorna arr[0]
TEMPO TOTAL: ~100 nanosegundos (uma eternidade para a CPU!)
Iterações 2-16: Acessa arr[1], arr[2], ... arr[15]
JITOOOO! Todos já estão no cache L1!
Acesso em ~1 nanosegundo cada!
100x mais rápido que o primeiro acesso!
Iteração 17: Acessa arr[16]
arr[16] está no endereço 0x1000 + (16 × 4) = 0x1040
Este é o PRIMEIRO BYTE da PRÓXIMA cache line!
→ Cache miss novamente → busca mais 64 bytes → lento!
RESULTADO: O loop é MUITO mais rápido do que parece!
Localidade Temporal vs. Espacial
Existem dois princípios que fazem os programas serem rápidos ou lentos:
LOCALIDADE TEMPORAL (Temporal Locality)
"Dados acessados recentemente tendem a ser acessados novamente."
Exemplo: Loop que soma elementos de um array
total = 0
for i in range(1000): # ← i é "reusado" 1000x!
total += arr[i] # ← arr[i] pode estar no cache
A variável 'i' fica no registrador da CPU durante TODO o loop!
Acesso: ~0.3 nanosegundos
LOCALIDADE ESPACIAL (Spatial Locality)
"Dados em endereços próximos tendem a ser acessados juntos."
Exemplo: Array de inteiros (cada int = 4 bytes)
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Quando você acessa arr[0], a CPU carrega:
bytes 0-63 da memória (16 inteiros: arr[0] até arr[15])
Então quando você acessa arr[1], arr[2], arr[3]...
→ JÁ ESTÃO NO CACHE! Acesso ultra-rápido!
MAS e se você acessasse arr[1000]?
→ Não está no cache! Precisa buscar da RAM novamente!
Arrays vs. Linked Lists: A Comparação Final
Agora você entende POR QUE arrays são mais rápidos para iteração:
ARRAY (Memória Contígua)
Endereço: 0x1000 0x1004 0x1008 0x100C 0x1010
Valor: 10 20 30 40 50
CONTÍGUO! UM BLOCO SÓ!
Percorrer array:
for i in range(1000):
x = arr[i] # Endereço: base + i*4 → direto!
16 elementos por cache line (64 bytes / 4 bytes)
A CPU "sabe" onde está o próximo elemento
Prefetching funciona: CPU antecipa e carrega dados
100 iterações ≈ 7 cache misses + 1600 hits!
LINKED LIST (Memória Esparramada)
Cada nó está em um lugar diferente da memória!
Dado: 10 Dado: 20 Dado: 30
Próximo Próximo Próximo
0x5000 0x9000 NULL
0x1000 0x5000 0x9000
↑ ↑ ↑
Tão perto... Longe demais! Longe demais!
Percorrer linked list:
node = head
while node: # ← Para CADA nó...
x = node.value # Acesso direto ao valor
node = node.next # ← SEGUE PONTEIRO!
# A CPU NÃO sabe onde está o próximo!
Cada nó pode estar em qualquer lugar da memória
A CPU NÃO sabe onde está o próximo nó
NÃO dá para fazer prefetching (CPU não consegue prever)
100 iterações = até 100 cache misses!
Resumo: Complexidade de Arrays
OPERAÇÕES EM ARRAYS
OPERAÇÃO COMPLEXIDADE POR QUE?
Acessar por[i] O(1) Fórmula direta: base + i*4
Buscar valor O(n) Precisa verificar cada elemento
Inserir no início O(n) Empurrar todos os outros para frente
Inserir no fim O(1) amort. Espaço já alocado, só colocar
Inserir no meio O(n) Mover elementos após a posição
Deletar no início O(n) Mover todos os outros para trás
Deletar no fim O(1) Só remover o último
Deletar no meio O(n) Mover elementos após a posição
O(1) amortizado? O que significa?
Arrays dinâmicos (como em Python/JavaScript) começam pequenos
e dobram de tamanho quando ficam cheios.
A cada "dobro", você copia todos os elementos para o novo array.
Isso é O(n) uma vez, mas não acontece sempre.
Ao longo de n inserções, o custo total é:
n + n/2 + n/4 + n/8 + ... = 2n
Então cada inserção média é O(2n/n) = O(1)!
Isso se chama "análise amortizada" — o custo MÉDIO por operação.
Exemplo do Mundo Real: Por Que Isso Importa?
CENÁRIO: Você está fazendo um site de e-commerce com 1 milhão de produtos.
Cada produto tem:
- Nome (50 caracteres)
- Preço (float de 8 bytes)
- Estoque (int de 4 bytes)
- ID (int de 4 bytes)
Total: ~66 bytes por produto = 66 MB de dados
OPÇÃO 1: Array de structs (memória contígua)
struct Product { int id; char name[50]; float price; int stock; };
Product products[1000000]; // Array na memória
for (int i = 0; i < 1000000; i++) {
if (products[i].id == target_id) { // ← O(1) por comparação
return products[i]; // 16MM comparções
} // 1M * O(1) = 1M operações
}
Cache hits: ~99% dos acessos!
Tempo: ~10 milissegundos (muito rápido!)
OPÇÃO 2: Lista encadeada de ponteiros
struct Node { Product* product; Node* next; };
Node* head = load_products_from_database();
for (Node* curr = head; curr != NULL; curr = curr->next) {
if (curr->product->id == target_id) { // ← Segue ponteiros
return curr->product;
} // 1M * possíveis cache misses
}
Cache hits: ~0.1% (cada nó está em lugar diferente)
Tempo: ~10 SEGUNDOS (1000x mais lento!)
CONCLUSÃO: A diferença é de 10ms vs 10 segundos para a mesma operação!
Problemas Essenciais
Maximum Subarray (Kadane)
Medium
Encontre o subarray contíguo com maior soma.
Resolver no LeetCode →
Product of Array Except Self
Medium
Produto de todos exceto o próprio, sem divisão.
Resolver no LeetCode →Hash Maps (Dictionaries)
O que são Hash Maps? (Explicação Completa)
Hash Maps são estruturas de dados que armazenam pares chave → valor e permitem busca extremamente rápida. Pense neles como um dicionário de Português:
HASH MAPS SÃO COMO DICIONÁRIOS
Em um dicionário físico (como Aurélio):
"CACHORRO"
Substantivo masculino.
Mamífero carnívoro da família dos canídeos...
↑
Para encontrar a definição de "cachorro", você não lê
todas as palavras! Você vai direto para a letra "C"!
Em um Hash Map:
key: "cachorro" → value: "mamífero carnívoro..."
↑
Para encontrar o valor, você NÃO procura em todos os elementos!
Você calcula ONDE ele deveria estar.
Diferença crucial para arrays:
• Array: busca por ÍNDICE numérico (arr[5]) → O(1)
• Hash Map: busca por CHAVE arbitrária ("nome") → O(1)
A Função Hash: Como Funciona? (Deep Dive)
A função hash é o "cérebro" do Hash Map. Ela transforma qualquer chave em um número que determina onde guardar o valor.
O QUE É UMA FUNÇÃO HASH?
Uma função hash pega um input (string, número, etc.) e retorna
um número (chamado de "hash code" ou "digest").
Propriedades desejáveis:
Mesmo input → Mesmo output (consistente)
Outputs uniformes (distribuídos no range)
Rápida de calcular
Não invertible (não dá para voltar ao input original)
EXEMPLO SIMPLES:
// Função hash "horrível" (só para entender):
function hash(key):
return length(key) // "cachorro" → 8
Problema: "gato" e "cao" retornam 4! Colisão!
// Função hash melhor:
function hash(key):
total = 0
for char in key:
total += ord(char) // ord() = código ASCII
return total % 16 // resto da divisão por 16
"gato" → 103+97+116+111 = 427 → 427 % 16 = 11
"cao" → 99+97+111 = 307 → 307 % 16 = 3
HASH EM JAVA (como realmente funciona)
A JDK usa esta fórmula (simplificada):
hashCode = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
Onde s[i] é o código ASCII do caractere.
EXEMPLO: hashCode de "abc"
'a' = 97, 'b' = 98, 'c' = 99
hash = 97 * 31² + 98 * 31¹ + 99 * 31⁰
= 97 * 961 + 98 * 31 + 99
= 93117 + 3038 + 99
= 96254
Depois, para encontrar o índice no array interno:
index = hashCode % tamanho_do_array
EXEMPLO: array de 16 posições
index = 96254 % 16 = 14
Então "abc" fica guardado na posição 14!
O Processo Completo: Inserir e Buscar
INSERIR: map.put("nome", "Alice")
PASSO 1: Calcular hash da chave "nome"
hashCode("nome") = 110*31² + 111*31¹ + 101*31⁰
= 110*961 + 111*31 + 101
= 105710 + 3441 + 101
= 109252
PASSO 2: Determinar índice (ex: array de 16 posições)
index = 109252 % 16 = 4
PASSO 3: Guardar na posição 4
...
0 1 2 3 4 5 6
[("nome", "Alice")]
Tempo total: ~1 nanosegundo!
BUSCAR: map.get("nome")
PASSO 1: Calcular hash de "nome" → 109252
PASSO 2: Calcular índice → 109252 % 16 = 4
PASSO 3: Ir direto para a posição 4 → ["nome", "Alice"]
TEMPO: O(1)! Sem procurar em todos os elementos!
Colisões: O Problema Fundamental
Quando duas chaves diferentes geram o mesmo índice, temos uma colisão. Isso é inevitável (princípio da pigeonhole)!
POR QUE COLISÕES ACONTECEM?
Imagine um array de 10 posições:
Index: 0 1 2 3 4 5 6 7 8 9
Se você tem 1000 chaves diferentes e só 10 posições...
Alguma posição VAI ter mais de uma chave! (Princípio da pigeonhole)
Exemplo:
hash("apple") % 10 = 3
hash("banana") % 10 = 3 ← MESMO ÍNDICE! Colisão!
MÉTODOS DE RESOLUÇÃO DE COLISÃO
MÉTODO 1: Separate Chaining (encadeamento separado)
Cada posição do array contém uma LISTA (ou lista encadeada)
0 1 2 3 4
→ [key: "apple", val] → [key: "grape",
→ [key: "banana", val: "grape"]
val: "banana"]
Busca: hash → índice → percorre lista no índice
Complexidade: O(1) amortizado, O(n) no pior caso
MÉTODO 2: Open Addressing (endereçamento aberto)
Quando há colisão, procura a PRÓXIMA posição livre
0 1 2 3 4 5 6 7
↑ ↑
"banana" "apple" (colidiu, foi para 4)
estava 3 não cabe em 3, foi para 4
Estratégias de busca:
• Linear: índice+1, índice+2, índice+3...
• Quadratic: índice+1², índice+2², índice+3²...
• Double hashing: hash1(key), hash2(key), usar ambos!
Load Factor e Quando Dobrar
Hash Maps modernos são dinâmicos — começam pequenos e crescem conforme necessário.
LOAD FACTOR: A RAZÃO CRÍTICA
Load Factor (α) = número de elementos / número de posições
Exemplo: array de 16 posições com 12 elementos
Load Factor = 12 / 16 = 0.75 (75%)
α = 0.75 = 75% das posições ocupadas
← 75% cheio!
A PARTIR DAQUI: COLISÕES MUITO FREQUENTES!
QUANDO DOBRAR?
A maioria das implementações dobra quando α atinge 0.7 ou 0.75:
16 → 32 → 64 → 128 → 256 → 512 → 1024...
Por que não deixar α crescer indefinidamente?
• α = 0.9 → 90% cheio → muitas colisões → O(n) em vez de O(1)!
• α = 0.5 → 50% cheio → poucas colisões → O(1) consistente
COMPLEXIDADE: O(1) AMORTIZADO
HashMap em JavaScript/Python faz n inserções:
Inserção 1: hash → índice, coloca, α = 1/16 = 6%
Inserção 2: hash → índice, coloca, α = 2/16 = 12%
...
Inserção 12: hash → índice, coloca, α = 12/16 = 75%
Inserção 13: α > 0.75 → DOBRA! Copia 13 elementos, α = 13/32 = 40%
...
Inserção 25: α > 0.75 → DOBRA! Copia 25 elementos, α = 25/64 = 39%
Custo de cada inserção:
• Inserção normal: O(1)
• Dobrar array: O(n) para copiar TODOS os elementos
Mas dobrar acontece cada vez menos frequentemente:
n + n/2 + n/4 + n/8 + ... = 2n
Custo total para n inserções = O(2n) = O(n)
Custo por inserção = O(n)/n = O(1) amortizado!
Exemplos do Mundo Real
ONDE HASH MAPS SÃO USADOS?
1. DATABASE CACHING (Redis)
Redis é basicamente um Hash Map distribuído!
SET user:123:profile '{"name": "Alice", "age": 30}'
↑
key: "user:123:profile"
value: '{"name": "Alice", "age": 30}'
GET user:123:profile → O(1) para buscar!
2. COMPILADORES (verificação de variáveis)
Quando o compilador vê "x = 5", ele verifica:
symbol_table["x"] = { tipo: int, escopo: global, endereco: 0x100 }
Busca: O(1)! Não precisa procurar em todas as variáveis!
3. CONTAGEM DE PALAVRAS (word frequency)
texto = "o gato comeu o peixe e o gato dormiu"
freq["o"] = 3 → "o" aparece 3 vezes
freq["gato"] = 2 → "gato" aparece 2 vezes
freq["comeu"] = 1 → "comeu" aparece 1 vez
Algoritmo O(n) para texto de n palavras!
4. DETECÇÃO DE DUPLICATAS
Existe algum número repetido em [1, 2, 3, 4, 2, 5]?
seen = {}
for num in array:
if seen.get(num): # O(1) lookup
return True # Duplicata encontrada!
seen[num] = True
return False
Tempo: O(n), Espaço: O(n)
Resumo: Complexidade de Hash Maps
OPERAÇÕES EM HASH MAPS
OPERAÇÃO MÉDIA PIOR CASO POR QUE?
Insert O(1) O(n) Colisões em excesso
Delete O(1) O(n) Localizar → deletar
Search/Lookup O(1) O(n) Hash → índice → valor
Get all keys O(n) O(n) Precisa iterar todos
Get all values O(n) O(n) Precisa iterar todos
PIOR CASO ACONTECE QUANDO:
• Hash function ruim (não distribui bem)
• Muitas colisões na mesma posição
• Ataque dehash flooding (adversário conhece a hash)
CASO MÉDIO (bem projetado):
• Hash function distribui uniformemente
• Load factor < 0.7
• Poucas colisões
Problemas Essenciais
First Unique Character
Easy
Encontre o primeiro caractere único em uma string.
Resolver no LeetCode →Linked Lists (Listas Encadeadas)
O que são Linked Lists? (Explicação Completa)
Linked Lists são sequências de nós conectados por ponteiros. Cada nó guarda dois things: o dado e um "endereço" para o próximo nó.
LINKED LIST: TRENZINHO DE VAGÕES
Pense em um TREN:
→→→→→→→→→→→→→→→→→→→→→→
↑
Locomotiva (head) que puxa todos os vagões!
Em uma Linked List:
Dado: 5 → Dado: 3 → Dado: 8 → Dado: 1 → NULL
Next: → Next: → Next: → Next: →
↑ ↑ ↑ ↑
Nó (node) Nó (node) Nó (node) Nó (node)
Cada vagão (nó) contém:
• O passageiro (dado)
• Um ticket que diz "próximo vagão está na plataforma 0x50A0"
DIFERENÇA CRUCIAL PARA ARRAYS:
• Array: Vagões numerados 0, 1, 2, 3... são fixos em ordem
• Linked List: Vagões podem estar EM QUALQUER lugar!
Estrutura de um Nó na Memória
ESTRUTURA DE UM NÓ EM C
struct Node {
int data; // 4 bytes: o dado que você quer guardar
Node* next; // 8 bytes: ENDEREÇO do próximo nó (64-bit)
};
Este é o "ponteiro"!
Tamanho total de cada nó: 4 + 8 = 12 bytes (em sistemas 64-bit)
Na prática: alinhamento de memória → 16 bytes por nó
Representação na memória:
Nó 1 Nó 2 Nó 3
5 0x2000 → 3 0x5000 → 8 NULL
4B 8B 4B 8B 4B 8B
End: 0x1000 End: 0x2000 End: 0x5000
Memória Fragmentada vs. Contígua: O Problema Real
Esta é a parte mais importante para entender POR QUE arrays são mais rápidos!
ARRAY: MEMÓRIA ORDENADINHA
Quando você cria: int arr[5] = {10, 20, 30, 40, 50}
A memória aloca TUDO JUNTO, em sequência:
MEMÓRIA RAM
0x1000 0x1004 0x1008 0x100C 0x1010 0x1014 0x1018 0x101C
10 20 30 40 50 ?? ?? ??
→ DADOS SEGUINTES JÁ ESTÃO CARREGADOS!
TUDO NUM BLOCO SÓ! → 64 bytes (16 ints) cabem na cache line!
LINKED LIST: MEMÓRIA ESPARRAMADA
Cada nó alocado INDIVIDUALMENTE conforme necessário:
MEMÓRIA RAM
Área de dados do programa A:
?? ?? ?? ?? ?? ?? ?? ??
...outros programas, sistema operacional...
Área heap (onde nós são alocados):
10 0x5A 20 0x9F 30 NULL
End: 0x1000 End: 0x5A00 End: 0x9F00
PONTEIROS "SALTAM" pela memória!
Cada nó pode estar a MILES de bytes de distância!
Cache Miss em Profundidade: O Impacto Real
O QUE ACONTECE QUANDO VOCÊ SEGUE UM PONTEIRO?
PASSO 1: CPU acessa o primeiro nó (0x1000)
L1 Cache: MISS
L2 Cache: MISS
L3 Cache: MISS
RAM: PEGA bytes 0x1000 a 0x103F (64 bytes) → CARREGA PARA CACHE
TEMPO: ~100 nanosegundos (muito lento!)
CPU → L1 (1ns) → L2 (4ns) → L3 (15ns) → RAM (100ns)
PASSO 2: CPU lê o ponteiro (0x5A00) e acessa o próximo nó
L1 Cache: MISS (0x5A00 não está em 0x1000-0x103F)
L2 Cache: MISS
L3 Cache: MISS
RAM: PEGA bytes 0x5A00 a 0x5A3F → CARREGA PARA CACHE
TEMPO: ~100 nanosegundos DE NOVO!
Cada "salto" de ponteiro pode custar 100ns!
IMPACTO NA PERFORMANCE:
Array de 1000 inteiros:
• Acesso 1: 100ns (cache miss)
• Acessos 2-1000: ~1ns cada (cache hits!)
• TOTAL: ~1.1 microssegundos
Linked List de 1000 nós:
• Acesso 1: 100ns (cache miss)
• Acesso 2: 100ns (cache miss - próximo nó está longe!)
• Acesso 3: 100ns (cache miss...)
• ...
• TOTAL: ~100.000 microssegundos = 0.1 segundos!
DIFERENÇA: 100x mais lento!
Então Por Que Linked Lists Existem?
VANTAGENS DAS LINKED LISTS
VANTAGEM 1: Inserção no início é O(1)!
Para adicionar NOVO elemento no INÍCIO da lista:
Antes:
A → B → C → NULL
1. Criar novo nó: novo = Node(D)
2. Apontar novo para cabeça: novo.next = head
3. Atualizar cabeça: head = novo
Depois:
D → A → B → C → NULL
Tempo: O(1) — não precisa mover ninguém!
VANTAGEM 2: Inserção no meio sem mover elementos
Para inserir X depois de B:
Antes:
A → B → C → NULL
↑
Inserir X aqui
1. Criar nó X
2. X.next = B.next (aponta para C)
3. B.next = X (B agora aponta para X)
Depois:
A → B → X → C → NULL
↑
X inserido sem mover C!
Não precisa deslocar C, D, E... como no array!
VANTAGEM 3: Não precisa saber o tamanho antecipadamente
• Array: você precisa dizer o tamanho na criação
• Linked List: cresce conforme você adiciona
Comparação Completa: Arrays vs Linked Lists
COMPARAÇÃO DETALHADA
OPERAÇÃO ARRAY LINKED LIST VENCEDOR
Acesso arr[i] O(1) O(n) Array
Busca por valor O(n) O(n) Empate
Inserção no início O(n) O(1) Linked
Inserção no fim O(1) amort. O(1) se tem tail Empate
Inserção no meio O(n) O(1) + busca Linked *
Deleção no início O(n) O(1) Linked
Deleção no meio O(n) O(1) + busca Linked *
Iteração O(n) + cache O(n) + cache miss Array
Memória usada n × 4 bytes n × 16 bytes Array
Crescimentodinâmico Precisa realocar Cresce naturalmente Linked
* Depois de encontrar a posição (O(n))
QUANDO USAR CADA UM:
USE ARRAY QUANDO:
• Precisa acessar elementos por índice frequentemente
• Vai iterar por todos os elementos
• Sabe o tamanho máximo antecipadamente
• Memória é limitada
• Exemplo: armazenar pontuações de um jogo
USE LINKED LIST QUANDO:
• Precisa inserir/remover no início frequentemente
• Não sabe o tamanho máximo
• Insere/remover no meio raramente (mas busca é rara também)
• Exemplo: histórico de comandos undo/redo
Exemplo do Mundo Real: Por Que Não É Tão Ruim?
CASOS ONDE LINKED LISTS SÃO BOAS
1. UNDO/REDO em Editores (Photoshop, VS Code, etc.)
Edit1→Edit2→Edit3→Edit4→ NULL
↑ ↑ ↑ ↑
Undo Undo Undo Undo
• Você precisa adicionar NOVO estado quando usuário edita
• Você precisa remover do INÍCIO quando usuário dá undo
• Aulas operações são O(1)!
• Performance de cache não importa muito aqui (umas dezenas de nós)
2. MÚSICAS EM PLAYLIST (Spotify, YouTube Music)
Música → Música → Música → Música → ...
1 2 3 4
↑
Próxima música: next.next (muito rápido!)
• Adicionar música: O(1) se tiver ponteiro para posição atual
• Próxima música: next → O(1)
• Músicas são relativamente poucas (milhares, não milhões)
3. HASH MAP IMPLEMENTAÇÃO (JavaScript Map, Java HashMap)
Internamente, Hash Maps usam arrays para dados!
Mas quando há COLISÃO, usam linked lists (separate chaining):
0 1 2
→ [("apple", 5)] → [("banana", 3)]
↑
Colisão: apple e banana
têm o mesmo índice!
Guardados em linked list!
Problemas Essenciais
Stacks & Queues
Stack (LIFO - Last In, First Out)
Como uma pilha de pratos: o último que você coloca é o primeiro que tira.
4 ← top (próximo a sair)
3
2
1 ← bottom
push(4) → push(3) → push(2) → push(1)
↓
pop() retorna 1, pop() retorna 2...
Queue (FIFO - First In, First Out)
Como uma fila de banco: o primeiro que chega é o primeiro a ser atendido.
front → [1] [2] [3] [4] ← back
↓
(sai primeiro) (entra por aqui)
enqueue(1) → enqueue(2) → enqueue(3) → enqueue(4)
↓
dequeue() retorna 1, dequeue() retorna 2...
Casos de Uso
Stack:
- Undo/Redo functionality
- Parenthesis matching
- Function call stack
- DFS traversal
Queue:
- BFS traversal
- Task scheduling
- Print queue
- Message queues
Problemas Essenciais
Como a CPU Acessa Memória: Por Dentro do Computador
Hierarquia de Memória: Do Mais Rápido ao Mais Lento
CPUs modernas têm múltiplos níveis de memória, cada um com características diferentes:
HIERARQUIA DE MEMÓRIA (do mais rápido ao mais lento)
REGISTRADORES (dentro da CPU):
rax, rbx, rcx, rdx, rsi, rdi, r8, r9, r10... (16-32 registradores)
Tamanho: 64 bits = 8 bytes cada
Acesso: ~0.3 nanosegundos (super ultra rápido!)
Exemplo: "mov rax, 5" → coloca 5 no registrador rax
↓ 10x mais lento
L1 CACHE (Level 1):
~32 KB por core (ex: Intel i7 tem 32KB L1d + 32KB L1i)
Acesso: ~1 nanosegundo
Latência: 4 ciclos de clock (~0.7ns a 3.5GHz)
O que guarda: instruções e dados sendo usados AGORA
↓ 4x mais lento
L2 CACHE (Level 2):
~256 KB por core (alguns chips modernos têm 512KB ou 1MB)
Acesso: ~4 nanosegundos
Latência: ~12 ciclos de clock
O que guarda: dados recently acessados + código
↓ 4x mais lento
L3 CACHE (Level 3):
~8-32 MB (compartilhado entre todos os cores!)
Acesso: ~15 nanosegundos
Latência: ~40 ciclos de clock
O que guarda: blocos de memória Recently acessados
Exemplo: AMD Ryzen 9 tem 32MB L3 compartilhado
↓ 7x mais lento
RAM (MEMÓRIA PRINCIPAL):
8-64 GB (sistemas modernos)
Acesso: ~100 nanosegundos (0.1 microssegundos)
Latência: ~200 ciclos de clock
O que guarda: seu código, dados, sistemas operacionais
Tipo: DDR4 ou DDR5 (mais rápido = mais caro)
↓ 1000x mais lento!
SSD (ARMAZENAMENTO SÓLIDO):
256 GB - 4 TB
Acesso: ~0.1-1 milissegundos (100.000 nanosegundos)
Leitura sequencial: ~3-7 GB/s (NVMe)
Leitura aleatória: ~50.000-500.000 IOPS
↓ 10x mais lento!
HDD (DISCO RÍGIDO):
1-16 TB
Acesso: ~10 milissegundos (leitura aleatória)
Leitura sequencial: ~100-200 MB/s
POUCO USADO HOJE EM DIA (SSDs são melhores!)
REGRA DE OURO: Cada nível é ~10x mais lento, mas ~10x maior!
⏱ Por Que Isso Importa? Números Reais!
COMPARAÇÃO DE VELOCIDADE (dados de 2024)
Vamos supor que acessar RAM leva 1 SEGUNDO:
L1 Cache: 0.01 segundo (100x mais rápido)
L2 Cache: 0.04 segundos (25x mais rápido)
L3 Cache: 0.15 segundos (7x mais rápido)
RAM: 1 segundo (nosso baseline)
SSD NVMe: 15 segundos (15x mais lento)
HDD: 3 minutos (180x mais lento)
EXEMPLO PRÁTICO:
Se você acessar dados da RAM 1000 vezes:
• Tempo: 1000 × 100ns = 100.000ns = 0.1ms
Se você acessar dados do SSD 1000 vezes:
• Tempo: 1000 × 100.000ns = 100.000.000ns = 100ms = 0.1s
DIFERENÇA: 1000x!
CONCLUSÃO: Minimizar acessos à RAM (usar cache) = programas mais rápidos
Cache Lines: O Bloco Mágico de 64 Bytes
CPUs não buscam byte por byte da RAM. Elas carregam blocos de 64 bytes de uma vez. Isso se chama "cache line".
O QUE SÃO CACHE LINES?
Quando a CPU precisa de 1 byte, ela carrega 64 bytes consecutivos!
Endereço 0x1000 solicitado:
Bytes carregados para o cache:
[0x1000, 0x1001, 0x1002, 0x1003, ... até 0x103F] ← 64 bytes!
POR QUE 64 BYTES?
• Experimentos mostram que 64 bytes é o "sweet spot"
• Maior que 64 bytes = muito desperdício (dados não usados)
• Menor que 64 bytes = overhead muito alto (mais requisições)
• Padrão da indústria desde ~2010 (Intel, AMD, ARM)
O que Acontece Quando Você Acessa Memória?
A JORNADA DE UM ACESSO À MEMÓRIA
Código: int x = arr[5]; // arr está na RAM
PASSO 1: CPU calcula o endereço
endereço = base_address + (5 × 4 bytes) = 0x1014
PASSO 2: Verificar se o dado está no L1 cache
A CPU verifica: "O endereço 0x1014 está em alguma cache line?"
0x1014 está no range 0x1000-0x103F? SIM!
→ CACHE HIT! O dado está no L1!
→ Tempo: ~1 nanosegundo!
SE FOSSE CACHE MISS:
L1 MISS → Verificar L2 → Se miss → Verificar L3 → Se miss → RAM
L1: ~1ns → L2: ~4ns → L3: ~15ns → RAM: ~100ns
→ Total: ~120 nanosegundos (120x mais lento!)
Temporal vs. Spatial Locality: Por Que Seu Código É Lento
LOCALIDADE TEMPORAL (Temporal Locality)
"Dados acessados RECENTEMENTE tendem a ser acessados NOVAMENTE."
Exemplo RUIM (sem locality temporal):
// Processa arrays diferentes um por um
process(arrayA); // Usa arrayA
process(arrayB); // Usa arrayB
process(arrayC); // Usa arrayC
process(arrayD); // Usa arrayD
Cache de arrayA é descartado antes de reutilizar!
Exemplo BOM (com locality temporal):
for round in range(10):
process(arrayA); // Usa arrayA 10x!
Cada array é carregado uma vez, usado muitas vezes
LOCALIDADE ESPACIAL (Spatial Locality)
"Dados em ENDEREÇOS PRÓXIMOS tendem a ser acessados JUNTOS."
Exemplo RUIM (stride grande):
for (int i = 0; i < n; i += 1000) // Pula 4000 bytes!
x = arr[i];
A cada acesso, precisa buscar da RAM!
Exemplo BOM (acesso sequencial):
for (int i = 0; i < n; i++)
x = arr[i]; // arr[0], arr[1], arr[2]...
A cada 16 acessos, só 1 cache miss!
Prefetching: A CPU Prevendo o Futuro
PREFETCH: A CPU TENTA ADIVINHAR
CPUs modernas TENTAM prever quais dados você vai precisar:
1. STRIDE PREFETCHER (reconhece padrões)
for (int i = 0; i < 1000; i += 4) // Acessa 0, 4, 8, 12...
x = arr[i];
A CPU nota: "Stride de 4! Vou pré-carregar arr[4], arr[8]..."
Quando você acessa arr[4], os dados já estão no cache!
2. STREAM PREFETCHER (detecta acesso sequencial)
for (int i = 0; i < n; i++)
process(arr[i]); // Acesso sequencial!
A CPU pré-carrega arr[i+1], arr[i+2], arr[i+3]...
QUANDO PREFETCHING NÃO FUNCIONA:
for (int i = 0; i < n; i++) {
idx = random() % n;
x = arr[idx]; // Onde está o próximo? Ninguém sabe!
}
CPU não consegue prever endereços aleatórios!
Implicações Práticas Para Algoritmos
REGRAS DE OURO PARA PERFORMANCE
REGRA 1: Use arrays para iteração, não linked lists
ARRAY: Cache-friendly
for (int i = 0; i < n; i++) sum += arr[i];
// 1 cache miss a cada 16 elementos
LINKED LIST: Cache-hostile
for (Node* p = head; p != NULL; p = p->next)
sum += p->value;
// Potencial cache miss a cada elemento!
REGRA 2: Acesse dados em ordem, não pule endereços
BOM: for (int i = 0; i < n; i++) arr[i]
RUIM: for (int i = 0; i < n; i += 1000) arr[i] // Pula muito!
REGRA 3: Blocking/tiling para algoritmos pesados
Matrix multiplication naive: gera muitos cache misses
Com blocking: processa blocos que cabem no cache
// Pode ser 5-10x mais rápido!
Exemplo do Mundo Real: Por Que Photoshop É Rápido?
PROCESSING DE IMAGEM: UM CASO DE ESTUDO
Imagem de 4000x3000 pixels = 12.000.000 pixels
Cada pixel RGB = 3 bytes
Total: 36 MB de dados
ABORDAGEM 1: Pixels como nós (Linked List?)
• Cada nó em lugar diferente da memória
• Para aplicar filtro: ~12.000.000 cache misses!
• Tempo: MINUTOS!
ABORDAGEM 2: Pixels como array contiguous
• Pixels armazenados em ordem: R,G,B,R,G,B,R,G,B...
• Para aplicar filtro: 36MB / 64 bytes = 562.500 cache misses (só!)
• Tempo: milissegundos!
Speedup: 100-1000x mais rápido!
CONCLUSÃO: A escolha da estrutura de dados impacta diretamente
a velocidade do programa em ORDENS DE GRANDEZA!