Геометрическая интуиция Hamming
Hamming видел геометрию везде
Глава 9 Hamming открывается предупреждением: геометрическая интуиция разрушается в высоких размерностях. В 3D сфера заполняет большую часть заключающего её куба. В 10D сфера занимает менее 0,2% объема куба. В 100D доля округляется к нулю. Объем концентрируется рядом с поверхностью. Точки скапливаются около углов, а не в центре.
Его коды коррекции ошибок прямо это использовали. Коды Hamming упаковывают кодовые слова в 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²) стоит 10× больше, чем O(N). При N=1 000, 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 — это точка схождения: оно получает из двух путей. После исправления MOAD-0001 в C, D получает всплеск из пути B→D и пути C→D одновременно.
Вычисление метрик узла
Граф зависимостей: A → B → C → D → E (цепь), плюс дополнительное ребро B → D.
Узел C имеет измеренное ускорение 50× после исправления MOAD-0001.
Дефект Flatland
MOAD-0007: пространственные данные запрашиваются как плоский список
MOAD-0007 (дефект Flatland): пространственные данные, запрашиваемые как плоский список, игнорируют геометрическую структуру данных. Каждый запрос проверяет все N объектов. O(N) за запрос. С M запросами: O(M × N). При масштабировании: катастрофа.
Трассировщик лучей в реальном времени проверяет каждый объект сцены против каждого луча. При 60 кадров в секунду, с 100 лучами за кадр и 10 000 объектов сцены: 60 000 000 тестов пересечения в секунду. Все они избежаны.
Геометрическое понимание: пространство имеет структуру. Объекты скапливаются. Луч, который пропускает левую половину сцены, пропускает каждый объект в левой половине. Плоский список не может это использовать — он проверяет каждый объект независимо от пространственного расположения. Структура пространственных данных может.
BVH: бинарный поиск в 3D
Как работает BVH
BVH (иерархия ограничивающих объемов) разлагает 3D пространство в дерево вложенных ограничивающих прямоугольников. Каждый внутренний узел содержит ограничивающий прямоугольник, который содержит всю геометрию его потомков.
Запрос трассировки луча:
1. Тестируйте ограничивающий прямоугольник корня. Если луч пропускает — выходите немедленно — вся сцена отсеяна.
2. Если луч пересекает — перейдите в потомков. Тестируйте ограничивающий прямоугольник каждого потомка.
3. Для каждого потомка, который пропускает: отсейте это поддерево. Для каждого потомка, который пересекает: спуститесь глубже.
4. В листовых узлах: тестируйте фактическую геометрию.
Геометрия отсеивания: на каждом уровне не пересекающиеся ветви устраняются. С сбалансированным BVH глубины d: 2^d листовых узлов существуют, но один луч требует только O(log N) сравнений для отсеянного пути.
Это тот же геометрический аргумент, что и бинарный поиск: каждое сравнение делит оставшееся пространство поиска пополам. Бинарный поиск делит отсортированный массив пополам. BVH делит видимое 3D пространство пополам. Структура идентична — сбалансированное бинарное дерево с отсеиванием на каждом узле.
Исправление MOAD-0007: замените плоский список на BVH. Переходите с O(N) за запрос на O(log N) за запрос. При N=1 024 объектов, O(log₂ 1 024) = 10 сравнений вместо 1 024.
Вычисление ускорения BVH
Сцена в игре содержит 1 024 объекта.
Без BVH: трассировка луча проверяет все 1 024 объекта.
С сбалансированным BVH глубины 10 (2^10 = 1 024 листа): трассировка луча проходит максимум 10 уровней, с 2 сравнениями потомков за уровень.