Hamming'in Geometrik Sezgisi
Hamming Her Yerde Geometri Gördü
Hamming'in Ch. 9 uyarıyla açılır: yüksek boyutlarda geometrik sezgi çöker. 3D'de, bir küre içeren küpün çoğunu doldurur. 10D'de, küre küpün hacminin %0,2'sinden azını kaplar. 100D'de, oran sıfıra yuvarlanır. Hacim yüzeye yakın yoğunlaşır. Noktalar merkezde değil, köşelere yakın kümelenir.
Hata düzeltme kodları bunu doğrudan kullandı. Hamming kodları, her kod sözcüğünün düzeltilebilir hataların bir küresyle çevrili olacak şekilde kod sözcüklerini n-boyutlu ikili uzaya yerleştirir. Geometri, kaç hatayı düzeltebileceğinizi belirler. n-uzayda küre paketlemesi, gerçek tehlikelerle ilgili bir matematik problemidir: küreleri daha yoğun paketleyin, daha fazla hatayı düzeltin.
Aynı geometrik başarısızlık modu algoritmik karmaşıklığa da uygulanır. Küçük N'de, O(N²) ve O(N) bir grafik üzerinde neredeyse özdeş 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 çöktüğü gibi. Küçük ölçekte yönetilebilir görünen şey ö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 ne olursa olsun aynı maliyet. Eğim yok.
- O(log N): yumuşak yükseliş eğrisi düzleşir. N her kare olduğunda iki katına çıkar. N'deki rakam sayısıyla orantılı olarak büyür.
- O(N): orijinden geçen çapraz bir çizgi. Maliyet N'yle orantılı olarak büyür.
- O(N log N): biraz daha dik çapraz. Çok hafif yukarı doğru eğilen bir çizgi.
- O(N²): parabol. N=100'de: 10.000 işlem. N=1.000'de: 1.000.000 işlem.
Kritik içgörü: iki karmaşıklık sınıfı arasındaki oran kendisi N'nin bir fonksiyonudur. N=10'da, O(N²) O(N)'den 10 kat daha pahalıdır. N=1.000'de, O(N²) 1.000 kat daha pahalı. N=1.000.000'de, 1.000.000 kat daha pahalı. Boşluk sadece büyümez — N'nin hızında büyür.
Bu, MOAD-0001 yamaları için neden önemli olduğunun geometrik argümanıdır. Bir bağımlılık çözücüyü O(N²)'den O(N)'ye taşımak sabit bir hızlanma değildir. N=50.000 pakette, 50.000 kat hızlanmadır. N=100.000'de, 100.000 kat hızlanmadır. Yamanın değeri problem boyutuyla büyür.
Genişleyen Boşluk
O(N²) ve O(N) ikisi de doğru sonuçlar verir.
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 Olarak
Yönlendirilmiş Asiklik Grafik
DAG (yönlendirilmiş asiklik grafik), bir geometrik yapıdır: yönetilen kenarlarla bağlı düğümler & döngü yok. Yazılım bağımlılık grafikleri, inşa hatları & veri akışı mimarileri tümü DAG oluşturur.
Her düğüm, kenarlarını sayarak ölçülen geometrik özellikler taşır:
- Gelen derece: düğüme varış kenarlarının sayısı. Yüksek gelen derece, birçok yukarı bağımlılığın bu düğümü beslemesi anlamına gelir.
- Giden derece: düğümden ayrılan kenarlarının sayısı. Yüksek giden derece, birçok aşağı tüketicinin bu düğüme bağlı olması anlamına gelir.
- Aradalık: gelen derece + giden derece. Bu düğümden kaç yol geçtiğini ölçer. Yüksek aradalık düğümü grafikte bir kavşakta oturtuk.
- Dalgalanma puanı: hızlanma × gelen derece. Bu darboğaz temizlendiğinde aşağıya ne kadar iş akışı yoğunlaştığını ölçer.
Fabrika modeli bu geometrik özellikleri fiziksel anlamla verir:
- Yüksek aradalık + yüksek dalgalanma puanı = çalışkan düğüm. Bu darboğazı aşağıyı hazırlamadan kaldırın = çöküş.
- Yüksek giden derece + düşük dalgalanma puanı = açgözlü düğüm. Üretmeden tüketir. Durmayı unutan makine.
Uygulamada Dalgalanma & Aradalık
DAG Okuma
5 düğümlü bir zincir düşünün: A → B → C → D → E, artı ek kenar B → D.
- A: gelen derece 0, giden derece 1, aradalık 1. Kaynak düğüm. Hiçbir şey beslemez. Bir tüketici.
- B: gelen derece 1 (A'dan), giden derece 2 (C'ye & D'ye), aradalık 3. İki aşağı düğümü besler — bir fan-out noktası.
- C: gelen derece 1 (B'den), giden derece 1 (D'ye), aradalık 2. Bir geçiş düğümü.
- D: gelen derece 2 (B'den & C'den), giden derece 1 (E'ye), aradalık 3. İki yoldan alır.
- E: gelen derece 1 (D'den), giden derece 0, aradalık 1. Batış düğümü.
B & D en yüksek aradalığı paylaşır (3). B fan-out: iki düğümü besler. D yakınsama noktası: iki yoldan alır. C'de MOAD-0001 yamasından sonra, D B→D yolu & C→D yolundan eşzamanlı olarak dalgalanma alır.
Düğüm Metriklerini Hesaplama
Bağımlılık grafiği: A → B → C → D → E (zincir), artı ek kenar B → D.
C düğümü MOAD-0001 yamасından sonra 50× ölçülen hızlanmaya sahiptir.
Flatland Kusuru
MOAD-0007: Uzaysal Veri Düz Liste Olarak Sorgulanmış
MOAD-0007 (Flatland Kusuru): uzaysal veri düz liste olarak sorgulanmış verilerin geometrik yapısını görmezden gelir. Her sorgu N nesneyi kontrol eder. Sorgu başına O(N). M sorguyla: O(M × N). Ölçekte: felaket.
Gerçek zamanlı ışın izleyici her nesneyi sahnede her ışına karşı kontrol eder. Saniye başına 60 çerçeve, çerçeve başına 100 ışın & 10.000 sahne nesnesi: saniye başına 60.000.000 kesişim testi. Hepsi kaçınılabilir.
Geometrik içgörü: uzayın yapısı vardır. Nesneler kümelenir. Bir ışın sahnedeki sol yarısını kaçırır, sol yarıdaki her nesneyi kaçırır. Düz liste bunu kullanamaz — nesnelerin uzaysal konumundan bağımsız olarak hepsini kontrol eder. Uzaysal veri yapısı yapabilir.
BVH: 3D'de İkili Arama
BVH Nasıl Çalışır
BVH (Sınırlayıcı Hacim Hiyerarşisi) 3D uzayını iç içe sınırlayıcı kutuların ağacına bölünür. Her iç düğüm çocuklarının tüm geometrisini içeren bir sınırlayıcı kutu tutar.
Işın izleme sorgusu:
1. Kök sınırlayıcı kutosunu test edin. Işın kaçırırsa, hemen çıkın — tüm sahne budanır.
2. Işın vurursa, çocuklara özyinele gidin. Her çocuğun sınırlayıcı kutosunu test edin.
3. Kaçıran her çocuk için: o alt ağacı budayın. Vuran her çocuk için: daha derin özyinele.
4. Yaprak düğümlerinde: gerçek geometriyi test edin.
Budama geometrisi: her seviyede, kesişmeyen dallar ortadan kaldırılır. Dengeli bir BVH derinlik d ile: 2^d yaprak düğümleri vardır, ama tek bir ışın budanmış yolu için en fazla O(log N) karşılaştırmasına ihtiyaç duyar.
Bu, ikili aramanın aynı geometrik argümanıdır: her karşılaştırma kalan arama alanını yarıya böler. İkili arama sıralanmış bir diziyi yarıya böler. BVH görünür 3D uzayını yarıya böler. Yapı tamamen aynı — her düğümde budamalı dengeli ikili ağaç.
MOAD-0007 onarımı: düz listeyi BVH ile değiştirin. Sorgu başına O(N)'den O(log N)'ye taşıyın. N=1.024 nesnede, O(log₂ 1.024) = 1.024 yerine 10 karşılaştırma.
BVH Hızlanmasını Hesaplama
Bir oyun sahnesinde 1.024 nesne vardır.
BVH olmadan: ışın izleme tüm 1.024 nesneyi kontrol eder.
Derinlik 10 (2^10 = 1.024 yaprak) dengeli BVH ile: ışın izleme en fazla 10 seviyeyi geçer, seviye başına 2 çocuk karşılaştırması.