دالة مرتبطة بالذاكرة

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
الموسوعة الحرة

في علم الحاسوب ، تُعتبر المسألة الحسابية محدودة الذاكرة عندما يتحدد وقت إنجازها بشكل أساسي بكمية الذاكرة الحرة المطلوبة لتخزين البيانات . وهذا يختلف عن الخوارزميات التي تُعتبر محدودة الحساب ، حيث يكون عدد خطوات الحساب الأساسية هو العامل الحاسم.

يمكن أحيانًا الموازنة بين حدود الذاكرة والحساب، على سبيل المثال عن طريق حفظ وإعادة استخدام النتائج الأولية أو استخدام جداول البحث .

الدوال المرتبطة بالذاكرة ودوال الذاكرة

ترتبط الوظائف المرتبطة بالذاكرة والوظائف المرتبطة بالذاكرة من حيث أن كليهما ينطوي على وصول مكثف إلى الذاكرة، ولكن يوجد فرق بينهما.

تستخدم دوال الذاكرة تقنية برمجة ديناميكية تُسمى التخزين المؤقت (memoization) للتخفيف من عدم كفاءة الاستدعاء الذاتي (recursion) الذي قد يحدث. تعتمد هذه التقنية على فكرة بسيطة تتمثل في حساب وتخزين حلول المسائل الفرعية، بحيث يمكن إعادة استخدام هذه الحلول لاحقًا دون الحاجة إلى إعادة حساب المسائل الفرعية . يُعدّ خوارزمية حساب أعداد فيبوناتشي المثال الأشهر الذي يستفيد من التخزين المؤقت . يستخدم الكود الزائف التالي الاستدعاء الذاتي والتخزين المؤقت، ويعمل في وقت معالجة خطي :

فيبوناتشي ( ن ) { من أجل i = 0 إلى n - 1 النتائج [ i ] = -1 // -1 تعني غير معرفreturn Fibonacci_Results ( results , n ); }Fibonacci_Results ( results , n ) { if ( results [ n ] != -1 ) // إذا تم حلها من قبل، فأرجع results [ n ] // ابحث عنها. if ( n == 0 ) val = 0 else if ( n == 1 ) val = 1 else val = Fibonacci_Results ( results , n -2 ) + Fibonacci_Results ( results , n -1 ) results [ n ] = val // احفظ هذه النتيجة لإعادة استخدامها.return val }

قارن ما سبق بخوارزمية تستخدم التكرار فقط، وتعمل في وقت معالجة مركزي أسي :

دالة فيبوناتشي التكرارية ( n ) { إذا كان ( n == 0 ) أرجع 0، إذا كان ( n == 1 ) أرجع 1return Recursive_Fibonacci ( n -1 ) + Recursive_Fibonacci ( n -2 ) }

على الرغم من أن الخوارزمية التي تعتمد على التكرار فقط أبسط وأكثر أناقة من الخوارزمية التي تستخدم التكرار والتخزين المؤقت، إلا أن الأخيرة تتمتع بتعقيد زمني أقل بكثير من الأولى.

مصطلح "الدالة المقيدة بالذاكرة" حديث الاستخدام نسبيًا، ويُستخدم أساسًا لوصف دالة تستخدم عملية XOR وتتألف من سلسلة من العمليات الحسابية، حيث تعتمد كل عملية على سابقتها. لطالما كانت دوال الذاكرة أداةً مهمةً لتحسين التعقيد الزمني، إلا أن تطبيقات الدوال المقيدة بالذاكرة كانت أقل بكثير.

استخدام الدوال المرتبطة بالذاكرة لمنع البريد العشوائي

قد تكون الوظائف المقيدة بالذاكرة مفيدة في نظام إثبات العمل الذي يمكن أن يردع البريد العشوائي ، والذي أصبح مشكلة ذات أبعاد وبائية على الإنترنت .

في عام ١٩٩٢، نشرت الباحثتان في شركة IBM، سينثيا دورك وموني ناور، ورقة بحثية في مؤتمر CRYPTO 1992 بعنوان " التسعير عبر المعالجة أو مكافحة البريد العشوائي " [ ١ ] ، مقترحتين إمكانية استخدام وظائف تعتمد على وحدة المعالجة المركزية لردع المُسيئين عن إرسال البريد العشوائي. استندت هذه الخطة إلى فكرة أن مستخدمي الحاسوب أكثر عرضة لإساءة استخدام الموارد إذا كانت تكلفة إساءة استخدامها ضئيلة: والسبب الرئيسي وراء انتشار البريد العشوائي هو أن إرسال بريد إلكتروني لا يكلف مُرسليه شيئًا يُذكر.

اقترح دوورك وناور أنه يمكن تقليل البريد العشوائي عن طريق إضافة تكلفة إضافية في شكل عملية حسابية مكلفة لوحدة المعالجة المركزية : ستستهلك الوظائف المرتبطة بوحدة المعالجة المركزية موارد وحدة المعالجة المركزية في جهاز المرسل لكل رسالة، مما يمنع إرسال كميات هائلة من البريد العشوائي في فترة قصيرة.

تتلخص الآلية الأساسية للحماية من إساءة الاستخدام فيما يلي: بافتراض وجود مُرسِل ومُستقبِل ورسالة بريد إلكتروني، إذا وافق المُستقبِل مُسبقًا على استلام البريد الإلكتروني من المُرسِل، تُرسَل الرسالة بالطريقة المعتادة. وإلا، يُجري المُرسِل عملية حسابية باستخدام دالة G(Message) ويرسل (Message, G(Message)) إلى المُستقبِل. يتحقق المُستقبِل مما إذا كانت الرسالة التي يستلمها من المُرسِل مطابقة للصيغة (Message, G(Message)) . إذا كانت كذلك، يقبل المُستقبِل الرسالة. وإلا، يرفضها.

تم اختيار الدالة G() بحيث يكون التحقق من قبل المُستلم سريعًا نسبيًا (مثلاً، يستغرق جزءًا من الألف من الثانية) ويكون الحساب من قبل المُرسل بطيئًا نوعًا ما (يستغرق عدة ثوانٍ على الأقل). لذلك، سيُحجم المُرسل عن إرسال الرسالة إلى مُستلمين مُتعددين دون اتفاق مُسبق: إذ ستصبح تكلفة حساب G() بشكل مُتكرر، من حيث الوقت وموارد الحوسبة، باهظة للغاية بالنسبة لمُرسل الرسائل المُزعجة الذي ينوي إرسال ملايين الرسائل الإلكترونية.

تكمن المشكلة الرئيسية في استخدام المخطط المذكور أعلاه في أن المعالجات المركزية السريعة تُجري العمليات الحسابية بسرعة أكبر بكثير من المعالجات البطيئة. علاوة على ذلك، تتميز أنظمة الحاسوب المتطورة ببنية تحتية متطورة وميزات أخرى تُسهّل العمليات الحسابية. ونتيجة لذلك، لن يتأثر مُرسل الرسائل المزعجة الذي يمتلك نظامًا متطورًا بهذا الردع، بينما سيتأثر المستخدم العادي الذي يمتلك نظامًا متوسطًا سلبًا. فإذا استغرقت عملية حسابية بضع ثوانٍ على جهاز حاسوب جديد ، فقد تستغرق دقيقة على جهاز حاسوب قديم، وعدة دقائق على جهاز مساعد رقمي شخصي ، وهو ما قد يكون مزعجًا لمستخدمي أجهزة الحاسوب القديمة، ولكنه غير مقبول على الأرجح لمستخدمي أجهزة المساعد الرقمي الشخصي. ويُعدّ التفاوت في سرعة المعالج المركزي أحد أبرز العوائق أمام الانتشار الواسع لأي مخطط يعتمد على وظيفة مُقيدة بالمعالج. لذلك، يهتم الباحثون بإيجاد وظائف تُقيّمها معظم أنظمة الحاسوب بنفس السرعة تقريبًا، بحيث تُقيّم الأنظمة المتطورة هذه الوظائف أسرع قليلًا من الأنظمة منخفضة الأداء (بسرعة تتراوح بين 2 و10 أضعاف، ولكن ليس بين 10 و100 ضعف) كما قد يُوحي به التفاوت في سرعة المعالج المركزي. تعتبر هذه النسب " مساواة " كافية للتطبيقات المقصودة: فالوظائف فعالة في ردع التجاوزات ولا تضيف تأخيرًا كبيرًا على التفاعلات المشروعة، عبر مجموعة واسعة من الأنظمة.

يتمثل النهج الجديد القائم على المساواة في الاعتماد على الدوال المرتبطة بالذاكرة. وكما ذُكر سابقًا، فإن الدالة المرتبطة بالذاكرة هي دالة يهيمن وقت الوصول إلى الذاكرة على وقت تنفيذها. تصل هذه الدالة إلى مواقع في منطقة واسعة من الذاكرة بطريقة غير متوقعة، مما يجعل استخدام ذاكرة التخزين المؤقت غير فعال. في السنوات الأخيرة، شهدت سرعة المعالجات المركزية نموًا هائلًا، لكن التقدم في تطوير ذاكرة رئيسية أسرع كان ضئيلًا نسبيًا. وبما أن نسب زمن استجابة الذاكرة للأجهزة المصنعة في السنوات الخمس الماضية لا تتجاوز عادةً اثنين، ودائمًا ما تكون أقل من أربعة، فإن الدالة المرتبطة بالذاكرة ستظل مناسبة لمعظم الأنظمة في المستقبل المنظور.

انظر أيضاً

مراجع

  1. ↑ دورك، سينثيا ؛ ناور، موني (1992). "التسعير من خلال معالجة البريد العشوائي أو مكافحته" . التطورات في علم التشفير - CRYPTO' 92. سلسلة محاضرات في علوم الحاسوب. المجلد  740. الصفحات 139-147 . doi : 10.1007/3-540-48071-4_10 . ISBN  978-3-540-57340-1.( نسخة محدثة من نفس الشيء )