Intuisi Geometris Hamming
Hamming Melihat Geometri Di Mana-mana
Bab 9 Hamming dimulai dengan peringatan: intuisi geometri runtuh di dimensi tinggi. Pada 3D, bola mengisi sebagian besar kubus pengisiannya. Pada 10D, bola menutupi kurang dari 0,2% volume kubus. Pada 100D, fraksi mengarah ke nol. Volume berkonsentrasi dekat permukaan. Titik berkumpul di sudut-sudut, bukan di tengah.
Kodex koreksinya memanfaatkan ini secara langsung. Kode Hamming memuat kata-kata kod di ruang n-dimensional biner sehingga setiap kata kod diapit oleh bola kesalahan yang dapat diperbaiki. Geometri menentukan berapa banyak kesalahan yang dapat diperbaiki. Pemadatan bola di ruang n adalah masalah matematika dengan konsekuensi nyata: padatkan bola lebih padat, korrig lebih banyak kesalahan.
Sama halnya dengan kegagalan geometri ini pada kompleksitas algoritmik. Pada skala kecil, O(N²) dan O(N) tampak hampir identik pada grafik. Jarak antara mereka terasa dapat diatasi. Pada skala besar, jarak meledak - tepat seperti fraksi volume bola yang runtuh di dimensi tinggi. Yang terasa dapat diatasi pada skala kecil menjadi mustahil pada skala.
Bentuk Setiap Kelas Kompleksitas
Mencetak Kompleksitas
Setiap kelas kompleksitas memiliki bentuk geometri:
- O(1): garis horizontal. Biaya yang sama terlepas dari N. Tanpa kemiringan.
- O(log N): kurva naik yang agak melengkung dan rata. Dua kali lipat setiap kali N disiku. Tumbuh secara proporsional dengan jumlah angka dalam N.
- O(N): garis diagonal melalui asal. Biaya tumbuh secara proporsional terhadap N.
- O(N log N): diagonal agak lebih miring. Garis yang agak melengkung naik.
- O(N²): parabola. Pada N = 100: 10.000 operasi. Pada N = 1.000: 1.000.000 operasi.
Insight kritis: rasio antara dua kelas kompleksitas itu sendiri adalah fungsi dari N. Pada N = 10, O(N²) menghabiskan 10 kali lebih banyak daripada O(N). Pada N = 1.000, O(N²) menghabiskan 1.000 kali lebih banyak. Pada N = 1.000.000, itu menghabiskan 1.000.000 kali lebih banyak. Jarak tidak hanya tumbuh - ia tumbuh dengan laju N itu sendiri.
Ini adalah argumen geometri mengapa patch MOAD-0001 penting. Menggerakkan pemecah ketergantungan dari O(N²) ke O(N) bukan peningkatan kecepatan konstan. Pada N=50,000 paket, ini adalah peningkatan kecepatan 50,000×. Pada N=100,000, ini adalah peningkatan kecepatan 100,000×. Nilai patch tumbuh seiring dengan ukuran masalah.
Jarak Menjadi Lebar
O(N²) dan O(N) keduanya menghasilkan hasil yang benar.
Pada N=10: O(N²) menghabiskan 100 operasi, O(N) menghabiskan 10 operasi. Perbandingan: 10×.
Pada N=1,000: O(N²) menghabiskan 1,000,000 operasi, O(N) menghabiskan 1,000 operasi.
Grafik sebagai Geometri
Grafik Terarah Tanpa Lingkaran
Grafik DAG (directed acyclic graph) adalah struktur geometri: node yang terhubung oleh edgenya dengan arah tanpa lingkaran. Grafik ketergantungan perangkat lunak, alur pembangunan, dan arsitektur aliran data semuanya membentuk DAG.
Setiap node memiliki sifat geometris yang diukur dengan menghitung edgenya:
- In-degree: jumlah edgenya yang tiba di node. In-degree tinggi berarti banyak dependensi upstream yang mengalir ke node ini.
- Out-degree: jumlah edgenya yang keluar dari node. Out-degree tinggi berarti banyak konsumen downstream yang tergantung pada node ini.
- Betweenness: in-degree + out-degree. Mengukur berapa banyak jalur yang melewati node ini. Node dengan betweenness tinggi berada di persimpangan dalam grafik.
- Surge score: kecepatan × in-degree. Mengukur seberapa banyak kerja yang mengalir ke bawah saat bottleneck ini dibersihkan.
Model pabrik memberikan arti makna kepada sifat geometris ini:
- Tinggi antara + skor surges tinggi = node workaholic. Hilangkan bottleneck ini tanpa mengatur ulang turunannya = runtuh.
- Tinggi out-degree + skor surges rendah = node glutton. Mengkonsumsi tanpa memproduksi. Mesin yang lupa untuk berhenti.
Surge & Betweenness dalam Praktek
Membaca DAG
Pertimbangkan sebuah jaringan 5 node: A → B → C → D → E, serta tambahan satu edge B → D.
- A: in-degree 0, out-degree 1, betweenness 1. Node sumber. Tidak ada yang mengirim kepadanya. Satu konsumen.
- B: in-degree 1 (dari A), out-degree 2 (ke C dan ke D), betweenness 3. Mengirim ke dua node turunannya - titik fan-out.
- C: in-degree 1 (dari B), out-degree 1 (ke D), betweenness 2. Node transit.
- D: in-degree 2 (dari B dan dari C), out-degree 1 (ke E), betweenness 3. Menerima dari dua jalur.
- E: in-degree 1 (dari D), out-degree 0, betweenness 1. Node sumber.
B dan D memiliki antara betweenness tertinggi (3). B adalah fan-out: mengirim ke dua node. D adalah titik konvergensi: menerima dari dua jalur. Setelah patch MOAD-0001 di C, D menerima surge dari kedua jalur B→D dan C→D secara bersamaan.
Menghitung Metrik Node
Sebuah grafik ketergantungan: A → B → C → D → E (rantai), ditambah satu edge tambahan B → D.
Node C memiliki percepatan yang diukur 50× setelah patch MOAD-0001.
Kekacauan Flatland
MOAD-0007: Data Spasial Diqueri Sebagai Daftar Rata
MOAD-0007 (Kekacauan Flatland): mengqueri data spasial sebagai daftar rata mengabaikan struktur geometris data. Setiap queri mengecek semua N objek. O(N) per queri. Dengan M queri: O(M × N). Di skala yang besar: kacau.
Raycaster nyata memeriksa setiap objek dalam scene terhadap setiap ray. Dengan 60 frame per detik, dengan 100 ray per frame dan 10,000 objek scene: 60,000,000 tes perpotongan per detik. Semua nya dapat dihindari.
Insight geometris: ruang memiliki struktur. Objek berkumpul. Sebuah ray yang melewatkan setengah kiri scene melewati setiap objek di setengah kiri. Sebuah daftar rata tidak bisa mengambil keuntungan ini - itu mengecek setiap objek meskipun lokasi spasial. Struktur data spasial bisa.
BVH: Pencarian Biner di 3D
Cara Kerja BVH
BVH (Bounding Volume Hierarchy) memecah ruang 3D menjadi pohon yang terdiri dari kotak pembungkus yang saling melengkapi. Setiap node internal menampung kotak pembungkus yang mengandung semua geometri anaknya.
Query raycast:
1. Tes kotak pembungkus root. Jika ray melewatkan, keluar segera - seluruh scene dipangkas.
2. Jika ray menumbuk, lanjut ke anak. Tes setiap anak's kotak pembungkus.
3. Untuk setiap anak yang melewatkan: pangkas cabang tersebut. Untuk setiap anak yang menumbuk: lanjut lebih dalam.
4. Pada node daun: tes geometri yang sebenarnya.
Geometri pemangkasan: pada setiap tingkat, cabang yang tidak saling bersinggungan dihilangkan. Dengan BVH seimbang dengan kedalaman d: 2^d node daun ada, tapi satu ray perlu maksimum O(log N) perbandingan untuk jalur yang dipangkas.
Ini adalah argumen geometris yang sama dengan pencarian biner: setiap perbandingan mengurangi setengah ruang pencarian yang tersisa. Pencarian biner mengurangi setengah array yang terurut. BVH mengurangi setengah ruang 3D yang terlihat. Struktur yang sama - pohon biner seimbang dengan pemangkasan pada setiap node.
Perbaikan MOAD-0007: ganti daftar rata dengan BVH. Bergerak dari O(N) per queri ke O(log N) per queri. Dengan N=1,024 objek, O(log₂ 1,024) = 10 perbandingan daripada 1,024.
Menghitung Kecepatan BVH
Sebuah scene permainan memiliki 1.024 objek.
Tanpa BVH: raycast mengecek semua 1.024 objek.
Dengan BVH seimbang dengan kedalaman 10 (2^10 = 1.024 cabang): raycast menelusuri paling banyak 10 tingkat, dengan 2 perbandingan anak per tingkat.