Memoization في Python: @lru_cache بينزّل الزمن من ثواني لميكروثانية

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

النتيجة على 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