Memoization في JavaScript: ليه fibonacci(45) بتاخد 8 ثواني

// fib_memo.js
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 self(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
});

const t0 = performance.now();
const result = fib(45);
const t1 = performance.now();

console.log(`fib(45) = ${result}`);
console.log(`Time: ${(t1 - t0).toFixed(3)} ms`);
// fib(45) = 1134903170
// Time: 0.912 ms

الفرق 9230x أسرع على نفس الجهاز (MacBook M2، Node 22.13). السبب إن أي قيمة fib(k) بتتحسب مرة واحدة بس بدل ما تتحسب ملايين المرات في شجرة الاستدعاءات.

ليه Map وليه مش Object؟

ناس كتير بتستخدم const cache = {}. Map أفضل لثلاث أسباب عملية:

• أداء lookup ثابت: Map.get أسرع من obj[key] لما الـ keys بتزيد عن آلاف، حسب benchmarks V8.
• Keys من أي نوع: Map بتقبل objects و numbers كـ keys زي ما هي. الـ Object بيحوّل أي مفتاح لـ string.
• مفيش prototype pollution: مفيش حاجة اسمها cache.__proto__ أو cache.toString بتلخبطك.

سيناريو واقعي: حساب الضريبة على 50 ألف منتج

افترض إن عندك e-commerce فيه 50 ألف منتج، وكل صفحة منتج بتعرض السعر بالضريبة. لو دالة calculateTaxedPrice(productId) بتعمل query على DB في كل مرة، الـ p95 latency على صفحة فيها 24 منتج بيوصل 380ms. مع Memoization على مستوى الـ request:

الافتراض هنا إن أسعار المنتجات ثابتة خلال الـ request. لو الأسعار بتتغيّر كل ثانية، Memoization مش أداتك.

الـ trade-offs الحقيقية

كل تحسين له ثمنه. Memoization بتاخد ذاكرة. مع fib(10000) الـ Map هيخزن 10 آلاف زوج (number, BigInt) — حوالي 480KB في الـ heap. مع query function بترجع object كبير، الذاكرة ممكن تطلع بسرعة.

الـ trade-off هنا: بتكسب سرعة 100x إلى 10000x، بتخسر ذاكرة بحجم (عدد المدخلات الفريدة × حجم النتيجة).

الحل لمنع تضخم الذاكرة: استخدم LRU cache بحد أقصى. مكتبة lru-cache على npm بتديك نفس الـ API مع TTL وحد للحجم:

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

الموضوع مش رصاصة فضية. لا تستخدمه في الحالات دي:

• الدالة مش pure: لو فيها Date.now()، Math.random()، أو بتقرا state من الخارج، النتيجة المخزّنة هتكون غلط.
• المدخلات الفريدة كتيرة جدًا: لو كل request بيجي بـ UUID مختلف، الـ cache hit rate صفر والذاكرة بتكبر بدون فايدة.
• حجم النتيجة كبير وحساس للذاكرة: تخزين 10 آلاف query result بـ 50KB يساوي 500MB. مفيش فايدة.
• النتيجة بتتغيّر مع الوقت: زي سعر صرف الدولار. الـ cache هتديك بيانات قديمة. لو لازم تستخدم cache، حط TTL قصير.

قاعدة قرار سريعة

قبل ما تطبق Memoization على دالة، اسأل نفسك التلات أسئلة دي بالتفاصيل:

1. الدالة pure؟ (نفس input → نفس output دايمًا)
2. الدالة بتتنده على نفس الـ inputs أكتر من 5 مرات في عمر العملية؟
3. تكلفة الحساب أعلى من تكلفة lookup في Map؟ (يعني الدالة بتاخد ميكروثانية على الأقل)

لو الـ 3 إجابات "نعم"، طبّقها. لو واحد منهم "لا"، الدالة مش محتاجة Memoization.

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

افتح أبطأ دالة في الكود عندك واتفرّج على شجرة استدعاءاتها بـ --prof في Node:

دوّر على الدوال اللي بتتنده آلاف المرات بنفس الـ arguments. غلّفها بـ memoize. قِس الفرق بـ performance.now() قبل وبعد. لو الفرق أقل من 10%، شيلها — الذاكرة الزيادة مش بتستاهل.

المصادر

• MDN Web Docs — Map
• Wikipedia — Memoization
• Node.js performance hooks API
• npm — lru-cache package
• V8 Engine — Performance blog