المستوى: متوسط — المقال موجّه لمن يكتب Python بانتظام ويفهم الدوال والـ Recursion بشكل أساسي. القراءة حوالي 7 دقائق.

لو الدالة عندك بتحسب نفس الناتج آلاف المرات في الدقيقة، أنت بتدفع تكلفة CPU بدون مبرر. Memoization بتخلي الدالة تفتكر إجاباتها القديمة وترجّعها في O(1) بدل ما تعيد الحساب من الصفر.

Memoization: لما الدالة بتفتكر بدل ما تعيد الحساب

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

دوال كتير بتتنده بنفس المدخلات في الثانية الواحدة. كل استدعاء بيعيد نفس الحساب. لو الحساب رخيص، مفيش مشكلة. لو الحساب فيه recursion عميق أو lookup من قاعدة بيانات، الفاتورة بتكبر بسرعة.

ابدأ بمثال بسيط — قبل ما ندخل في الكود

تخيل إنك بتطلب من زميلك في المكتب يحسبلك ضرب الأرقام من 1 لـ 10 كل صباح. طريقة غبية: يعيد الحساب من الأول كل مرة. طريقة ذكية: يحسبها مرة واحدة، يكتبها في ورقة على المكتب، وكل صباح يبصلها ويقولك. الورقة دي هي الـ cache، والفعل ده بالظبط هو Memoization.

التعريف العلمي بدقة

Memoization تقنية تحسين بتخزّن نتائج الدوال الـ pure في جدول lookup مفهرس بمدخلات الدالة. لو نفس المدخلات اتطلبت مرة تانية، النتيجة بترجع من الجدول في O(1) بدل إعادة الحساب. الشرط الأساسي: الدالة لازم تكون pure — يعني نفس المدخلات بترجع نفس المخرجات بدون side effects (مفيش كتابة في ملف، مفيش تعديل لمتغير global، مفيش request شبكي).

المثال الكلاسيكي: فيبوناتشي بدون memoization

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# fib(35) ≈ 3.4 ثانية على MacBook Pro M2

المشكلة: fib(35) بينده fib(34) و fib(33). و fib(34) بينده fib(33) تاني. النتيجة: حوالي 9 ملايين استدعاء، أغلبهم تكرار لنفس الأرقام. التعقيد O(2^n).

الحل بسطر واحد — @lru_cache

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# fib(35) ≈ 7 ميكروثانية

الفرق: من 3,400 ميلي ثانية لـ 0.007 ميلي ثانية. ده ليس "أسرع شوية"، ده تسريع تقريبًا 485,000×. السبب: lru_cache بيخزّن نتيجة كل قيمة لـ n أول مرة بتتحسب، فالاستدعاءات اللي بعدها بترجع من الـ cache مباشرة. التعقيد بيرجع O(n) بدل O(2^n).

قياس فعلي بـ time.perf_counter

import time
from functools import lru_cache

def fib_slow(n):
    if n < 2: return n
    return fib_slow(n - 1) + fib_slow(n - 2)

@lru_cache(maxsize=None)
def fib_fast(n):
    if n < 2: return n
    return fib_fast(n - 1) + fib_fast(n - 2)

t0 = time.perf_counter()
fib_slow(35)
print(f"slow: {(time.perf_counter() - t0) * 1000:.1f} ms")

t0 = time.perf_counter()
fib_fast(35)
print(f"fast: {(time.perf_counter() - t0) * 1e6:.1f} us")

النتيجة على Python 3.12 / MacBook Pro M2:

• slow: 3,420 ms
• fast: 6.8 µs

إعدادات lru_cache المهمة

• maxsize=128 (الافتراضي): الـ cache بيحتفظ بآخر 128 إدخال، الأقدم بيتطرد لما الـ cache يمتلئ. مناسب لو المدخلات كتير ومش عايز تستهلك ذاكرة بلا حد.
• maxsize=None: لا حد للحجم. استخدمها لو عارف إن مجموعة المدخلات محدودة (50 منتج، 200 دولة).
• typed=True: fib(1) و fib(1.0) بيتعاملوا كمدخلين مختلفين بدل ما يشاركوا نفس الإدخال.
• fib.cache_info(): بيطبع hits و misses و currsize. أداة مهمة لقياس فعالية الـ cache.
• fib.cache_clear(): بيمسح الـ cache. مفيد في الاختبارات.

