해밍의 기하학적 직관
해밍은 모든 곳에서 기하학을 봤다
해밍의 9장은 경고로 시작한다: 기하학적 직관은 고차원에서 붕괴된다. 3차원에서 구는 외접하는 정육면체 부피의 대부분을 차지한다. 10차원에서 구는 정육면체 부피의 0.2% 미만을 차지한다. 100차원에서 그 비율은 0에 가까워진다. 부피는 표면 근처에 집중된다. 점들은 중심이 아니라 모서리 근처에 모인다.
그의 오류 정정 부호들은 이를 직접 이용했다. 해밍 부호는 n차원 이진 공간에 부호어를 배치하여 모든 부호어를 정정 가능한 오류의 구로 둘러싼다. 기하학은 정정할 수 있는 오류의 개수를 결정한다. n공간의 구 채우기는 실제 영향력을 가진 수학 문제다: 구를 더 밀하게 채울수록 더 많은 오류를 정정할 수 있다.
같은 기하학적 실패 양식은 알고리즘 복잡도에도 적용된다. 작은 N에서 O(N²)과 O(N)은 그래프에서 거의 동일하게 보인다. 그들 사이의 간격은 관리 가능해 보인다. 큰 N에서 간격은 폭발한다 — 정확히 구의 부피 비율이 고차원에서 붕괴되는 것처럼. 작은 규모에서 다루기 쉬워 보이는 것이 규모가 커지면 불가능해진다.
각 복잡도 클래스의 형태
복잡도 그리기
각 복잡도 클래스는 기하학적 형태를 가진다:
- O(1): 수평선. N과 관계없이 같은 비용. 기울기 없음.
- O(log N): 가파르지 않은 위로 향하는 곡선이 점점 평탄해진다. N이 제곱될 때마다 두 배씩 증가. N의 자릿수에 비례하여 증가.
- O(N): 원점을 지나는 대각선. 비용은 N에 비례하여 증가.
- O(N log N): 약간 더 가파른 대각선. 아주 완만하게 위로 향하는 직선.
- O(N²): 포물선. N=100일 때: 10,000개 연산. N=1,000일 때: 1,000,000개 연산.
핵심 통찰: 두 복잡도 클래스 사이의 비율 자체가 N의 함수다. N=10일 때 O(N²)은 O(N)보다 10배 더 많은 비용이 든다. N=1,000일 때 O(N²)은 O(N)보다 1,000배 더 많은 비용이 든다. N=1,000,000일 때 1,000,000배 더 많은 비용이 든다. 간격은 단순히 성장하는 것이 아니라 N의 속도로 성장한다.
이것이 MOAD-0001 패치가 중요한 이유에 대한 기하학적 논거다. 의존성 리졸버를 O(N²)에서 O(N)으로 이동하는 것은 상수 배의 속도 향상이 아니다. N=50,000개 패키지에서 50,000배의 속도 향상이다. N=100,000일 때 100,000배의 속도 향상이다. 패치의 가치는 문제 크기와 함께 증가한다.
점점 벌어지는 간격
O(N²)과 O(N) 모두 올바른 결과를 생성한다.
N=10일 때: O(N²)은 100개 연산, O(N)은 10개 연산. 비율: 10배.
N=1,000일 때: O(N²)은 1,000,000개 연산, O(N)은 1,000개 연산.
기하학으로서의 그래프
방향성 비순환 그래프
DAG(방향성 비순환 그래프)는 기하학적 구조다: 순환 없이 방향 간선으로 연결된 노드들. 소프트웨어 의존성 그래프, 빌드 파이프라인, 데이터 흐름 아키텍처 모두 DAG를 형성한다.
각 노드는 간선 개수를 세어서 측정한 기하학적 속성을 가진다:
- 입차수: 노드에 도달하는 간선의 수. 높은 입차수는 많은 상위 의존성이 이 노드에 공급됨을 의미한다.
- 출차수: 노드에서 나가는 간선의 수. 높은 출차수는 많은 하위 소비자가 이 노드에 의존함을 의미한다.
- 중심성: 입차수 + 출차수. 이 노드를 지나가는 경로의 수를 측정한다. 높은 중심성 노드는 그래프의 교차로에 앉아있다.
- 급증 점수: 속도 향상 × 입차수. 이 병목이 제거될 때 하위에 얼마나 많은 작업이 흘러내리는지를 측정한다.
공장 모델은 이러한 기하학적 속성에 물리적 의미를 부여한다:
- 높은 중심성 + 높은 급증 점수 = 일중독 노드. 이 병목을 제거하지만 하위를 준비하지 않으면 = 붕괴.
- 높은 출차수 + 낮은 급증 점수 = 탐욕 노드. 생산하지 않고 소비한다. 멈추는 것을 잊은 기계.
실제 응용에서의 중심성과 급증
DAG 읽기
5개 노드 체인을 생각해보라: A → B → C → D → E, 그리고 추가 간선 B → D.
- A: 입차수 0, 출차수 1, 중심성 1. 소스 노드. 아무것도 공급하지 않는다. 한 명의 소비자.
- B: 입차수 1 (A에서), 출차수 2 (C와 D로), 중심성 3. 두 개의 하위 노드를 공급한다 — 팬아웃 지점.
- C: 입차수 1 (B에서), 출차수 1 (D로), 중심성 2. 통과 노드.
- D: 입차수 2 (B와 C에서), 출차수 1 (E로), 중심성 3. 두 경로에서 받는다.
- E: 입차수 1 (D에서), 출차수 0, 중심성 1. 싱크 노드.
B와 D는 가장 높은 중심성(3)을 공유한다. B는 팬아웃: 두 노드를 공급한다. D는 수렴 지점: 두 경로에서 받는다. C에서의 MOAD-0001 패치 후, D는 B→D 경로와 C→D 경로 모두에서 동시에 급증을 받는다.
노드 메트릭 계산
의존성 그래프: A → B → C → D → E (체인), 그리고 추가 간선 B → D.
노드 C는 MOAD-0001 패치 후 측정된 속도 향상이 50배다.
평탄지 결함
MOAD-0007: 평탄 목록으로 쿼리된 공간 데이터
MOAD-0007 (평탄지 결함): 공간 데이터가 평탄 목록으로 쿼리되면 데이터의 기하학적 구조를 무시한다. 모든 쿼리가 모든 N개 객체를 확인한다. 쿼리당 O(N). M개 쿼리와 함께: O(M × N). 규모: 재앙적.
실시간 레이캐스터는 장면의 모든 객체를 모든 광선과 비교한다. 초당 60 프레임, 프레임당 100개 광선, 10,000개 장면 객체: 초당 60,000,000개 교점 테스트. 모두 피할 수 있다.
기하학적 통찰: 공간은 구조를 가진다. 객체들이 모인다. 장면의 왼쪽 절반을 놓친 광선은 왼쪽 절반의 모든 객체를 놓친다. 평탄 목록은 이를 이용할 수 없다 — 공간 위치와 관계없이 모든 객체를 확인한다. 공간 데이터 구조는 할 수 있다.
BVH: 3D의 이진 탐색
BVH 어떻게 작동하는가
BVH(경계 부피 계층)는 3D 공간을 중첩된 경계 상자의 트리로 분해한다. 각 내부 노드는 모든 자식의 기하학을 포함하는 경계 상자를 보유한다.
광선 투사 쿼리:
1. 루트 경계 상자를 테스트한다. 광선이 놓치면 즉시 종료한다 — 전체 장면이 제거된다.
2. 광선이 맞으면 자식으로 재귀한다. 각 자식의 경계 상자를 테스트한다.
3. 놓친 각 자식: 그 부분트리를 제거한다. 맞춘 각 자식: 더 깊이 재귀한다.
4. 리프 노드에서: 실제 기하학을 테스트한다.
제거의 기하학: 각 수준에서 교점이 없는 가지가 제거된다. 깊이 d의 균형잡힌 BVH: 2^d개 리프 노드가 존재하지만, 단일 광선은 제거된 경로에 대해 최대 O(log N) 비교만 필요하다.
이것은 이진 탐색과 같은 기하학적 논거다: 각 비교가 남은 검색 공간을 반으로 줄인다. 이진 탐색은 정렬된 배열을 반으로 줄인다. BVH는 보이는 3D 공간을 반으로 줄인다. 구조는 동일하다 — 각 노드에서 제거를 사용한 균형잡힌 이진 트리.
MOAD-0007 수정: 평탄 목록을 BVH로 바꾼다. 쿼리당 O(N)에서 O(log N)으로 이동한다. N=1,024개 객체일 때, O(log₂ 1,024) = 10회 비교 vs 1,024회.
BVH 속도 향상 계산
게임 장면에 1,024개의 객체가 있다.
BVH 없음: 광선 투사는 모든 1,024개 객체를 확인한다.
깊이 10 (2^10 = 1,024개 리프)의 균형잡힌 BVH: 광선 투사는 최대 10개 수준을 통과하고, 각 수준에 2개의 자식 비교가 있다.