فهم الجبري لهامنج
رأى هامنج الجبر في كل مكان
تبدأ الفصل 9 لهامنج بشعار: ينهار فهم الجبر في الأبعاد العالية. في 3D، تملأ الكرة معظم مكعبها المحيطي. في 10D، تشغل الكرة أقل من 0.2% من حجم المكعب. في 100D، يتقارب العدد بنسبة صفر. تركز الحجم بالقرب من السطح. تجمع النقاط بالقرب من الزوايا وليس من مركز الكرة.
استغلت كوداته التصحيح للأخطاء هذا بشكل مباشر. كودات هامنج تجمع كلمات المصدر في الفضاء البيني n-بعدي بحيث يكون كل كلمة مصدر محاطة بسفر من الأخطاء القابلة للتصحيح. يحدد الجبر كمية الأخطاء التي يمكن تصحيحها. تجميع الكرات في الفضاء n-بعدي مشكلة رياضية ذات عواقب حقيقية: تجمع الكرات بشكل أقل كثافة، تصحيح أخطاء أكثر.
تطبق نفس مشكلة الفهم الجبري على تعقيد الخوارزميات. في نطاق صغير من N، يبدو O(N²) وO(N) على حد سواء على الرسم البياني. الفجوة بينهم تبدو مرتاحة. في الأبعاد العالية، تفجر الفجوة - تماما مثل انهيار نسبة حجم الكرة في الأبعاد العالية. ما يبدو مرتاحا على نطاق صغير يصبح مستحيلا على نطاق كبير.
شكل كل طبقة التعقيد
رسم التعقيد
لدي كل طبقة التعقيد شكل:
- O(1): خط أفقي. التكلفة نفسها بغض النظر عن N. لا توجد ميل.
- O(log 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، تكلف O(N²) 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 (موجه غير مخالطة) هي بنية هندسية: العقد متصلّة بروابط موجهة بدون دوائر. جميع شبكات العلاقات بين البرمجيات ومخططات البناء ونظم تدفق البيانات تتشكل كشبكات DAG.
يحمل كل عقدة خصائص هندسية يتم قياسها عن طريق عدّ رؤوسها:
- درجة الدخول: عدد الروابط التي تصل إلى العقدة. درجة الدخول العالية تعني أن العديد من الاعتماديات العليا تروي هذه العقدة.
- درجة الخروج: عدد الروابط التي تخرج من العقدة. درجة الخروج العالية تعني أن العديد من المستهلكين الأدنى يعتمدون على هذه العقدة.
- درجة الوساطة: درجة الدخول + درجة الخروج. تقيس مدى عدد المسارات التي تمر عبر هذه العقدة. عقدة ذات درجة وسيطة عالية تقع في مفترق الطرق في الشبكة.
- درجة التزايد: السرعة × درجة الدخول. تقيس كمية العمل التي تتدفق نحو الأسفل عندما يتضح هذا المحول.
يُعطى المعنى المادي لهذه خصائص الهندسة من نموذج المصنع:
- درجة بينس بينسيس عالية + درجة قفز عالية = عقدة متعطشة العمل. إزالة هذا الحاجز بدون توجيه الأعمال الأدناه = انهيار.
- درجة خروج عالية + درجة قفز منخفضة = عقدة طعام. تستهلك بدون إنتاج. الآلة التي تنس الإيقاف.
القفز والبينس بينسيس في الممارسة
قراءة DAG
考虑一个5节点链:A → B → C → D → E，加上一个额外的边B → D。
- A: in-degree 0, out-degree 1, betweenness 1. Source node. Nothing feeds it. One consumer.
- B: in-degree 1 (from A), out-degree 2 (to C and to D), betweenness 3. Feeds two downstream nodes — a fan-out point.
- C: in-degree 1 (from B), out-degree 1 (to D), betweenness 2. A pass-through node.
- D: in-degree 2 (from B and from C), out-degree 1 (to E), betweenness 3. Receives from two paths.
- E: in-degree 1 (from D), out-degree 0, betweenness 1. Sink node.
B and D share the highest betweenness (3). B is the fan-out: it feeds two nodes. D is the convergence point: it receives from two paths. After a MOAD-0001 patch at C, D receives surge from both the B→D path and the C→D path simultaneously.
حساب معطيات العقد
A dependency graph: A → B → C → D → E (a chain), plus an additional edge B → D.
Node C has a measured speedup of 50× after a MOAD-0001 patch.
عيوب بلاد المflatland
MOAD-0007: استعلام البيانات المكانية كقائمة رقيقة
MOAD-0007 (عيوب بلاد المflatland): استعلام البيانات المكانية كقائمة رقيقة يتجاهل تركيب الجيومتيرية للبيانات. ي провер كل نماذج الاستعلام N. O (N) لكل استعلام. مع M الاستعلامات: O (M × N). على مقياس: كارثي.
متصفح خطي زمني ي провер كل الأشياء في المشهد ضد كل شعاع. بسرعة 60 إطارًا في الثانية، مع 100 شعاعًا في الإطار و 10,000 شیء في المشهد: 60,000,000 اختبار التقاطع لكل ثانية. كلها يمكن تجنبها.
فكرة الجيومتيرية: المكان له تركيب. الأشياء تجمعات. شعاع يmiss النصف الأيسر للمكان يmiss كل شيء في النصف الأيسر. القائمة المسطحة لا يمكنها استغلال هذا - تقوم بفحص كل شيء بغض النظر عن الموقع المكاني. هيكل بيانات المكاني يمكن.
BVH: البحث الثنائي في 3D
كيف يعمل BVH
BVH (Bounding Volume Hierarchy) يقسم المساحة ثلاثية الأبعاد إلى شجرة من المخازن المتصلة المربوطة. كل عقدة داخلية تحتوي على صندوق حدودي يحتوي على جميع أطفالها من الجيومتيريا.
استعلام تصفح الشعاع:
1. اختبار الصندوق الحدودي الأساسي. إذا miss الشعاع، انتهي الأمر فوريًا - تم اقتطاع المشهد بأكمله.
2. إذا لامس، استمر إلى الأطفال. اختبار كل صندوق حدودي.
3. لكل طفل الذي miss: اقطع هذا العمر. لكل طفل الذي لامس: استمر deeper.
4. في العقد الفوقية: اختبار الجيومتيريا الفعلية.
المظهر الجيومتيري للقص: في كل مستوى، يتم إلغاء الشعاب غير المتطايرة. مع BVH متوازن من عمق d: 2^d العقد الفوقية موجودة، لكن شعاع واحد يحتاج إلى أقصى O (log N) المقارنات للطريق المقطوع.
هذا هو نفس حجة الجيومتيريا التي تم استخدامها في البحث الثنائي: كل مقارنة تقسم المساحة البحثية الناتجة بمقدار نصف. البحث الثنائي يقسم المصفوفة المرتبة. BVH يقسم المساحة ثلاثية الأبعاد. الهيكل هو نفسه - شجرة ثنائية الحالة متوازنة مع القص في كل عقدة.
تصحيح MOAD-0007: استبدل القائمة المستوية بBVH. انتقل من O (N) لكل استعلام إلى O (log N) لكل استعلام. عند N = 1,024 الأشياء، O (log₂ 1,024) = 10 المقارنات بدلاً من 1,024.
حساب تسرع BVH
لقد كانت مشهد اللعب يحتوي على 1,024 جسمًا.
بدون BVH: يفحص cast الرAYS جميع الجسيمات 1,024.
باستخدام BVH متوازن عمق 10 (2^10 = 1,024 ورقة): يتفاعل cast الرAYS بأكثر من 10 مستوى، مع 2 تحليل للأطفال لكل مستوى.