Intuisi Geometris Hamming
Hamming Melihat Geometri di Mana-Mana
Bab 9 Hamming dibuka dengan peringatan: intuisi geometris runtuh dalam dimensi tinggi. Pada 3D, sebuah bola mengisi sebagian besar kubus penutupnya. Pada 10D, bola menempati kurang dari 0,2% volume kubus. Pada 100D, fraksi dibulatkan menjadi nol. Volume terkonsentrasi di dekat permukaan. Titik-titik berkumpul di dekat sudut, bukan di pusat.
Kode koreksi kesalahannya memanfaatkan ini secara langsung. Kode Hamming mengemas codeword ke dalam ruang biner n-dimensi sedemikian rupa sehingga setiap codeword dikelilingi oleh bola kesalahan yang dapat diperbaiki. Geometri menentukan berapa banyak kesalahan yang dapat Anda perbaiki. Pengemasan bola dalam ruang-n adalah masalah matematika dengan pertaruhan nyata: kemasan bola lebih padat, perbaiki lebih banyak kesalahan.
Mode kegagalan geometris yang sama berlaku untuk kompleksitas algoritmik. Pada N kecil, O(N²) dan O(N) terlihat hampir identik pada grafik. Celah di antara mereka tampak dapat dikelola. Pada N besar, celah meledak — persis seperti fraksi volume bola runtuh dalam dimensi tinggi. Apa yang terasa dapat ditangani pada skala kecil menjadi tidak mungkin pada skala besar.
Bentuk Setiap Kelas Kompleksitas
Menggambar Kompleksitas
Setiap kelas kompleksitas memiliki bentuk geometris:
- O(1): garis horizontal. Biaya yang sama terlepas dari N. Tidak ada kemiringan.
- O(log N): kurva naik lembut yang mendatar. Menggandakan setiap kali N kuadrat. Tumbuh sebanding dengan jumlah digit dalam N.
- O(N): garis diagonal melalui titik asal. Biaya tumbuh sebanding dengan N.
- O(N log N): diagonal sedikit lebih curam. Garis yang melengkung sangat lembut ke atas.
- O(N²): parabola. Pada N=100: 10.000 operasi. Pada N=1.000: 1.000.000 operasi.
Wawasan kritis: rasio antara dua kelas kompleksitas adalah fungsi dari N itu sendiri. Pada N=10, O(N²) biaya 10× lebih besar dari O(N). Pada N=1.000, O(N²) biaya 1.000× lebih besar. Pada N=1.000.000, biayanya 1.000.000× lebih besar. Celah tidak hanya tumbuh — celah tumbuh dengan laju N itu sendiri.
Ini adalah argumen geometris untuk mengapa patch MOAD-0001 penting. Memindahkan resolver dependensi dari O(N²) ke O(N) bukanlah speedup konstan. Pada N=50.000 paket, ini adalah speedup 50.000×. Pada N=100.000, ini adalah speedup 100.000×. Nilai patch tumbuh dengan ukuran masalah.
Celah yang Melebar
O(N²) dan O(N) keduanya menghasilkan hasil yang benar.
Pada N=10: O(N²) biaya 100 operasi, O(N) biaya 10 operasi. Rasio: 10×.
Pada N=1.000: O(N²) biaya 1.000.000 operasi, O(N) biaya 1.000 operasi.
Graf sebagai Geometri
Grafik Asiklik Berarah
DAG (directed acyclic graph) adalah struktur geometris: node yang terhubung oleh tepi berarah tanpa siklus. Grafik dependensi perangkat lunak, pipeline pembangunan, dan arsitektur aliran data semuanya membentuk DAG.
Setiap node membawa sifat geometris yang diukur dengan menghitung tepinya:
- In-degree: jumlah tepi yang tiba di node. In-degree tinggi berarti banyak dependensi upstream memberi makan node ini.
- Out-degree: jumlah tepi yang meninggalkan node. Out-degree tinggi berarti banyak konsumen downstream bergantung pada node ini.
- Betweenness: in-degree + out-degree. Mengukur berapa banyak path yang melewati node ini. Node dengan betweenness tinggi duduk di persimpangan dalam grafik.
- Surge score: speedup × in-degree. Mengukur berapa banyak pekerjaan yang banjir downstream saat bottleneck ini hilang.
Model pabrik memberikan makna fisik pada sifat geometris ini:
- Betweenness tinggi + surge score tinggi = node workaholic. Buang bottleneck ini tanpa mempersiapkan downstream = keruntuhan.
- Out-degree tinggi + surge score rendah = node glutton. Mengkonsumsi tanpa menghasilkan. Mesin yang lupa untuk berhenti.
Surge & Betweenness dalam Praktek
Membaca DAG
Pertimbangkan rantai 5-node: A → B → C → D → E, ditambah tepi tambahan B → D.
- A: in-degree 0, out-degree 1, betweenness 1. Node sumber. Tidak ada yang memberinya makan. Satu konsumen.
- B: in-degree 1 (dari A), out-degree 2 (ke C dan ke D), betweenness 3. Memberi makan dua node downstream — titik fan-out.
- C: in-degree 1 (dari B), out-degree 1 (ke D), betweenness 2. Node pass-through.
- D: in-degree 2 (dari B dan dari C), out-degree 1 (ke E), betweenness 3. Menerima dari dua path.
- E: in-degree 1 (dari D), out-degree 0, betweenness 1. Node sink.
B dan D berbagi betweenness tertinggi (3). B adalah fan-out: ia memberi makan dua node. D adalah titik konvergensi: ia menerima dari dua path. Setelah patch MOAD-0001 di C, D menerima surge dari path B→D dan path C→D secara bersamaan.
Menghitung Metrik Node
Grafik dependensi: A → B → C → D → E (rantai), ditambah tepi tambahan B → D.
Node C memiliki speedup terukur 50× setelah patch MOAD-0001.
Cacat Flatland
MOAD-0007: Data Spasial Ditanyai sebagai Daftar Flat
MOAD-0007 (Flatland Defect): data spasial yang ditanyai sebagai daftar flat mengabaikan struktur geometris data. Setiap query memeriksa semua N objek. O(N) per query. Dengan M query: O(M × N). Pada skala: katastropal.
Ray caster real-time memeriksa setiap objek dalam scene terhadap setiap ray. Pada 60 frame per detik, dengan 100 ray per frame dan 10.000 objek scene: 60.000.000 tes interseksi per detik. Semua dapat dihindari.
Wawasan geometris: ruang memiliki struktur. Objek berkumpul. Ray yang melewatkan setengah kiri scene melewatkan setiap objek di setengah kiri. Daftar flat tidak dapat memanfaatkan ini — ia memeriksa setiap objek terlepas dari lokasi spasial. Struktur data spasial dapat.
BVH: Pencarian Biner dalam 3D
Bagaimana BVH Bekerja
BVH (Bounding Volume Hierarchy) mendekomposisi ruang 3D menjadi pohon kotak pembatas bersarang. Setiap node internal memegang kotak pembatas yang berisi semua geometri anaknya.
Query raycast:
1. Test kotak pembatas root. Jika ray melewatkan, keluar segera — seluruh scene dipangkas.
2. Jika ray mengenai, recurse ke anak-anak. Test kotak pembatas setiap anak.
3. Untuk setiap anak yang melewatkan: pangkas subtree itu. Untuk setiap anak yang mengenai: recurse lebih dalam.
4. Di leaf node: test geometri sebenarnya.
Geometri pemangkasan: di setiap level, branch non-intersecting dihilangkan. Dengan BVH yang seimbang dengan kedalaman d: 2^d leaf node ada, tetapi ray tunggal memerlukan paling banyak O(log N) perbandingan untuk path yang dipangkas.
Ini adalah argumen geometris yang sama dengan pencarian biner: setiap perbandingan membagi dua sisa ruang pencarian. Pencarian biner membagi dua array yang diurutkan. BVH membagi dua ruang 3D yang terlihat. Struktur identik — pohon biner seimbang dengan pemangkasan di setiap node.
Perbaikan MOAD-0007: ganti daftar flat dengan BVH. Pindahkan dari O(N) per query ke O(log N) per query. Pada N=1.024 objek, O(log₂ 1.024) = 10 perbandingan bukan 1.024.
Menghitung Speedup BVH
Scene game memiliki 1.024 objek.
Tanpa BVH: raycast memeriksa semua 1.024 objek.
Dengan BVH seimbang dengan kedalaman 10 (2^10 = 1.024 leaf): raycast melintasi paling banyak 10 level, dengan 2 perbandingan anak per level.