المستوى المطلوب: متوسط. المقال ده مناسب لو انت كاتب كود بالفعل وعارف يعني إيه دالة تنادي نفسها (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 جاهز اسمه functools.lru_cache بيعمل الكاش ده أوتوماتيك:

import time
from functools import lru_cache

@lru_cache(maxsize=None)
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 * 1000:.4f} مللي ثانية")

النتيجة نفسها (9227465)، لكن دلوقتي جسم الدالة بيتنفّذ 36 مرة بس بدل 29.8 مليون، والزمن بينزل لأجزاء من الألف من المللي ثانية. التعقيد اتحوّل من O(2^n) لـ O(n)، لأن كل قيمة من fib(0) لـ fib(35) بتتحسب مرة واحدة وبس.

ولو عايز تعمل الكاش بإيدك عشان تفهم اللي بيحصل جوّه، ده نفس المبدأ بـ dict:

cache = {}

def fib(n):
    if n in cache:          # لقيناها في الورقة؟ رجّعها على طول
        return cache[n]
    if n < 2:
        result = n
    else:
        result = fib(n - 1) + fib(n - 2)
    cache[n] = result       # اكتبها في الورقة لأول مرة
    return result

سيناريو واقعي مش مجرد فيبوناتشي

لو عندك API بيحسب سعر شحنة بناءً على (المدينة، الوزن)، وبيتنده 5000 مرة في الدقيقة، أغلب الطلبات بتكون على نفس المدن المشهورة. لو الحساب بياخد 40 مللي ثانية، و80% من الطلبات مكررة، الـ Memoization بينزّل متوسط زمن الاستجابة من 40 لحوالي 8 مللي ثانية، ويخفّف الضغط على الـ DB بنسبة تقارب 80%. الافتراض هنا إن نتيجة الحساب ثابتة للمدخل نفسه خلال فترة صلاحية معقولة.

الـ trade-offs اللي لازم تعرفها

مفيش حاجة ببلاش. الـ Memoization بيقايض الذاكرة مقابل السرعة. كل نتيجة بتتخزّن، فلو المدخلات كتير ومتنوعة، الكاش بيكبر ويستهلك رام. مع lru_cache(maxsize=None) الكاش بيفضل يكبر بلا حدود؛ لو ده يقلقك، حدّد رقم زي maxsize=1024 عشان يشيل الأقل استخدامًا. المكسب: سرعة رهيبة. الخسارة: استهلاك ذاكرة يتناسب مع عدد المدخلات المختلفة، زائد إن نتايج قديمة ممكن تفضل محفوظة بعد ما تبقى غلط.

متى لا تستخدم هذه الطريقة

• لو الدالة مش نقية: بتقرا وقت النهارده، أو رقم عشوائي، أو بيانات بتتغير من قاعدة بيانات. هتكاش نتيجة قديمة وتديها للعميل غلط.
• لو المدخلات مش قابلة للتجزئة (unhashable) زي list أو dict؛ lru_cache محتاج مفتاح hashable. حوّلها لـ tuple الأول.
• لو كل نداء بمدخل مختلف ومفيش تكرار أصلًا، الكاش هياكل ذاكرة من غير أي مكسب في السرعة.
• لو الحساب أصلًا رخيص جدًا، تكلفة إدارة الكاش ممكن تبقى أغلى من الحساب نفسه.

الخطوة التالية

افتح أبطأ دالة recursive عندك دلوقتي، وشوف: هل بتتنده بنفس المدخلات أكتر من مرة؟ لو أه، وكانت نقية ومدخلاتها hashable، حط فوقها سطر @lru_cache(maxsize=None) وقِس الزمن بـ time.perf_counter قبل وبعد. لو الفرق كبير، انت لقيت مشكلة كانت مستخبية. لو الفرق صفر، يبقى مفيش تكرار في المدخلات والمشكلة في حتة تانية خالص.

المصادر

• توثيق بايثون الرسمي لـ functools.lru_cache وcache: docs.python.org/3/library/functools.html
• تعريف Memoization ونشأته: en.wikipedia.org/wiki/Memoization
• عدد نداءات فيبوناتشي الساذجة وعلاقتها بالنمو الأُسّي — Dynamic Programming، MIT OpenCourseWare 6.006: ocw.mit.edu/courses/6-006
• شرط الدالة النقية (pure function): en.wikipedia.org/wiki/Pure_function