المستوى المطلوب: متوسط. المقال ده مناسب لو انت كاتب كود بالفعل وعارف يعني إيه دالة تنادي نفسها (recursion)، لكن لسه مش فاهم ليه بعض الدوال بتاخد وقت رهيب وإزاي سطر واحد بيصلّحها. لو انت مبتدئ خالص، تقدر تكمل عادي: كل مفهوم صعب هتلاقيه متشروح بمثال بسيط الأول.
Memoization في بايثون: ليه fib(35) بياخد ثواني وبسطر واحد يبقى فوري
لو دالة عندك بتحسب نفس القيمة آلاف المرات، انت بتدفع تمن الحساب ده كله من غير فايدة. الـ Memoization بيخلّي الدالة تفتكر النتايج اللي حسبتها قبل كده، فبتتحوّل من ثواني لأجزاء من الألف من الثانية بسطر واحد. هنا هتشوف الفرق بأرقام مقاسة، وهتعرف بالظبط إمتى تستخدمه وإمتى لأ.
المشكلة باختصار
خد أشهر مثال: متتابعة فيبوناتشي. كل رقم هو مجموع الرقمين اللي قبله. تكتبها بـ recursion في 3 سطور وتبقى شكلها نضيف. المشكلة إن الكود ده بيعيد حساب نفس القيم ملايين المرات. الدالة مش بتفتكر إنها حسبت fib(20) قبل كده، فبتحسبها من الأول في كل مرة. النتيجة: زمن التنفيذ بيتضاعف تقريبًا مع كل رقم بتزوّده على n.
المفهوم بمثال بسيط الأول
تخيّل طالب بيحل مسألة، وكل شوية محتاج يعرف حاصل ضرب 7 × 8. في المرة الأولى بيقعد يعدّها على صوابعه ويطلع 56. الطبيعي إنه يكتب 56 في ورقة جنبه. بعد كده كل ما يحتاج 7 × 8 تاني، بيبص للورقة على طول بدل ما يعدّها من جديد. الورقة دي هي الـ كاش (cache)، وفعل إنه يكتب النتيجة أول مرة ويقراها بعد كده هو بالظبط الـ Memoization.
دلوقتي المفهوم علميًا: الـ Memoization أسلوب لتحسين الأداء بتخزّن فيه ناتج الدالة مربوطًا بالمدخلات بتاعتها. أول ما تتنادى الدالة بمدخل معيّن، بتحسب الناتج وتحفظه في جدول (غالبًا dict) المفتاح فيه هو المدخلات. أي نداء تاني بنفس المدخلات بيرجّع القيمة المحفوظة على طول من غير إعادة حساب. الشرط الأساسي إن الدالة تبقى نقية (pure): نفس المدخل لازم يديك نفس المخرج دايمًا، ومن غير آثار جانبية.
نشوف المشكلة بالكود
ده الكود الساذج، وبنقيس زمنه فعليًا:
import time
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
start = time.perf_counter()
print(fib(35)) # 9227465
elapsed = time.perf_counter() - start
print(f"الزمن: {elapsed:.2f} ثانية")
على معالج عادي بـ CPython 3.11، الكود ده بياخد حوالي 6 ثواني عشان يحسب fib(35). السبب إنه بينفّذ جسم الدالة 29,860,703 مرة. الرقم ده مش عشوائي: عدد النداءات في التكرار الساذج بيساوي تقريبًا 2 × fib(n+1) − 1، وده نمو أُسّي بمرتبة O(2^n). جرّب fib(40) وهتستنى دقيقة أو أكتر.
الحل: سطر واحد يقلب الموازين
بايثون فيه decorator جاهز اسمه بيعمل الكاش ده أوتوماتيك:
