Геометрична інтуїція Хеммінга
Хеммінг бачив геометрію скрізь
Розділ 9 Хеммінга починається з попередження: геометрична інтуїція розпадається у високих вимірах. При 3D сфера заповнює більшість куба, що її оточує. При 10D сфера займає менше 0,2% об'єму куба. При 100D частка наближується до нуля. Об'єм концентрується біля поверхні. Точки групуються біля кутків, а не у центру.
Його коди корекції помилок використовували це прямо. Коди Хеммінга пакують кодові слова у 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: 10000 операцій. При N=1000: 1000000 операцій.
Критичне розуміння: відношення між двома класами складності саме по собі є функцією N. При N=10 O(N²) коштує в 10× більше, ніж O(N). При N=1000 O(N²) коштує в 1000× більше. При N=1000000 воно коштує в 1000000× більше. Розрив не просто зростає — він зростає зі швидкістю самого N.
Це геометричний аргумент того, чому патчі MOAD-0001 мають значення. Переміщення розв'язувача залежностей з O(N²) на O(N) — це не постійне прискорення. При N=50000 пакетів це прискорення в 50000×. При N=100000 це прискорення в 100000×. Цінність патча зростає з розміром задачі.
Розширюючийся розрив
O(N²) та O(N) обидва дають правильні результати.
При N=10: O(N²) коштує 100 операцій, O(N) коштує 10 операцій. Відношення: 10×.
При N=1000: O(N²) коштує 1000000 операцій, O(N) коштує 1000 операцій.
Графи як геометрія
Орієнтований ациклічний граф
DAG (орієнтований ациклічний граф) — це геометрична структура: вузли, з'єднані спрямованими ребрами без циклів. Графи залежностей програмного забезпечення, конвеєри побудови та архітектури потоків даних утворюють DAG.
Кожен вузол несе геометричні властивості, виміряні підрахунком його ребер:
- In-degree: кількість ребер, які входять у вузол. Високе in-degree означає, що на цей вузол надходить живлення від багатьох попередніх залежностей.
- Out-degree: кількість ребер, що виходять з вузла. Високе out-degree означає, що багато інших вузлів залежать від цього вузла.
- Betweenness: in-degree + out-degree. Вимірює, скільки шляхів проходить через цей вузол. Вузол з високим betweenness перебуває на перехресті у графі.
- Surge score: прискорення × in-degree. Вимірює, як багато роботи заливає розташовані нижче вузли, коли це вузьке місце звільняється.
Модель фабрики надає цим геометричним властивостям фізичне значення:
- Високе betweenness + високий surge score = вузол трудоголіка. Усунення цього вузького місця без підготовки розташованих нижче = колапс.
- Високе out-degree + низький surge score = вузол обжери. Споживає без виробництва. Машина, яка забуває зупинитися.
Surge & Betweenness на практиці
Читання DAG
Розглянемо ланцюг з 5 вузлів: A → B → C → D → E, плюс додаткове ребро B → D.
- A: in-degree 0, out-degree 1, betweenness 1. Вихідний вузол. Нічого його не живить. Один споживач.
- B: in-degree 1 (від A), out-degree 2 (на C та на D), betweenness 3. Живить два розташовані нижче вузли — точка розгалуження.
- C: in-degree 1 (від B), out-degree 1 (на D), betweenness 2. Вузол, що пропускає дані.
- D: in-degree 2 (від B та від C), out-degree 1 (на E), betweenness 3. Отримує дані з двох шляхів.
- E: in-degree 1 (від D), out-degree 0, betweenness 1. Вузол-приймач.
B та D мають найвище betweenness (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 променями на кадр та 10000 об'єктів сцени: 60000000 тестів перетину на секунду. Всі вони можна уникнути.
Геометричне розуміння: простір має структуру. Об'єкти групуються. Промінь, що пропускає ліву половину сцени, пропускає кожен об'єкт у лівій половині. Плаский список не може це експлуатувати — він перевіряє кожен об'єкт незалежно від просторового розташування. Просторова структура даних може.
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=1024 об'єктів, O(log₂ 1024) = 10 порівнянь замість 1024.
Обчислення прискорення BVH
Сцена гри має 1024 об'єкти.
Без BVH: трасування променя перевіряє всі 1024 об'єкти.
З збалансованою BVH глибини 10 (2^10 = 1024 листків): трасування променя проходить щонайбільше 10 рівнів, з 2 порівняннями дочірніх вузлів на рівень.