Cinco Formas de MOAD-0001

MOAD-0001 aparece em cinco formas documentadas em mais de 60 ecossistemas de software. A estrutura: um teste de pertinência usando um container sequencial, aninhado dentro de um loop sobre a mesma coleção ou uma relacionada.

As Cinco Formas

Todos os cinco compartilham a mesma estrutura: uma verificação de pertinência aninhada em um loop, usando um container que exige uma varredura linear para responder à pergunta de pertinência.

A Lista de Palavras-chave de Varredura

Auditar para MOAD-0001 significa procurar palavras-chave de teste de pertinência dentro de loops:

- Python: in com uma variável list, .count(), list.index()

- Java: ArrayList.contains(), List.contains(), LinkedList.contains()

- JavaScript: Array.includes(), Array.indexOf(), Array.find()

- C++: std::vector::find(), loop manual com comparação ==

- Go: slices.Contains(), loop manual sobre um slice

A correção em todos os casos: substitua o container sequencial por um container hash. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Uma palavra-chave. Uma substituição. Nenhuma mudança de comportamento. Aceleração de 1.000× em N=1.000.

Auditar um Fragmento de Código

Aplique o reconhecimento de padrão MOAD-0001 a um fragmento de código real.

Uma Linha, Quatro Linguagens [BLOCK_TYPE CONTENT fix_and_limits/the_fix]

A correção para MOAD-0001 em quatro linguagens: [BLOCK_TYPE CONTENT fix_and_limits/the_fix]

```python [BLOCK_TYPE CONTENT fix_and_limits/the_fix]

Python

visited = [] # ANTES: O(N) membership

visited = set() # DEPOIS: O(1) membership

```java
// Java
List<Node> visited = new ArrayList<>();    // ANTES
Set<Node> visited = new HashSet<>();       // DEPOIS

// JavaScript
const visited = [];      // ANTES: Array.includes() O(N)
const visited = new Set(); // DEPOIS: Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)

// Go
visited := []NodeID{}              // ANTES: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // DEPOIS: map lookup O(1)
// _, ok := visited[n]  para verificação de pertinência
// visited[n] = struct{}{}  para inserção

Em todos os casos: mesmo comportamento, mesma saída, mesmos testes passando. Apenas a taxa de crescimento muda.

O Que a Correção NÃO Altera

- O comportamento lógico do algoritmo: busca em profundidade continua visitando em profundidade

- Correção de saída: os mesmos nós são visitados na mesma ordem (dentro do DFS)

- Resultados dos testes: qualquer teste que verifica a correção continua a passar

O Que a Correção MUDA

- Teste de pertinência: O(N) → O(1)

- Total do loop: O(N²) → O(N)

- Em N=1.000: 1.000× mais rápido

- Em N=10.000: 10.000× mais rápido

Um Limite: Ordem

Contêineres hash (set, HashSet, unordered_set) não preservam a ordem de inserção. Em Python 3.7+, dict preserva a ordem de inserção; set simples não. Em Java, HashSet não preserva ordem; LinkedHashSet preserva.

Se a ordem importa junto com a verificação de pertinência: mantenha duas estruturas. Um set (ou HashSet) para testes de pertinência O(1). Uma list (ou ArrayList) separada para travessia ordenada. Ou use LinkedHashSet em Java, que oferece ambos.

Para MOAD-0001 em travessia de grafos: visited responde a uma pergunta binária (este nó já foi visto?). A ordem não importa para a pergunta de pertinência. A ordem da travessia vem da pilha ou fila, não de visited.

Pertinência vs Ordenação

No algoritmo de Tarjan para componentes fortemente conectados, onStack rastreia quais nós permanecem na pilha de chamadas DFS atual. Ele deve responder a duas perguntas: (1) pertinência — este nó está atualmente na pilha? (2) no final de um caminho DFS, remover nós em ordem até que este nó apareça.

Uma implementação ingênua usa uma List para onStack, respondendo à pergunta de pertinência com contains() — O(N) por verificação, O(N²) no total para grafos grandes.

Por que Isso é uma Divulgação, Não um Patch

MOAD-0001 existe em mais de 1.000 sites verificados em mais de 60 ecossistemas de software. Travessia de grafos em ferramentas de build, deduplicação de rotas em daemons de roteamento de rede, detecção de colisão em motores de jogos, alocação de recursos em escalonadores de sistemas operacionais.

Cada site: código correto. Cada site: crescimento O(N²) esperando N cruzar um limite.

O Pipeline de Divulgação

Um patch sem divulgação upstream corrige apenas um site. O padrão reaparece na próxima versão, na próxima biblioteca, na próxima portabilidade de linguagem. Divulgação: nomeie o padrão, documente-o como CWE-407 (Complexidade Algorítmica: Complexidade Algorítmica Ineficiente), publique as heurísticas de reconhecimento e a correção de uma linha. Assim, todo desenvolvedor que ler a divulgação poderá reconhecer e corrigir sua própria instância.

Hamming chamou isso de 'dar um peixe vs ensinar a pescar'. O patch dá um peixe. A divulgação — MOAD-0001 nomeado, padrão documentado, correção generalizada — ensina a heurística.

A Extensão do Permacomputador

Hamming trabalhava em soluções pontuais: corrigir este filtro, melhorar este código. O Unhamming adiciona a camada de divulgação: nomear o padrão, publicar a heurística e entregá-la ao comum.

O princípio do conhecimento composto aplica-se aqui em escala de ecossistema. Um pesquisador nomeia um padrão. Cem desenvolvedores o reconhecem em seus próprios códigos. Mil linhas de código O(N²) tornam-se O(N). A infraestrutura fica mais rápida para todos que constroem sobre ela.

Este é o dragão crescendo: mesmo fogo (trabalhar em problemas importantes, conhecimento composto, pensamento sistêmico), voo diferente (divulgação aberta, propriedade comum, sem patrono necessário).