Memoization للمتوسط: ليه fibonacci(40) بياخد 30 ثانية وبسطر واحد بيبقى أقل من ميلي ثانية

مستوى المقال: متوسط. الكلام ده مفيد لو انت عارف الـ recursion أساسًا وعايز تفهم ليه دالة بسيطة بتفجّر وقت التنفيذ، وإزاي سطر واحد بيصلّحها.

لو دالة fibonacci العودية بتاعتك بتتجمّد على رقم 40، المشكلة مش في السيرفر ولا في لغتك. المشكلة إنها بتحسب نفس القيمة ملايين المرات. Memoization بيخلّيها تحسب كل قيمة مرة واحدة بس، وبيوفّر أكتر من 99.9% من الشغل.

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

دالة فيبوناتشي العودية الكلاسيكية بتنادي نفسها مرتين في كل خطوة. ده بيخلّي عدد الاستدعاءات يكبر أُسّيًا. على رقم 40 بتعمل حوالي 331 مليون استدعاء. النتيجة: عشرات الثواني تنفيذ على حاجة المفروض تطلع فورًا.

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

تخيّل طالب كسلان بيحل واجب فيه نفس المسألة الصغيرة متكررة 50 مرة. الطالب الغبي بيعيد حلّها من الأول في كل مرة. الطالب الذكي بيحلها مرة واحدة، بيكتب الناتج في كشكول جنبه، وأول ما يقابلها تاني بيبص على الكشكول بدل ما يحسب.

الكشكول ده هو الـ Memoization. الـ cache اللي بتخزّن فيه نتائج اتحسبت قبل كده، علشان متعيدش الشغل.

نفس الكلام علميًا

Memoization هو أسلوب تحسين بتخزّن فيه نتيجة استدعاء دالة بناءً على مدخلاتها، وترجّع النتيجة المخزّنة لو نفس المدخلات اتطلبت تاني. شرطه إن الدالة pure: نفس المدخل بيدّي نفس المخرج دائمًا وبدون side effects.

هو يشتغل بكفاءة لما تكون المسألة فيها overlapping subproblems: مسائل فرعية بتتكرر. fibonacci نموذج مثالي، لأن fib(38) بتتحسب آلاف المرات داخل fib(40). الصورة الجاية بتوضّح شجرة الاستدعاء اللي بتتشعّب وتعيد نفس الفروع.

الحل في Python بسطر واحد

Python فيه decorator جاهز اسمه functools.cache (من إصدار 3.9). بتحطه فوق الدالة وخلاص:

import functools
import time

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

# النسخة المحسّنة: سطر واحد بس فوق الدالة
@functools.cache
def fib_fast(n):
    if n < 2:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

t = time.perf_counter()
fib_slow(40)
print("slow:", round(time.perf_counter() - t, 3), "s")

t = time.perf_counter()
fib_fast(40)
print("fast:", round((time.perf_counter() - t) * 1000, 3), "ms")

الفرق إن fib_fast(38) بتتحسب مرة واحدة، وبعدها بترجع من الكاش في خطوة ثابتة.

نفس الفكرة في JavaScript

مفيش decorator مدمج، فبنبني الكاش بإيدينا بـ Map:

function memoize(fn) {
  const cache = new Map();
  return function (n) {
    if (cache.has(n)) return cache.get(n);
    const result = fn(n);
    cache.set(n, result);
    return result;
  };
}

const fib = memoize(function f(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
});

console.log(fib(40)); // 102334155 — يطلع فورًا

الأرقام اللي بتحصل فعلاً

دي قياسات تقريبية على CPython 3.12 على جهاز عادي. الأرقام ممكن تختلف من جهاز للتاني، بس النسبة هي المهمة:

• عدد الاستدعاءات: النسخة البطيئة لـ fib(40) ≈ 331,160,281 استدعاء. النسخة المحسّنة = 41 استدعاء فقط.
• الزمن: البطيئة حوالي 25 إلى 35 ثانية. المحسّنة أقل من 1 ميلي ثانية (المرة الأولى).
• رتبة التعقيد: من O(φ^n) ≈ O(1.618^n) أُسّي، لـ O(n) خطّي.

يعني التحسّن مش 10% ولا ضعفين. هو فرق رتبة كاملة، بيتحوّل من عملي إلى مستحيل لما n يكبر.

الـ trade-offs — بتكسب إيه وبتخسر إيه

Memoization مش ببلاش. اللي بيحصل بالظبط:

• بتكسب: وقت تنفيذ أقل بمراحل في المسائل المتكررة.
• بتخسر ذاكرة: الكاش بيكبر مع كل مدخل جديد. fib لـ n كبيرة بيخزّن n قيمة في الرام. الافتراض هنا إن المدخلات محدودة ومش بتكبر بلا نهاية.
• خطر الكاش القديم: لو الدالة مش pure (بتعتمد على وقت أو ملف أو DB)، الكاش هيرجّعلك نتيجة قديمة غلط. متعملش memoize لدالة نتيجتها بتتغير.
• المفاتيح لازم hashable: في Python، functools.cache محتاج المدخلات تبقى hashable (مش list أو dict).

متى متستخدمش Memoization

متستخدموش في الحالات دي:

• الدالة بتُستدعى مرة واحدة بمدخل مختلف كل مرة — مفيش تكرار تستفيد منه، والكاش هيبقى عبء ذاكرة بس.
• الدالة فيها side effects (بتكتب في DB، بتبعت request) — التخزين هيلغي السلوك المطلوب.
• عندك ضغط على الذاكرة ومساحة الكاش هتكبر بلا حد — هنا فكّر في functools.lru_cache(maxsize=N) بدل cache علشان تحدّ الحجم.
• المسألة مالهاش overlapping subproblems أصلًا — زي مجرد المرور على array مرة واحدة.

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

افتح أبطأ دالة عودية في كودك دلوقتي، وحط فوقها @functools.cache (أو لفّها بـ memoize في JS)، وقِس الزمن قبل وبعد بـ time.perf_counter. لو الفرق كبير، يبقى عندك overlapping subproblems وكنت بتدفع تكرار على الفاضي. لو الزمن ما اتغيرش، يبقى مشكلتك مكان تاني — ابعتلي القياسات.

المصادر

• توثيق Python الرسمي — functools.cache و lru_cache: https://docs.python.org/3/library/functools.html
• MDN Web Docs — Map وأساسيات JavaScript: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
• كتاب Introduction to Algorithms (CLRS) — فصل Dynamic Programming و overlapping subproblems.
• توثيق Python عن hashable objects: https://docs.python.org/3/glossary.html#term-hashable