Memoization للمبتدئ: من 2.1 ثانية لـ 0.03 مللي ثانية بسطر واحد

# مع Memoization: كل قيمة تُحسب مرة واحدة فقط
def fib_memo(n, memo):
    if n in memo:            # هل القيمة محفوظة؟ أعِدها فورًا
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print(fib_memo(35, {}))      # 9227465
# القياس الفعلي: ~0.03 مللي ثانية، 69 استدعاء فقط

في بايثون يوجد اختصار جاهز يفعل نفس الشيء بسطر واحد فوق الدالة:

لماذا الفرق بهذا الحجم؟

عندما تستدعي fib(5) بالطريقة العادية، تستدعي fib(4) وfib(3). وكل واحدة منهما تستدعي اثنتين أخريين، وهكذا. الشجرة تتضاعف في كل مستوى. النتيجة أن عدد الاستدعاءات ينمو نموًّا أُسّيًّا، أي تقريبًا 2 أُس n. عند n يساوي 35 هذا يعني عشرات الملايين.

المشكلة الحقيقية أن نفس القيمة تُحسب مرارًا. في شجرة استدعاءات fib(5) تُحسب fib(2) ثلاث مرات وfib(1) خمس مرات. تخيّل أنك تحل نفس مسألة الرياضيات من الصفر كل مرة تحتاج نتيجتها، بدل أن تكتبها في ورقة جانبية وتنظر إليها.

Memoization يقطع هذا الهدر. أول مرة يُحسب fib(2) يُخزَّن، وكل طلب لاحق له يعود من الذاكرة في خطوة واحدة. عدد القيم المختلفة التي تحتاج حسابًا فعليًا هو n فقط، فيتحوّل النمو من أُسّي إلى خطّي. هذا بالضبط هو الفرق بين 29 مليون استدعاء و69 استدعاء.

الـ trade-offs: ماذا تكسب وماذا تخسر

Memoization ليس مجانيًا. أنت تقايض الذاكرة بالسرعة، ولكل قرار ثمن:

• استهلاك الذاكرة: الكرّاسة تكبر مع كل مدخل جديد. fib(35) يخزّن 36 قيمة فقط، وهذا لا شيء يُذكر. لكن دالة تُستدعى بملايين المدخلات المختلفة قد تُراكم مئات الميجابايتات في الذاكرة.
• قِدَم البيانات: إذا كانت الدالة تعتمد على بيانات تتغيّر، ستُرجع الكرّاسة قيمة قديمة. الذاكرة لا تعرف أن العالم تغيّر.
• تكلفة البحث (overhead): كل استدعاء يدفع تكلفة صغيرة للبحث في القاموس. لو الدالة رخيصة جدًا أصلًا، قد يكون البحث أبطأ من الحساب نفسه.
• المدخلات يجب أن تكون قابلة للتجزئة (hashable): lru_cache لا يقبل قائمة أو قاموسًا كوسيط، لأنهما لا يصلحان مفتاحًا في الكرّاسة.

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

التقنية قوية لكنها ليست لكل حالة. تجنّبها في المواقف التالية:

• الدوال غير النقية: التي تقرأ من قاعدة بيانات، أو تستدعي API، أو تقرأ الوقت الحالي، أو تولّد رقمًا عشوائيًا.
• الدوال التي نادرًا ما تُستدعى بنفس المدخل: الكرّاسة لن تُصاب أبدًا، فتدفع تكلفة الذاكرة والبحث بلا أي فائدة.
• المدخلات غير المحدودة بلا سياسة حذف: استخدم maxsize محدودًا في lru_cache، وإلا تحوّلت الذاكرة إلى تسرّب صامت يكبر مع الوقت.
• الدوال الرخيصة جدًا: لو الحساب أرخص من البحث في القاموس، فالتحسين يضرّ ولا ينفع.

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

افتح كودك الآن وابحث عن دالة تكرارية (recursive) أو دالة تُستدعى كثيرًا بنفس الوسائط. أضف فوقها سطر @lru_cache(maxsize=None)، ثم قِس الزمن قبل وبعد باستخدام time.perf_counter(). لو لم يتغيّر الزمن، فهذا يعني أن مدخلاتك لا تتكرر، والكرّاسة هنا عبء بلا عائد، فاحذفها.

المصادر

• Donald Michie, "Memo Functions and Machine Learning", مجلة Nature، 1968 — الورقة التي صاغت مصطلح Memoization.
• توثيق بايثون الرسمي لـ functools.lru_cache — docs.python.org.
• Cormen, Leiserson, Rivest, Stein، "Introduction to Algorithms" (CLRS) — فصل البرمجة الديناميكية الذي يشرح الـ memoization رسميًا.
• القياسات الزمنية وعدد الاستدعاءات في المقال مأخوذة من تشغيل فعلي على Python 3.11 لدالة fib(35) بالطريقتين.