المستوى: مبتدئ

لو الـ fibonacci(40) بياخد عندك ثانية ونصف على لابتوب حديث، المشكلة مش الـ CPU. المشكلة إن نفس الرقم بيتحسب أكتر من 165 مليون مرة. سطر واحد اسمه Memoization بينزّل الزمن لـ 0.3 مللي ثانية. هنا الفكرة، الكود، الأرقام، وامتى ما تنفعش.

Memoization: تذكّر النتيجة بدل ما تحسبها كل مرة

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

كتير من الدوال في الكود بترجع نفس النتيجة لنفس المدخلات. لو الدالة دي بتاخد وقت في الحساب، وبتتنادى مرّتين بنفس الـ argument، يبقى انت بتدفع التكلفة مرتين بدون داعي.

fibonacci الكلاسيكي أبسط مثال على الفكرة. fib(40) بيعمل recursive call على fib(39) و fib(38). لكن fib(39) جوّاه بيحسب fib(38) تاني. والشجرة بتتفرّع لحد ما يبقى fib(38) اتحسب أكتر من 102 مليون مرة في عملية واحدة.

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

تخيّل صاحب مكتبة بتتسأله كل ساعة: "كتاب الخوارزميات لـ Cormen موجود فين؟". لو كل مرة بيقوم يلف على الأرفف، التليفون مش هيقفل. أول ما يلاقيه يكتب على ورقة: "الرف رقم 12 - الصف الرابع". المرة الجاية بيرد من الورقة في ثانية بدل ما يلف 5 دقايق.

الورقة دي هي الـ cache. وفعل تسجيل الإجابة بعد أول لفّة هو Memoization. الفرق إن المكتبي بيبدأ بالعشوائية، والكود بيبدأ بـ cache فاضي وبيتعلّم تدريجي مع كل استدعاء جديد.

التعريف العلمي بالظبط

Memoization تقنية optimization من فئة dynamic programming، بتعتمد على تخزين نتائج الـ function calls في lookup table، ثم استرجاعها لما نفس المدخلات تتكرر. الشرط الأساسي إن الدالة لازم تكون pure function: نفس المدخلات → نفس المخرجات، وبدون أي side effect (مش بتلمس DB، مش بتعدّل متغيّر برّاني، مش بتعتمد على Math.random أو Date.now أو شبكة).

المصطلح ابتدعه Donald Michie سنة 1968 في ورقة عنوانها "Memo Functions and Machine Learning" في مجلة Nature. الفكرة قديمة، لكنها بقت ضرورة في تطبيقات الويب لأن JavaScript بيشتغل single-thread، وأي computation ثقيل في الـ main thread بيمنع الـ UI من الاستجابة.

الكود التنفيذي على Node.js 22

function memoize(fn) {
  const cache = new Map();
  return function (...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

// الدالة العادية بدون كاش
function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

// نفس الدالة معمولها Memoization
const fibFast = memoize(function self(n) {
  if (n < 2) return n;
  return fibFast(n - 1) + fibFast(n - 2);
});

الـ memoize دالة بتاخد دالة وبترجع دالة. الـ cache جوّاها Map بيعيش في closure، يعني بيفضل في الذاكرة طول ما الـ fibFast موجودة. الـ key هو نسخة JSON من الـ args، عشان يشتغل مع أكتر من argument.

قياس الفرق بأرقام حقيقية

console.time('plain');
fib(40);
console.timeEnd('plain');     // plain: 1418.32ms

console.time('memoized');
fibFast(40);
console.timeEnd('memoized');  // memoized: 0.31ms

4500x فرق. مش سحر. السبب إن النسخة الأولى بتحسب نفس الفرع من الشجرة 165 مليون مرة. النسخة المحسّنة بتحسبه مرة واحدة، وبترجعه من الكاش 165 مليون مرة. كلفة الـ Map.get داخل V8 حوالي 35 نانو ثانية، والـ JIT بيحسّنها أكتر مع التكرار.

الـ trade-offs بصراحة

بتكسب: سرعة، أحيانًا 10x، أحيانًا 4500x زي ما هنا.

بتخسر:

• ذاكرة. الكاش بيكبر مع كل مدخل جديد. على fibFast(40) هما 41 entry بس (~3KB). لكن لو memoize دالة بتاخد URL أو user input، الكاش ممكن يوصل 200MB في ساعة.
• تعقيد. الكود بقى فيه طبقة زيادة. debugging أصعب لو نسيت إن الدالة محفوظة وبتتساءل ليه القيمة القديمة بترجع.
• تكلفة الـ key. JSON.stringify بياخد وقت لو الـ args object كبير. على object بـ 1000 مفتاح، الـ stringify لوحده بياخد 0.4ms — overhead أكبر من القيمة المحفوظة.

الافتراض إنك تعرف حدود الـ keyspace. لو الـ keyspace مفتوح (URLs أو user input)، استخدم LRU cache (مكتبة lru-cache على npm) بدل Map عادي عشان تحط حد للذاكرة.

أمثلة واقعية بتستحق Memoization

• Selectors في Redux: مكتبة reselect كاملة مبنيّة على Memoization عشان derived state ما يتحسبش في كل render.
• Regex compilation: بناء RegExp object بياخد ميكروثواني، لو بتنادي نفس النمط 10000 مرة لفّه في memoize.
• Date formatting: Intl.DateTimeFormat غالي الإنشاء، فا memoize بيتعمل حسب الـ locale.
• Pure utility functions: parsing CSV row، حساب hash لـ string، تنسيق العملات.

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

• الدالة بترجع قيم مختلفة لنفس المدخلات: Math.random، Date.now، fetch لـ API بتتغيّر.
• الدالة عندها side effect: بتكتب في DB، بتعدّل DOM، بترسل event.
• الـ keyspace غير محدود والذاكرة عندك محدودة (mobile، edge worker بـ 128MB).
• Computation أصلاً أقل من 0.1ms — overhead الـ JSON.stringify هيخليها أبطأ مش أسرع.
• الدالة بتتنادى مرة واحدة في عمر الـ process — لا فايدة من الكاش.

المصادر

• Donald Michie (1968). Memo Functions and Machine Learning. Nature 218, 19–22.
• MDN — Closures: developer.mozilla.org/Web/JavaScript/Closures
• V8 — Fast Properties & Map performance: v8.dev/blog/fast-properties
• Reselect (Memoization على Selectors): github.com/reduxjs/reselect
• Node.js Performance Hooks: nodejs.org/api/perf_hooks
• lru-cache على npm: npmjs.com/package/lru-cache

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

افتح أبطأ دالة في الكود بتاعك دلوقتي. شوف لو مدخلاتها deterministic ومالهاش side effect. لفّها في memoize() اللي فوق، وقيس بـ console.time قبل وبعد. لو ما اتغيّرش الزمن، الدالة فعلًا بسيطة. لو اتسارعت 10x أو أكتر، يبقى لقيت candidate حقيقي للـ optimization. لو خرجت الذاكرة عن السيطرة، حوّل من Map لـ LRU بحجم محدد.