الـ Memoization: خلّي دالتك تفتكر الإجابة بدل ما تحسبها من الأول

مستوى المقال: مبتدئ. لو لسه بادئ في البرمجة وسمعت كلمة Memoization وحسّيتها معقّدة، المقال ده ليك. هتخرج منه فاهم الفكرة وقادر تطبّقها في سطر واحد.

الـ Memoization: خلّي دالتك تفتكر الإجابة بدل ما تحسبها من الأول

نفس الدالة ممكن تشتغل في جزء من الثانية، أو تتعلّق ثواني طويلة، والفرق سطر واحد بس. الحيلة اسمها Memoization: بدل ما الدالة تعيد حساب نفس النتيجة كل مرة، بتحفظها وترجّعها جاهزة.

مثال بسيط الأول

تخيّل طالب بيحل مسألة رياضة، ولقى إنه محتاج ناتج 7×8 خمس مرات في نفس الورقة. المرة الأولى حسبها وكتب "56" على الهامش. باقي المرات بصّ على الهامش وخلّص في ثانية بدل ما يعيد الضرب.

ده بالظبط اللي بيعمله الـ Memoization: أول مرة الدالة تحسب، تكتب الناتج في جنب (الذاكرة)، وأي مرة تانية تقرأه بدل ما تحسبه من الأول.

يعني إيه علميًا

الـ Memoization أسلوب تحسين (optimization) بتخزّن فيه نتيجة استدعاء الدالة مربوطة بمدخلاتها. لو الدالة اتنادت بنفس المدخل تاني، بترجّع النتيجة المخزّنة من غير إعادة حساب. الشرط الأساسي: الدالة لازم تكون "نقية" (pure) — نفس المدخل يدّي نفس المخرج دايمًا، من غير آثار جانبية.

المشكلة في مثال حقيقي: متتالية فيبوناتشي

خد دالة فيبوناتشي اللي بتنادي نفسها. من غير Memoization، حساب fib(40) بيكرّر نفس القيم ملايين المرات. عدد الاستدعاءات بينمو أُسّيًا وبيوصل 331,160,281 استدعاء — أكتر من 331 مليون. مع Memoization بينزل لـ 41 عملية بس، لأن كل قيمة بتتحسب مرة واحدة وتتخزّن.

الكود: قبل وبعد

import time

# من غير Memoization — بطيء
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# مع Memoization — سريع
cache = {}
def fib_memo(n):
    if n < 2:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return cache[n]

t = time.perf_counter()
fib(35)
print("fib بدون:", round(time.perf_counter() - t, 3), "ثانية")

t = time.perf_counter()
fib_memo(35)
print("fib memo:", round((time.perf_counter() - t) * 1000, 4), "مللي ثانية")

على جهاز عادي، fib(35) من غير Memoization بياخد حوالي 1.6 ثانية. النسخة اللي فيها Memoization بتخلّص في حوالي 0.02 مللي ثانية — يعني تحسّن أكتر من 10 آلاف مرة على نفس الجهاز. في بايثون تقدر تكسب نفس النتيجة بسطر واحد فوق الدالة باستخدام functools.lru_cache:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

الـ trade-off: بتكسب إيه وبتخسر إيه

بتكسب سرعة كبيرة، بتخسر ذاكرة. كل نتيجة محفوظة بتاخد مكان في الـ RAM. الافتراض هنا إن المدخلات بتتكرر فعلًا، وإن الحساب نفسه أغلى من قراءة قيمة من الذاكرة. لو المدخلات دايمًا مختلفة، الكاش هيكبر من غير أي فايدة.

متى لا تستخدم Memoization

• لو الدالة مش نقية — بترجّع نتيجة مختلفة لنفس المدخل، أو بتقرأ من قاعدة بيانات بتتغيّر.
• لو المدخلات دايمًا مختلفة ومفيش تكرار — هتخزّن بلا فايدة.
• لو الحساب رخيص أصلًا — إدارة الكاش ممكن تبقى أغلى من الحساب نفسه.
• لو الذاكرة محدودة والكاش ممكن يكبر بلا حدود — استخدم حجم محدود زي lru_cache(maxsize=1000).

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

افتح أي دالة عندك بتتنادى كتير بنفس المدخلات، وحط فوقها @lru_cache(maxsize=None)، وقيس الزمن قبل وبعد بـ time.perf_counter(). لو الفرق واضح، يبقى الدالة كانت بتكرّر شغل فعلًا. لو مفيش فرق، يبقى مفيش تكرار ومش محتاجها.

المصادر

• Python Docs — functools.lru_cache: https://docs.python.org/3/library/functools.html#functools.lru_cache
• Wikipedia — Memoization: https://en.wikipedia.org/wiki/Memoization
• Wikipedia — Fibonacci sequence (نمو الاستدعاءات الأُسّي): https://en.wikipedia.org/wiki/Fibonacci_sequence