الـ trade-offs اللي لازم تعرفها

المكسب: زمن الاستجابة بينزل بشكل دراماتيكي على الدوال المتكررة. التحسن من 5× لـ 100,000× حسب طبيعة المشكلة.

التكلفة: الذاكرة. الـ cache بيكبر مع كل مدخلات جديدة. fib(1000) → 1000 entry محفوظة في الـ heap. لو الدالة عندك بتتطلب بمليون مدخلات مختلفة في اليوم، الـ cache هيستهلك مئات الميجابايتات بسهولة.

الافتراض الخفي: نفس المدخلات بترجّع نفس النتيجة دائمًا. لو الدالة بتقرأ من قاعدة بيانات أو ملف بيتغير، الـ cache هيرجّعلك قيم قديمة وأنت مش حاسس.

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

• الدالة فيها side effects. بتكتب في ملف، بترسل request، بتعدّل state. الـ cache هيخفي السلوك ده ويسبب bugs.
• المدخلات أنواع غير قابلة للـ hashing. list, dict, set ما بيشتغلوش مع lru_cache. الحل: حوّلهم لـ tuple أو frozenset قبل ما تبعتهم.
• الدالة بترجع قيمة بتتغير مع الوقت. أي حاجة فيها timestamp أو random أو قراءة من DB حية.
• الدالة سريعة أصلاً. لو الدالة بتتنفّذ في 200ns، تكلفة الـ lookup في الـ cache ممكن تساوي أو تتجاوز المكسب.
• الـ cache hit rate منخفض. لو كل request بييجي بمدخلات جديدة، الـ cache بيتملي بدون فايدة. اقيس بـ cache_info() الأول.

مثال واقعي من إنتاج

دالة get_tax_rate(country, product_type) بتعمل lookup من PostgreSQL لكل request. على API بـ 5,000 request/دقيقة، نفس الـ 50 combination (10 دول × 5 أنواع منتجات) بيتكرروا طول اليوم.

• قبل lru_cache: 8 ms متوسط لكل استدعاء (round-trip لقاعدة البيانات).
• بعد lru_cache(maxsize=128): 0.3 ms متوسط (lookup من dict في الذاكرة).
• التحسن: 26×. والـ DB load نزل 96%.

الافتراض هنا: نسبة الـ tax rates ما بتتغيرش يوميًا. لو اتغيرت، Service بتعمل cache_clear() كل 6 ساعات بـ background task.

بدائل خارج functools

• @functools.cache (Python 3.9+): اختصار لـ lru_cache(maxsize=None). أبسط لو مش محتاج LRU eviction.
• cachetools: مكتبة خارجية فيها TTLCache (انتهاء صلاحية بالوقت)، LFUCache، وstrategies تانية. مفيدة لما lru_cache مش كافي.
• Redis كـ external cache: لما كذا instance لازم يشاركوا نفس الـ cache. التكلفة: round-trip للشبكة (~1ms)، فالمكسب لازم يكون أكبر منها.

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

افتح أحدث ملف Python في مشروعك. دور على دوال recursive أو دوال بتعمل lookups متكررة (مثل قراءة config، حساب hash، تحويل عملات). ضع @lru_cache(maxsize=128) فوق واحدة منهم. شغّل benchmark بسيط بـ time.perf_counter قبل وبعد، ثم اطبع fn.cache_info() لتشوف نسبة hits/misses. لو الفرق ≥ 5× والـ hit rate أكبر من 70%، سيبها. لو الفرق أقل من 2× أو الـ hit rate ضعيف، شيلها — معناها الدالة مش متكررة بالقدر الكافي.

المصادر

• Python Standard Library — functools.lru_cache docs: docs.python.org/3/library/functools.html
• Python Source — Lib/functools.py implementation of LRU eviction (CPython repo on GitHub).
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), فصل Dynamic Programming، تعريف Memoization كأسلوب top-down.
• Donald Michie (1968) — Memo Functions and Machine Learning، Nature، الورقة اللي صكّت مصطلح "memo function".
• cachetools library docs: cachetools.readthedocs.io