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

Memoization: تخزين نتيجة الدالة بدل إعادة حسابها

دالة fib(35) المكتوبة بالطريقة العادية تأخذ 2.1 ثانية وتنفّذ 29,860,703 استدعاء. نفس الدالة بعد إضافة Memoization تأخذ 0.03 مللي ثانية و69 استدعاء فقط. هذا المقال يشرح سبب هذا الفرق الضخم، وكيف تطبّق التقنية بنفسك في دقائق.

المشكلة باختصار

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

الفكرة بمثال بسيط: موظف الاستقبال وكرّاسة الأرقام

تخيّل موظف استقبال في شركة كبيرة. كل قليل يسأله أحدهم: "رقم تحويلة قسم المبيعات كام؟". في المرة الأولى يقوم، يبحث في الدليل، يأخذ دقيقة كاملة، ثم يعود بالرقم. لو سأله 50 شخصًا نفس السؤال، سيبحث 50 مرة ويهدر 50 دقيقة على إجابة واحدة.

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

تعريف Memoization بدقة

Memoization تقنية تحسين تُخزّن نتيجة استدعاء دالة، وتُرجع النتيجة المخزّنة فورًا عندما تتكرر نفس المدخلات. المصطلح صاغه الباحث Donald Michie سنة 1968 في ورقته عن دوال المذكرة وتعلّم الآلة. الكلمة مشتقة من "memo" بمعنى مذكرة، وليست خطأ إملائيًا لكلمة memorization.

لها شرط أساسي واحد: الدالة يجب أن تكون دالة نقية (Pure Function). الدالة النقية تعطي نفس المخرج لنفس المدخل دائمًا، وليس لها أي تأثير جانبي. مثال بسيط: دالة تجمع رقمين دالة نقية، فـ add(2, 3) ترجع 5 في كل مرة. لكن دالة ترجع الوقت الحالي ليست نقية، لأن مخرجها يتغيّر في كل استدعاء. الافتراض الذي يقوم عليه هذا الشرح: الدالة التي تخزّنها نقية، ومدخلاتها تتكرر فعلًا.

الكود: من 2.1 ثانية إلى جزء من المللي ثانية

لنأخذ متتالية فيبوناتشي. الطريقة المباشرة تبدو نظيفة لكنها فخ:

# الطريقة العادية: تعيد نفس الحساب ملايين المرات
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# fib(35) = 9227465
# القياس الفعلي: ~2.1 ثانية، 29,860,703 استدعاء

الآن نفس الدالة مع كرّاسة (قاموس) تحفظ كل نتيجة محسوبة:

# مع 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 استدعاء فقط

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

from functools import lru_cache

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

print(fib(35))   # 9227465 — نفس النتيجة، بسطر @lru_cache واحد

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

عندما تستدعي 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) بالطريقتين.