الحدس الهندسي لهامنج
رأى هامنج الهندسة في كل مكان
يفتتح الفصل 9 من هامنج بتحذير: ينهار الحدس الهندسي في الأبعاد العالية. في البعد الثالث، تملأ الكرة معظم المكعب المحيط بها. في البعد العاشر، تشغل الكرة أقل من 0.2% من حجم المكعب. في البعد المئة، يقترب الكسر من الصفر. يتركز الحجم بالقرب من السطح. تتجمع النقاط بالقرب من الزوايا، وليس في المركز.
استغلت أكواده لتصحيح الأخطاء هذا مباشرة. تعبئ أكواد هامنج الكلمات المشفرة في فضاء ثنائي بأبعاد 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: 10,000 عملية. عند N=1,000: 1,000,000 عملية.
الرؤية الحرجة: النسبة بين فئتي تعقيد هي نفسها دالة N. عند N=10، O(N²) تكلفها 10× أكثر من O(N). عند N=1,000، O(N²) تكلفها 1,000× أكثر. عند N=1,000,000، تكلفها 1,000,000× أكثر. الفجوة لا تنمو فحسب — بل تنمو بمعدل N نفسه.
هذا هو الحجج الهندسي لسبب أهمية رقع MOAD-0001. نقل منحل الاعتمادية من O(N²) إلى O(N) ليس تسريعاً ثابتاً. عند N=50,000 حزمة، تسريع 50,000×. عند N=100,000، تسريع 100,000×. قيمة الرقعة تنمو مع حجم المسألة.
الفجوة المتسعة
O(N²) و O(N) كلاهما ينتج نتائج صحيحة.
عند N=10: O(N²) تكلفها 100 عملية، O(N) تكلفها 10 عمليات. النسبة: 10×.
عند N=1,000: O(N²) تكلفها 1,000,000 عملية، O(N) تكلفها 1,000 عملية.
الرسوم البيانية كهندسة
الرسم البياني غير الدوري الموجه
DAG (رسم بياني موجه غير دوري) هو بنية هندسية: عقد متصلة بحواف موجهة بدون دورات. الرسوم البيانية لاعتمادية البرامج، وخطوط أنابيب البناء، وعمائر تدفق البيانات كلها تشكل DAGs.
تحمل كل عقدة خصائص هندسية تُقاس بعد حوافها:
- درجة الداخل: عدد الحواف الوصول إلى العقدة. درجة داخل عالية تعني العديد من الاعتماديات الصاعدة تغذي هذه العقدة.
- درجة الخروج: عدد الحواف المغادرة للعقدة. درجة خروج عالية تعني العديد من المستهلكين النازلين يعتمدون على هذه العقدة.
- التوسطية: درجة الداخل + درجة الخروج. تقيس عدد المسارات التي تمر عبر هذه العقدة. عقدة عالية التوسطية تجلس عند تقاطع في الرسم البياني.
- درجة الفيضان: التسريع × درجة الداخل. تقيس كم عمل يفيض نازلاً عندما يزول هذا الاختناق.
يعطي النموذج الصناعي معنى فيزيائياً لهذه الخصائص الهندسية:
- توسطية عالية + درجة فيضان عالية = عقدة شغّال. إزالة هذا الاختناق دون إعداد النازل = انهيار.
- درجة خروج عالية + درجة فيضان منخفضة = عقدة نهام. تستهلك دون إنتاج. الآلة التي تنسى أن تتوقف.
الفيضان والتوسطية في الممارسة
قراءة DAG
تخيل سلسلة من 5 عقد: A → B → C → D → E، بالإضافة إلى حافة إضافية B → D.
- A: درجة داخل 0، درجة خروج 1، توسطية 1. عقدة مصدر. لا شيء يغذيها. مستهلك واحد.
- B: درجة داخل 1 (من A)، درجة خروج 2 (إلى C وإلى D)، توسطية 3. تغذي عقدتين نازلتين — نقطة انتشار.
- C: درجة داخل 1 (من B)، درجة خروج 1 (إلى D)، توسطية 2. عقدة مرور.
- D: درجة داخل 2 (من B ومن C)، درجة خروج 1 (إلى E)، توسطية 3. تستقبل من مسارين.
- E: درجة داخل 1 (من D)، درجة خروج 0، توسطية 1. عقدة غارقة.
تشترك B و D في أعلى توسطية (3). B هي الانتشار: تغذي عقدتين. D هي نقطة التقارب: تستقبل من مسارين. بعد رقعة MOAD-0001 عند C، تستقبل D فيضاناً من كل من مسار B→D و C→D بيسر.
حساب مقاييس العقدة
رسم بياني اعتماديات: A → B → C → D → E (سلسلة)، بالإضافة إلى حافة إضافية B → D.
العقدة C لها تسريع مقاس 50× بعد رقعة MOAD-0001.
عيب أرض السلام
MOAD-0007: بيانات مكانية مسؤولة كقائمة مسطحة
MOAD-0007 (عيب Flatland): البيانات المكانية المسؤولة كقائمة مسطحة تتجاهل البنية الهندسية للبيانات. كل استعلام يتحقق من كل N كائن. O(N) لكل استعلام. مع M استعلامات: O(M × N). على نطاق المقياس: كارثي.
يتحقق الراسم الشعاعي في الوقت الفعلي من كل كائن في المشهد مقابل كل شعاع. عند 60 إطار في الثانية، مع 100 شعاع لكل إطار و 10,000 كائن مشهد: 60,000,000 اختبار تقاطع في الثانية. كلهم قابلون للتجنب.
الرؤية الهندسية: الفضاء له بنية. الكائنات تتجمع. الشعاع الذي يفوت النصف الأيسر من المشهد يفوت كل كائن في النصف الأيسر. قائمة مسطحة لا يمكنها استغلال هذا — تتحقق من كل كائن بغض النظر عن الموقع المكاني. بنية بيانات مكانية يمكنها.
BVH: البحث الثنائي في 3D
كيف يعمل BVH
BVH (Bounding Volume Hierarchy) يفكك فضاء 3D إلى شجرة من الأحجام المحيطة المتداخلة. كل عقدة داخلية تحمل حجماً محيطاً يحتوي على كل الهندسة الخاصة بأطفالها.
استعلام الشعاع:
1. اختبر الحجم المحيط للجذر. إذا فشل الشعاع، اخرج فوراً — المشهد كله مقصوص.
2. إذا أصاب الشعاع، تكرار إلى الأطفال. اختبر الحجم المحيط لكل طفل.
3. لكل طفل يفشل: اقصص الشجرة الفرعية. لكل طفل يصيب: تكرار أعمق.
4. في العقد الورقية: اختبر الهندسة الفعلية.
هندسة القصص: في كل مستوى، فروع غير متقاطعة تُزال. مع BVH متوازن بعمق d: عقد 2^d ورقية توجد، لكن شعاع واحد يحتاج إلى معظم O(log N) مقارنات للمسار المقصوص.
هذا هو نفس الحجج الهندسي للبحث الثنائي: كل مقارنة تنصف فضاء البحث الباقي. البحث الثنائي ينصف مصفوفة مرتبة. BVH ينصف فضاء 3D المرئي. البنية متطابقة — شجرة ثنائية متوازنة مع قصص في كل عقدة.
إصلاح MOAD-0007: استبدل القائمة المسطحة بـ BVH. انتقل من O(N) لكل استعلام إلى O(log N) لكل استعلام. عند N=1,024 كائن، O(log₂ 1,024) = 10 مقارنات بدلاً من 1,024.
حساب تسريع BVH
مشهد لعبة به 1,024 كائن.
بدون BVH: يتحقق الشعاع من كل 1,024 كائن.
مع BVH متوازن بعمق 10 (2^10 = 1,024 ورقة): يعبر الشعاع معظم 10 مستويات، مع 2 مقارنة طفل لكل مستوى.