Hamming'in Dik Geometrik Intüisyon
Hamming Her Şeyi Dik Bir Şekilde Gördü
Hamming'in 9. bölümü, yüksek boyutlarda geometrik intüisyonun çöküşü konusunda bir uyarıyla başlıyor. 3D'de, bir küre kapsülün iç kubbesinin büyük bir kısmını doldurur. 10D'de, küre kapsülün hacminin %0,2'sini işgal eder. 100D'de, fraksiyon sıfırlandı. Hacim yüzey yakınlarında yoğunlaşır. Noktalar, merkezde değil, köşelerde yoğunlaşır.
Hata düzeltme kodları doğrudan bu kavramı kullandı. Hamming kodları, her kod sözcüğün n-boyutlu ikili uzayda, hataları düzeltilebilir bir küre içinde paketlenmesini sağlar. Dik geometri, ne kadar hata düzeltebileceğinizi belirler. n-uzaydaki küre paketleme, gerçek risklerle ilgili bir matematik sorundur: küreleri daha sıkı bir şekilde paketleyin, daha fazla hata düzeltin.
Algoritmik karmaşıklık için de aynı geometrik başarım modu geçerlidir. Küçük N'de, O(N²) ve O(N) grafikte neredeyse aynı görünür. Aralarındaki boşluk yönetilebilir görünür. Büyük N'de, boşluk patlar - tam olarak yüksek boyutlarda kürenin hacim fraksiyonunun çöküşü gibi. Küçük ölçekte yönetilebilir olan, ölçekte imkansız hale gelir.
Her Karmaşıklık Sınıfının Şekli
Karmaşıklığı Çizmek
Her karmaşıklık sınıfının bir geometrik şekli vardır:
- O(1): yatay bir çizgi. N'ye bağlı olarak maliyet aynıdır. Hiç eğik olmayan bir eğri.
- O(log N): hafif bir yukarıya doğru eğri, sonra düzleşir. N'in kareleri her zaman iki katlanır. N'in basamak sayısına orantılı büyür.
- O(N): eğik bir çizgi, köklüdür. N'ye orantılı olarak maliyet büyür.
- O(N log N): çok daha dik bir eğik çizgi. Çok hafif bir yukarıya doğru eğri.
- O(N²): bir elips. N=100'de: 10.000 işlem. N=1.000'de: 1.000.000 işlem.
Eleştirel kavrama: iki karmaşıklık sınıfı arasındaki oran N'ye bağlı bir fonksiyondur. N=10'da, O(N²) O(N) maliyetten 10 kat daha fazla. N=1.000'de, O(N²) maliyet 1.000 kat daha fazla. N=1.000.000'de, maliyet 1.000.000 kat daha fazla. Aradaki boşluk sadece büyümüyor - büyüyen, N'nin kendisi oranında büyüyor.
Bu, MOAD-0001 patchlerin neden önemli olduğunu gösteren geometrik argümandır. Bağımlılık çözücüyü O(N²) den O(N)'ye hareket ettirmek, sabit bir hızlandırmadır. N=50,000 pakette, 50,000× hızlandırma olur. N=100,000'de, 100,000× hızlandırma olur. Patchin değeri, sorun boyutu arttıkça artar.
Genişlenmekte Olan Fark
O(N²) ve O(N) her iki durumda da doğru sonuçlar üretir.
N=10'da: O(N²) 100 işlem maliyeti, O(N) 10 işlem maliyeti. Oran: 10×.
N=1,000'de: O(N²) 1.000.000 işlem maliyeti, O(N) 1.000 işlem maliyeti.
Grafikler - Geometri
Yönlendirilmiş Akılcı Graf
Bir DAG (yönlendirilmiş akılcı graf) bir geometrik yapıdır: düğümleyeni yönlendirilmiş kenarlarla bağlanmış, döngüsüz. Yazılım bağımlılık grafikleri, build.pipeline'ları ve veri akışı mimarileri tümü DAG oluşturur.
Her düğüm geometrik özelliklere sahip olup, kenar sayısına göre ölçülür:
- Giriş Açısı: Düğme başına gelen kenar sayısı. Yüksek giriş açıklığı, bu düğme için çok sayıda üst düzey bağımlılığa sahip demektir.
- Çıkış Açısı: Düğmeden çıkan kenar sayısı. Yüksek çıkış açıklığı, bu düğme için çok sayıda alt düzey tüketiciye bağlı demektir.
- Orta: Giriş açısı + çıkış açısı. Bu düğme üzerinden geçiş yapan sayıda yol ölçer. Yüksek orta düğüm, grafa bir kavşakta bulunur.
- Patika Skoru: Hızlandırma × giriş açısı. Bu kısıtlama açılırken, altta yüklü iş ne kadar fazla akar ölçer.
Fabrika modeli, bu geometrik özelliklere fiziksel anlam katıyor:
- Yüksek arasındalık + yüksek patlama puanı = çalışkan düğüm. Bu engeli indirgeme olmadan, aşağıya yönelik aşamaları hazırlamadan = çöküş.
- Yüksek çıkış derecesi + düşük patlama puanı = açgözlü düğüm. Tüketirken üretmez. Durdurma yapmayı unutansın makine.
Patlama & Arasıntı Uygulamada
Bir DAG Okuma
5 düğüm zinciri üzerinde düşünün: A → B → C → D → E, ayrıca B → D ek kenarı.
- A: giren bağlantı sayısı 0, çıkan bağlantı sayısı 1, arasındalık 1. Kaynaş düğüm. Ona beslenen yok. Bir tüketici.
- B: giren bağlantı sayısı 1 (A'dan), çıkan bağlantı sayısı 2 (C ve D'ye), arasındalık 3. İki aşağıya yönelik düğme besliyor - bir fan-out noktası.
- C: giren bağlantı sayısı 1 (B'den), çıkan bağlantı sayısı 1 (D'ye), arasındalık 2. Geçiş düğümü.
- D: giren bağlantı sayısı 2 (B'den ve C'den), çıkan bağlantı sayısı 1 (E'ye), arasındalık 3. İki yoldan besleniyor.
- E: giren bağlantı sayısı 1 (D'den), çıkan bağlantı sayısı 0, arasındalık 1. Sertifika düğümü.
B ve D en yüksek arasındalığa (3) sahip. B, iki düğme besleyen fan-out'tur. D, iki yoldan beslenen birleşme noktasıdır. C'deki MOAD-0001 düzeltmenin uygulanmasından sonra, B→D yolundan ve C→D yolundan aynı anda patlama alır.
Düğüm Ölçütlerini Hesapla
Bağımlılık grafiği: A → B → C → D → E (bir zincir), ayrıca B → D ek kenarı.
C düğümünün ölçülen hızlanması, MOAD-0001 düzeltmesinin uygulanmasından sonra 50 katına çıkıyor.
Düzlem Defekt
MOAD-0007: Uzay Verisi Düz Bir Liste Olarak Sorgulanır
MOAD-0007 (Düzlem Defekti): uzay verisi düz bir liste olarak sorgulanır ve verinin geometrik yapısını dikkate almaz. Her sorgu, N nesneyi kontrol eder. O(N) her sorgu. M sorgiyle: O(M × N). Büyük ölçekte: felaket.
Gerçek zamanlı bir raycaster, bir sahneyi her nesneye karşı her ray'ı kontrol eder. 60 kare hızında, her karede 100 ray ve 10.000 sahne nesnesi: 60.000.000 kesim testi her saniye. Hepsi kaçınılabilecek.
Geometrik kavrayış: uzayda yapı vardır. Nesneler kümeleşmiştir. Bir ray'ın sol yarıdağı geçmezse, sol yarıdağdaki her nesneyi kaçırır. Düz bir liste bunu kullanamaz - her nesneyi, uzay konumuna göre dikkate alamaz. Bir uzaysal veri yapısı bunu sağlayabilir.
BVH: 3D'deki İkili Arama
BVH Nasıl Çalışır
BVH (Sınırlı Cisim Ağacı) 3D'yi iç içe geçmiş sınırlı kutuların bir ağacı ile ayırır. Her iç düğüm, çocuklarının geometrisini içeren bir sınırlı kutu tutar.
Bir raycast sorgusu:
1. Ana sınırlı kutuyu test et. Eğer ray'ı kaçırıyorsa, hemen çık - tüm sahne kesilir.
2. Eğer ray'ı isabetliyorsa, daha derine in. Çocukların sınırlı kutularını test et.
3. Herhangi bir çocuğa isabet etmezse: o dalı kes. Herhangi bir çocuğa isabet ederse: daha derine in.
4. Son düğümlerde: gerçek geometriyi test et.
Kesme geometri: her seviyede, kesilmeyen dallar ortadan kaldırılır. Dengeli bir BVH'nin derinliği d: 2^d yaprak düğümü vardır, ancak bir ray'ın pruned yol için gereken maksimum O(log N) karşılaştırma gereklidir.
Bu, ikili arama ile aynı geometrik argümandır: her karşılaştırma kalan arama alanını ikiye böler. İkili arama, sıralı bir dizi. BVH, 3D'yi ikiye böler. Yapı aynıdır - dengeli bir ikili ağaç ile pruninng her düğüm.
MOAD-0007 düzelme: düz liste yerine BVH'yi kullanın. Sorgu başına O(N) ile O(log N) arasında geçin. N=1.024 nesne ile, O(log₂ 1.024) = 10 karşılaştırma yerine 1.024.
BVH Hızlandirma Hesaplaması
Bir oyun sahnesi 1.024 nesneye sahiptir.
BVH olmadan: bir raycast, 1.024 nesneyi kontrol eder.
Dengeli bir BVH (2^10 = 1.024 yaprak) ile: bir raycast en fazla 10 seviyeyi geçer, her seviyede 2 çocuk karşılaştırması yapar.