Intuición Geométrica de Hamming
Hamming Vio Geometría en Todas Partes
El Cap. 9 de Hamming abre con una advertencia: la intuición geométrica colapsa en altas dimensiones. En 3D, una esfera llena la mayoría de su cubo envolvente. En 10D, la esfera ocupa menos del 0.2% del volumen del cubo. En 100D, la fracción se redondea a cero. El volumen se concentra cerca de la superficie. Los puntos se agrupan cerca de las esquinas, no del centro.
Sus códigos de corrección de errores explotaban esto directamente. Los códigos de Hamming empaquetan palabras de código en espacio binario n-dimensional de modo que cada palabra de código está rodeada por una esfera de errores corregibles. La geometría determina cuántos errores puedes corregir. El empaquetamiento de esferas en espacio-n es un problema matemático con consecuencias reales: empaqueta las esferas más densamente, corrige más errores.
El mismo modo de fallo geométrico se aplica a la complejidad algorítmica. Para N pequeña, O(N²) y O(N) se ven casi idénticas en una gráfica. La brecha entre ellas parece manejable. Para N grande, la brecha explota — exactamente como la fracción del volumen de la esfera colapsa en altas dimensiones. Lo que se siente tratable a pequeña escala se vuelve imposible a escala.
La Forma de Cada Clase de Complejidad
Dibujando Complejidad
Cada clase de complejidad tiene una forma geométrica:
- O(1): una línea horizontal. Mismo costo sin importar N. Sin pendiente.
- O(log N): una curva hacia arriba suave que se aplana. Se duplica cada vez que N se eleva al cuadrado. Crece proporcionalmente al número de dígitos en N.
- O(N): una línea diagonal a través del origen. El costo crece proporcionalmente a N.
- O(N log N): una diagonal ligeramente más pronunciada. Una línea que se curva muy suavemente hacia arriba.
- O(N²): una parábola. En N=100: 10,000 operaciones. En N=1,000: 1,000,000 operaciones.
La idea clave: la relación entre dos clases de complejidad es en sí misma una función de N. En N=10, O(N²) cuesta 10× más que O(N). En N=1,000, O(N²) cuesta 1,000× más. En N=1,000,000, cuesta 1,000,000× más. La brecha no solo crece — crece a la velocidad de N mismo.
Este es el argumento geométrico de por qué importan los parches MOAD-0001. Mover un resolutor de dependencias de O(N²) a O(N) no es una aceleración constante. En N=50,000 paquetes, es una aceleración de 50,000×. En N=100,000, es una aceleración de 100,000×. El valor del parche crece con el tamaño del problema.
La Brecha que se Amplía
O(N²) y O(N) ambos producen resultados correctos.
En N=10: O(N²) cuesta 100 operaciones, O(N) cuesta 10 operaciones. Relación: 10×.
En N=1,000: O(N²) cuesta 1,000,000 operaciones, O(N) cuesta 1,000 operaciones.
Gráfos como Geometría
El Grafo Acíclico Dirigido
Un DAG (grafo acíclico dirigido) es una estructura geométrica: nodos conectados por arcos dirigidos sin ciclos. Los gráfos de dependencias de software, canales de construcción, & arquitecturas de flujo de datos forman todos DAGs.
Cada nodo lleva propiedades geométricas medidas contando sus arcos:
- Grado de entrada: número de arcos que llegan al nodo. Un alto grado de entrada significa que muchas dependencias ascendentes alimentan este nodo.
- Grado de salida: número de arcos que salen del nodo. Un alto grado de salida significa que muchos consumidores descendentes dependen de este nodo.
- Intermediación: grado de entrada + grado de salida. Mide cuántos caminos pasan a través de este nodo. Un nodo con alta intermediación se sienta en una encrucijada en el gráfo.
- Puntuación de flujo: aceleración × grado de entrada. Mide cuánto trabajo inunda aguas abajo cuando se despeja este cuello de botella.
El modelo de fábrica da significado físico a estas propiedades geométricas:
- Alta intermediación + alta puntuación de flujo = nodo workaholic. Elimina este cuello de botella sin preparar aguas abajo = colapso.
- Alto grado de salida + baja puntuación de flujo = nodo glutón. Consume sin producir. La máquina que olvida detenerse.
Flujo e Intermediación en la Práctica
Leyendo un DAG
Considera una cadena de 5 nodos: A → B → C → D → E, más un arco adicional B → D.
- A: grado de entrada 0, grado de salida 1, intermediación 1. Nodo fuente. Nada lo alimenta. Un consumidor.
- B: grado de entrada 1 (de A), grado de salida 2 (a C y a D), intermediación 3. Alimenta dos nodos descendentes — un punto de expansión.
- C: grado de entrada 1 (de B), grado de salida 1 (a D), intermediación 2. Un nodo de paso.
- D: grado de entrada 2 (de B y de C), grado de salida 1 (a E), intermediación 3. Recibe de dos caminos.
- E: grado de entrada 1 (de D), grado de salida 0, intermediación 1. Nodo sumidero.
B y D comparten la intermediación más alta (3). B es el punto de expansión: alimenta dos nodos. D es el punto de convergencia: recibe de dos caminos. Después de un parche MOAD-0001 en C, D recibe flujo de ambos caminos B→D y C→D simultáneamente.
Calculando Métricas de Nodos
Un gráfo de dependencias: A → B → C → D → E (una cadena), más un arco adicional B → D.
El nodo C tiene una aceleración medida de 50× después de un parche MOAD-0001.
El Defecto de Flatland
MOAD-0007: Datos Espaciales Consultados como una Lista Plana
MOAD-0007 (el Defecto de Flatland): datos espaciales consultados como una lista plana ignoran la estructura geométrica de los datos. Cada consulta verifica todos los N objetos. O(N) por consulta. Con M consultas: O(M × N). A escala: catastrófico.
Un raycaster en tiempo real verifica cada objeto en una escena contra cada rayo. A 60 fotogramas por segundo, con 100 rayos por fotograma & 10,000 objetos de escena: 60,000,000 pruebas de intersección por segundo. Todas ellas evitables.
La idea geométrica: el espacio tiene estructura. Los objetos se agrupan. Un rayo que pierde la mitad izquierda de la escena pierde cada objeto en la mitad izquierda. Una lista plana no puede explotar esto — verifica cada objeto sin importar la ubicación espacial. Una estructura de datos espacial puede.
El BVH: Búsqueda Binaria en 3D
Cómo Funciona un BVH
Un BVH (Jerarquía de Volúmenes Acotantes) descompone el espacio 3D en un árbol de cajas de delimitación anidadas. Cada nodo interno contiene una caja de delimitación que contiene toda la geometría de sus hijos.
Una consulta de raycast:
1. Prueba la caja de delimitación raíz. Si el rayo falla, sale inmediatamente — toda la escena se poda.
2. Si el rayo golpea, recursa en los hijos. Prueba cada caja de delimitación del hijo.
3. Para cada hijo que falla: poda ese subárbol. Para cada hijo que golpea: recursa más profundo.
4. En nodos hoja: prueba la geometría real.
Geometría de la poda: en cada nivel, las ramas que no se intersectan se eliminan. Con un BVH balanceado de profundidad d: existen 2^d nodos hoja, pero un único rayo necesita como máximo O(log N) comparaciones para la ruta podada.
Este es el mismo argumento geométrico que la búsqueda binaria: cada comparación reduce a la mitad el espacio de búsqueda restante. La búsqueda binaria reduce a la mitad una matriz ordenada. Un BVH reduce a la mitad el espacio 3D visible. La estructura es idéntica — un árbol binario balanceado con poda en cada nodo.
Una corrección MOAD-0007: reemplaza la lista plana con un BVH. Muévete de O(N) por consulta a O(log N) por consulta. En N=1,024 objetos, O(log₂ 1,024) = 10 comparaciones en lugar de 1,024.
Calculando la Aceleración del BVH
Una escena de juego tiene 1,024 objetos.
Sin un BVH: un raycast verifica todos los 1,024 objetos.
Con un BVH balanceado de profundidad 10 (2^10 = 1,024 hojas): un raycast atraviesa como máximo 10 niveles, con 2 comparaciones de hijos por nivel.