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")الفرق إن بتتحسب مرة واحدة، وبعدها بترجع من الكاش في خطوة ثابتة.