المستوى: مبتدئ
لو الـ 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);
});