Intuição Geométrica de Hamming
Hamming Viu Geometria em Toda Parte
O Cap. 9 de Hamming começa com um aviso: intuição geométrica desmorona em altas dimensões. Em 3D, uma esfera preenche a maior parte de seu cubo envolvente. Em 10D, a esfera ocupa menos de 0,2% do volume do cubo. Em 100D, a fração arredonda para zero. O volume se concentra perto da superfície. Os pontos se aglomeram perto dos cantos, não do centro.
Seus códigos corretores de erros exploravam isso diretamente. Códigos de Hamming empacotam palavras-código no espaço binário n-dimensional de modo que toda palavra-código é cercada por uma esfera de erros corrigíveis. A geometria determina quantos erros você pode corrigir. O empacotamento de esferas no espaço n-dimensional é um problema matemático com consequências reais: empacotar as esferas mais densamente, corrigir mais erros.
O mesmo modo de falha geométrica se aplica à complexidade algorítmica. Em N pequeno, O(N²) e O(N) parecem quase idênticos em um gráfico. A diferença entre eles parece gerenciável. Em N grande, a diferença explode — exatamente como a fração de volume da esfera desmorona em altas dimensões. O que parece tratável em pequena escala se torna impossível em escala.
A Forma de Cada Classe de Complexidade
Desenho da Complexidade
Cada classe de complexidade tem uma forma geométrica:
- O(1): uma linha horizontal. Mesmo custo independente de N. Sem inclinação.
- O(log N): uma curva suave para cima que se achata. Dobra cada vez que N se quadruplica. Cresce proporcionalmente ao número de dígitos em N.
- O(N): uma linha diagonal pela origem. O custo cresce proporcionalmente a N.
- O(N log N): diagonal ligeiramente mais íngreme. Uma linha que se curva muito suavemente para cima.
- O(N²): uma parábola. Em N=100: 10.000 operações. Em N=1.000: 1.000.000 operações.
A ideia crítica: a razão entre duas classes de complexidade é em si uma função de N. Em N=10, O(N²) custa 10× mais que O(N). Em N=1.000, O(N²) custa 1.000× mais. Em N=1.000.000, custa 1.000.000× mais. A diferença não apenas cresce — ela cresce na taxa de N em si.
Este é o argumento geométrico para por que patches MOAD-0001 importam. Mover um resolvedor de dependências de O(N²) para O(N) não é um aumento constante de velocidade. Em N=50.000 pacotes, é um aumento de velocidade de 50.000×. Em N=100.000, é um aumento de 100.000×. O valor do patch cresce com o tamanho do problema.
A Lacuna Crescente
O(N²) e O(N) ambos produzem resultados corretos.
Em N=10: O(N²) custa 100 operações, O(N) custa 10 operações. Razão: 10×.
Em N=1.000: O(N²) custa 1.000.000 operações, O(N) custa 1.000 operações.
Grafos como Geometria
O Grafo Acíclico Direcionado
Um DAG (grafo acíclico direcionado) é uma estrutura geométrica: nós conectados por arestas direcionadas sem ciclos. Grafos de dependência de software, pipelines de construção & arquiteturas de fluxo de dados formam DAGs.
Cada nó carrega propriedades geométricas medidas por contagem de suas arestas:
- Grau de entrada: número de arestas chegando ao nó. Alto grau de entrada significa muitas dependências a montante alimentam este nó.
- Grau de saída: número de arestas saindo do nó. Alto grau de saída significa muitos consumidores a jusante dependem deste nó.
- Betweenness: grau de entrada + grau de saída. Mede quantos caminhos passam por este nó. Um nó de betweenness elevada senta em um cruzamento no grafo.
- Pontuação de surge: aumento de velocidade × grau de entrada. Mede quanto trabalho inunda a jusante quando este gargalo se abre.
O modelo de fábrica dá a essas propriedades geométricas significado físico:
- Betweenness elevada + pontuação de surge elevada = nó workholic. Remover este gargalo sem preparar a jusante = colapso.
- Grau de saída elevada + pontuação de surge baixa = nó glutton. Consome sem produzir. A máquina que esquece de parar.
Surge & Betweenness na Prática
Lendo um DAG
Considere uma cadeia de 5 nós: A → B → C → D → E, mais uma aresta adicional B → D.
- A: grau de entrada 0, grau de saída 1, betweenness 1. Nó fonte. Nada o alimenta. Um consumidor.
- B: grau de entrada 1 (de A), grau de saída 2 (para C e para D), betweenness 3. Alimenta dois nós a jusante — um ponto de distribuição.
- C: grau de entrada 1 (de B), grau de saída 1 (para D), betweenness 2. Um nó de passagem.
- D: grau de entrada 2 (de B e de C), grau de saída 1 (para E), betweenness 3. Recebe de dois caminhos.
- E: grau de entrada 1 (de D), grau de saída 0, betweenness 1. Nó sumidouro.
B & D compartilham o betweenness mais elevado (3). B é a distribuição: alimenta dois nós. D é o ponto de convergência: recebe de dois caminhos. Após um patch MOAD-0001 em C, D recebe surge do caminho B→D & do caminho C→D simultaneamente.
Calculando Métricas de Nós
Um grafo de dependência: A → B → C → D → E (uma cadeia), mais uma aresta adicional B → D.
Nó C tem um aumento de velocidade medido de 50× após um patch MOAD-0001.
O Defeito Flatland
MOAD-0007: Dados Espaciais Consultados como Lista Flat
MOAD-0007 (o Defeito Flatland): dados espaciais consultados como uma lista flat ignora a estrutura geométrica dos dados. Cada consulta verifica todos os N objetos. O(N) por consulta. Com M consultas: O(M × N). Em escala: catastrófico.
Um raytracer em tempo real verifica todos os objetos em uma cena contra cada raio. A 60 quadros por segundo, com 100 raios por quadro & 10.000 objetos de cena: 60.000.000 testes de intersecção por segundo. Todos eles evitáveis.
A ideia geométrica: espaço tem estrutura. Objetos se aglomeram. Um raio que erra a metade esquerda da cena erra cada objeto na metade esquerda. Uma lista flat não pode explorar isso — ela verifica cada objeto independentemente da localização espacial. Uma estrutura de dados espacial pode.
O BVH: Busca Binária em 3D
Como um BVH Funciona
Um BVH (Hierarquia de Volume Envolvente) decompõe espaço 3D em uma árvore de caixas envolventes aninhadas. Cada nó interno contém uma caixa envolvente que contém toda a geometria de seus filhos.
Uma consulta raycast:
1. Teste a caixa envolvente raiz. Se o raio erra, saia imediatamente — toda a cena é podada.
2. Se o raio bate, recurse nos filhos. Teste a caixa envolvente de cada filho.
3. Para cada filho que erra: poda essa subárvore. Para cada filho que bate: recurse mais profundamente.
4. Nos nós folha: teste a geometria real.
Geometria da poda: em cada nível, ramos não-intersectantes são eliminados. Com um BVH balanceado de profundidade d: 2^d nós folha existem, mas um único raio precisa de no máximo O(log N) comparações para o caminho podado.
Este é o mesmo argumento geométrico que busca binária: cada comparação reduz pela metade o espaço de busca restante. Busca binária reduz pela metade um array ordenado. Um BVH reduz pela metade o espaço 3D visível. A estrutura é idêntica — uma árvore binária balanceada com poda em cada nó.
Um fix MOAD-0007: substitua a lista flat por um BVH. Mude de O(N) por consulta para O(log N) por consulta. Em N=1.024 objetos, O(log₂ 1.024) = 10 comparações em vez de 1.024.
Calculando Aumento de Velocidade do BVH
Uma cena de jogo tem 1.024 objetos.
Sem um BVH: um raycast verifica todos os 1.024 objetos.
Com um BVH balanceado de profundidade 10 (2^10 = 1.024 folhas): um raycast atravessa no máximo 10 níveis, com 2 comparações de filho por nível.