Lendo Código para Taxas de Crescimento
Revisão de Código para Correção vs Revisão de Código para Complexidade
Revisão de código para correção detecta erros de lógica: condições erradas, índices off-by-one, verificações nulas ausentes. Revisão de código consciente de complexidade detecta uma classe diferente de defect: código que funciona corretamente em N = 100 mas cresce catastroficamente em N = 100.000.
Esta lição se conecta a uma investigação mais profunda no curso unhamming: The Missing Chapter: Algorithmic Complexity aborda Big O no contexto de defects de produção, & MOAD-0001: The Sedimentary Defect mapeia o padrão em 60+ ecossistemas de software.
Duas Heurísticas de Revisão
Loops aninhados multiplicam a complexidade. Dois loops aninhados sobre N itens produzem O(N²). Três produzem O(N³). Ao revisar: conte primeiro a profundidade do aninhamento de loops.
Contêiner sequencial dentro de um loop quente. Qualquer verificação .contains(), .includes(), .find(), ou in list dentro de um loop custa O(N) por verificação. Sobre N iterações: O(N²) total. Este padrão aparece em código de produção em dezenas de ecossistemas — o compilador GHC Haskell, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Mesmo erro, bases de código diferentes.
Revisão: find_duplicates
Revise a seguinte função Python para complexidade:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: O Defect Sedimentar
O Mesmo Defect, Sessenta Ecossistemas
O padrão if x not in list: list.append(x) dentro de um loop aparece — apareceu — em código de produção em dezenas de ecossistemas de software:
- GHC (compilador Haskell): resolvedor de dependências, O(N²) em N = 50.000 pacotes, compilações de 17 minutos
- Python pip: resolução de conflito de dependência
- Apache Maven: deduplicação de classpath
- Rust Cargo: unificação de features
- Compilador TypeScript: resolução de módulo
- Godot / Redot game engine: travessia de grafo de nó
Nenhuma dessas equipes cometeu um erro. Eles escreveram código correto em N pequeno. N cresceu. O código calcificou. O padrão tem um nome: MOAD-0001, O Defect Sedimentar. Sedimento: correto, inofensivo em camadas finas. Com o tempo, as camadas se acumulam e endurecem.
A Correção
Em todos os casos: substitua o contêiner sequencial por um contêiner de hash. Uma linha. Mudança comportamental zero em entradas corretas. Aceleração de 100–1.000× em N do mundo real.
A correção funciona porque duas operações precisam permanecer rápidas:
1. Verificação de associação: este elemento foi visto antes?
2. Saída ordenada: retorna elementos na ordem em que apareceram (às vezes necessário, às vezes não).
Um conjunto manipula (1) em O(1). Se (2) também importa, mantenha uma lista separada para saída ordenada e um conjunto para a verificação de associação. Duas estruturas de dados, cada uma fazendo um trabalho.
Respondendo a um Revisor
Um pull request corrige MOAD-0001 na função de travessia de grafo de um projeto. Um revisor comenta:
> "Conjuntos não preservam a ordem de inserção — isso muda o comportamento."
O Padrão de Análise de Entrevista
O Formato Esperado
A análise de complexidade algorítmica aparece em entrevistas de engenharia de software. Uma resposta forte segue um padrão de quatro partes:
1. Declare a complexidade atual — O(?) para tempo, O(?) para espaço.
2. Explique por quê — identifique a construção específica responsável (loop aninhado, varredura linear em loop, ramificação recursiva).
3. Proponha uma otimização — nomeie a mudança e a estrutura de dados ou algoritmo que ela introduz.
4. Declare a nova complexidade — após a correção, qual é a complexidade de tempo & espaço?
Exemplo:
Code: [função que verifica associação em uma lista dentro de um loop]
Atual: O(N²) — `item in seen_list` é O(N) por verificação × N iterações
Otimização: substitua seen_list por seen_set (conjunto de hash)
Depois: O(N) — a verificação de associação do conjunto é O(1)Esta habilidade se transfere além de entrevistas: revisão de código consciente de complexidade, design de arquitetura, depuração de desempenho, auditorias de segurança. Qualquer sistema que processa entradas de tamanho variável se beneficia disso.
Esta lição se conecta à frente com o curso unhamming, que aplica este padrão exato à investigação de defect de produção em 60+ projetos de código aberto.
Entrevista: Analisar has_common_element
Aplique o formato de entrevista de quatro partes para esta função:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False