الحساب المسبق
في الخوارزميات ، الحساب المسبق هو إجراء عملية حسابية أولية قبل وقت التشغيل لتوليد جدول بحث يمكن استخدامه بواسطة خوارزمية لتجنب الحساب المتكرر في كل مرة يتم تنفيذها. غالبًا ما يتم استخدام الحساب المسبق في الخوارزميات التي تعتمد على نتائج الحسابات المكلفة التي لا تعتمد على مدخلات الخوارزمية. من الأمثلة البسيطة للحساب المسبق استخدام الثوابت الرياضية المبرمجة ، مثل π و e ، بدلاً من حساب تقريباتها بالدقة اللازمة في وقت التشغيل.
في قواعد البيانات ، يستخدم مصطلح التجسيد للإشارة إلى تخزين نتائج الحساب المسبق، [1] [2] كما هو الحال في العرض المجسد . [3] [4]
ملخص
إن الحساب المسبق لمجموعة من النتائج الوسيطة في بداية تنفيذ الخوارزمية يمكن أن يزيد غالبًا من كفاءة الخوارزمية بشكل كبير. ويصبح هذا مفيدًا عندما يتم تقييد أحد المدخلات أو أكثر بنطاق صغير بما يكفي بحيث يمكن تخزين النتائج في كتلة ذاكرة بحجم معقول. ولأن الوصول إلى الذاكرة ثابت في الأساس من حيث التعقيد الزمني (باستثناء تأخيرات التخزين المؤقت )، فإن أي خوارزمية تحتوي على مكون يتمتع بكفاءة أقل من الثبات على نطاق إدخال صغير يمكن تحسينها من خلال الحساب المسبق للقيم. وفي بعض الحالات، يمكن الحصول على خوارزميات تقريب فعالة من خلال حساب مجموعة فرعية منفصلة من القيم والاستيفاء لقيم الإدخال الوسيطة، لأن الاستيفاء هو أيضًا عملية خطية.
تاريخ
قبل ظهور أجهزة الكمبيوتر، كان الناس يستخدمون جداول البحث المطبوعة للقيم لتسريع الحسابات اليدوية للوظائف المعقدة، كما هو الحال في جداول المثلثات وجداول اللوغاريتم وجداول وظائف الكثافة الإحصائية [5]. غالبًا ما يتم تعليم أطفال المدارس حفظ " جداول الضرب " لتجنب حسابات الأرقام الأكثر استخدامًا (حتى 9 × 9 أو 12 × 12). حتى في وقت مبكر من عام 493 بعد الميلاد، كتب فيكتوريوس من آكيتاين جدول ضرب مكون من 98 عمودًا والذي أعطى ( بالأرقام الرومانية ) حاصل ضرب كل رقم من 2 إلى 50 مرة وكانت الصفوف عبارة عن "قائمة من الأرقام تبدأ بألف، وتنزل بالمئات إلى مائة، ثم تنزل بالعشرات إلى عشرة، ثم بالآحاد إلى واحد، ثم الكسور إلى 1/144" [6]
أمثلة
حتى تطبيقات الكمبيوتر الحديثة للوظائف المثلثية الرقمية غالبًا ما تستخدم جداول البحث المحسوبة مسبقًا لتوفير معاملات لخوارزميات الاستيفاء أو لتهيئة خوارزميات التقريب المتعاقبة .
تتضمن العديد من الهجمات على أنظمة التشفير عملية حسابية مسبقة.
تتضمن أمثلة الحوسبة المسبقة واسعة النطاق كجزء من الخوارزميات الفعالة الحديثة ما يلي:
- طاولات قوس قزح
- التجزئات المثالية
- هجوم المكعب
- أشجار BSP المحسوبة مسبقًا لحسابات الرؤية في الرسومات ثلاثية الأبعاد
- حساب مسبق للإشعاع للإضاءة في الرسومات ثلاثية الأبعاد
يستخدم المترجمون الحساب المسبق على نطاق واسع كوسيلة لزيادة سرعة وقت تشغيل الكود الناتج: يمكن اعتبار هذا الحساب المسبق في الواقع شكلاً من أشكال التقييم الجزئي لكود البرنامج نفسه. تتضمن أمثلة هذا النوع من الحساب المسبق تحليل تدفق البيانات وخطوات تقليل القوة .
انظر أيضا
مراجع
- ^ جياوي هان؛ ميشلين كامبر (9 يونيو 2011). استخراج البيانات: المفاهيم والتقنيات: المفاهيم والتقنيات. إلسيفير. ص. 159. رقم ISBN 978-0-12-381480-7.
- ^ Sven Groppe (29 أبريل 2011). إدارة البيانات ومعالجة الاستعلامات في قواعد بيانات الويب الدلالي. Springer Science & Business Media. ص. 178. ISBN 978-3-642-19357-6.
- ^ كارين مورتون. كيري أوزبورن؛ روبين ساندز؛ رياج شمس الدين؛ جاريد ستيل (28 أكتوبر 2013). برو أوراكل SQL. Apress. ص. 48. ردمك 978-1-4302-6220-6.
- ^ ماري-أودي أوفور؛ إستيبان زيماني (16 يناير 2012). Business Intelligence: First European Summer School, EBISS 2011, Paris, France, July 3-8, 2011, Tutorial Lectures. Springer Science & Business Media. ص. 43. ISBN 978-3-642-27357-5.
- ^ كامبل كيلي، مارتن ؛ كرواركين، ماري ؛ فلود، رايموند ؛ وآخرون، محررون (2003). تاريخ الجداول الرياضية من سومر إلى جداول البيانات . مطبعة جامعة أكسفورد. رقم ISBN 978-0-19-850841-0.
- ^ ماهر، ديفيد. دبليو جيه وجون ف. ماكوسكي. "الأدلة الأدبية على الحساب الروماني باستخدام الكسور"، فقه اللغة الكلاسيكي (2001) المجلد 96 العدد 4 (2001) ص 376-399. (انظر الصفحة ص 383).
