LRU مخفف Least Recently Used است. این الگوریتم یک استراتژی مدیریت حافظه است که وقتی حافظه کش پر میشود، کمترین آیتمهای استفادهشده اخیراً را حذف میکند تا فضا برای آیتمهای جدید باز شود.
فرض کنید یک دفترچه تلفن دارید و فقط میتوانید ۳ شماره آخر را به خاطر بسپارید. وقتی شماره جدیدی یاد میگیرید، قدیمیترین شماره فراموش میشود. این دقیقاً همان رفتار LRU Cache است.
lru_cache در پایتون
پایتون یک پیادهسازی آماده از LRU Cache را از طریق دکوراتور @lru_cache در ماژول functools ارائه میدهد.
from functools import lru_cache
نحوه استفاده پایه
سادهترین شکل استفاده، بدون هیچ پارامتری:
from functools import lru_cache
import time
@lru_cache
def slow_function(n):
time.sleep(2)
return n * n
print(slow_function(4)) # ۲ ثانیه صبر میکند و 16 برمیگرداند
print(slow_function(4)) # فوری 16 برمیگرداند (از کش)
print(slow_function(5)) # ۲ ثانیه صبر میکند و 25 برمیگرداند
پارامتر max_size
این پارامتر تعداد حداکثر آیتمهایی که در کش نگهداری میشوند را مشخص میکند:
@lru_cache(maxsize=128)
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# استفاده از کش
for i in range(100):
fibonacci(i)
در این مثال بدون کش، محاسبه fibonacci(100) بسیار زمانبر بود. اما با کش، هر مقدار فقط یکبار محاسبه میشود و دفعات بعد از کش خوانده میشود.
نکات مهم درباره maxsize
maxsize=Noneیعنی کش هیچ محدودیتی ندارد و همه نتایج ذخیره میشوند.maxsize=128یعنی حداکثر ۱۲۸ آیتم نگهداری شود (پیشفرض).maxsize=0یعنی کش غیرفعال باشد و هیچ نتیجهای ذخیره نشود.- استفاده از توان ۲ برای maxsize معمولاً عملکرد بهتری دارد: ۶۴، ۱۲۸، ۲۵۶ و غیره.
پارامتر typed
وقتی typed=True باشد، آرگومانهایی با نوعهای مختلف بهصورت جداگانه کش میشوند:
@lru_cache(maxsize=128, typed=True)
def operation(a, b):
print(f"Computing: {a}, {b}")
return a + b
operation(3, 5) # محاسبه میشود
operation(3.0, 5.0) # محاسبه میشود چون نوع float است
اگر typed=False باشد (پیشفرض)، هر دو فراخوانی بالا نتیجه کش را برمیگردانند.
متدهای cache_info و cache_clear
این دو متد برای نظارت و مدیریت کش بسیار مفید هستند:
from functools import lru_cache
@lru_cache(maxsize=3)
def get_data(key):
return f"Data for {key}"
print(get_data.cache_info())
# CacheInfo(hits=0, misses=0, maxsize=3, currsize=0)
get_data("a")
get_data("b")
get_data("c")
print(get_data.cache_info())
# CacheInfo(hits=0, misses=3, maxsize=3, currsize=3)
get_data("a") # از کش
get_data("b") # از کش
print(get_data.cache_info())
# CacheInfo(hits=2, misses=3, maxsize=3, currsize=3)
توضیح خروجی cache_info
- hits: تعداد دفعاتی که نتیجه از کش خوانده شده
- misses: تعداد دفعاتی که نتیجه باید محاسبه شود
- maxsize: حداکثر ظرفیت کش
- currsize: تعداد آیتمهای فعلی در کش
استفاده از cache_clear
@lru_cache(maxsize=3)
def square(n):
return n * n
square(5)
square(10)
print(square.cache_info())
# CacheInfo(hits=0, misses=2, maxsize=3, currsize=2)
square.cache_clear() # پاک کردن کش
print(square.cache_info())
# CacheInfo(hits=0, misses=0, maxsize=3, currsize=0)
مقایسه عملکرد با و بدون کش
import time
from functools import lru_cache
# بدون کش
def fibonacci_no_cache(n):
if n < 2:
return n
return fibonacci_no_cache(n - 1) + fibonacci_no_cache(n - 2)
# با کش
@lru_cache(maxsize=None)
def fibonacci_with_cache(n):
if n < 2:
return n
return fibonacci_with_cache(n - 1) + fibonacci_with_cache(n - 2)
# اندازهگیری زمان
start = time.time()
fibonacci_no_cache(30)
print(f"بدون کش: {time.time() - start:.4f} ثانیه")
start = time.time()
fibonacci_with_cache(30)
print(f"با کش: {time.time() - start:.4f} ثانیه")
نتیجه典型: بدون کش حدود ۰.۳ ثانیه و با کش کمتر از ۰.۰۰۰۱ ثانیه طول میکشد.
محدودیتهای lru_cache
- فقط روی توابعی کار میکند که آرگومانهایشان قابل هش شدن (hashable) باشند. یعنی آرگومانها باید immutable باشند.
- برای توابعی با آرگومانهای تغییرپذیر مانند لیست یا دیکشنری نمیتوان استفاده کرد.
- اگر تابع عوارض جانبی (side effects) داشته باشد، کش کردن میتواند مشکلساز شود.
# این کار نمیکند
@lru_cache
def bad_function(data):
return data * 2
bad_function([1, 2, 3]) # TypeError: unhashable type: 'list'
# این کار میکند
@lru_cache
def good_function(data):
return tuple(data) * 2
good_function([1, 2, 3]) # OK
استفاده از متدهای کلاس
@lru_cache روی متدها نیز قابل استفاده است:
from functools import lru_cache
class TextProcessor:
def __init__(self):
self._cache = {}
@lru_cache(maxsize=256)
def word_count(self, text: str) -> int:
return len(text.split())
@lru_cache(maxsize=64)
def char_count(self, text: str) -> int:
return len(text)
t = TextProcessor()
print(t.word_count("سلام دنیا"))
print(t.word_count.cache_info())
پاکسازی خودکار با expire
@lru_cache استاندارد پایتون expire ندارد، اما میتوانید این قابلیت را خودتان پیادهسازی کنید:
from functools import lru_cache
import time
from typing import Any, Callable
def cached_with_expiry(maxsize: int = 128, ttl: int = 60):
def decorator(func: Callable) -> Callable:
cache = {}
timestamps = {}
@lru_cache(maxsize=maxsize)
def cached_func(*args, **kwargs):
return func(*args, **kwargs)
def wrapper(*args, **kwargs):
key = (args, tuple(sorted(kwargs.items())))
now = time.time()
if key in timestamps and (now - timestamps[key]) > ttl:
cached_func.cache_clear()
cache.pop(key, None)
timestamps.pop(key, None)
result = cached_func(*args, **kwargs)
cache[key] = result
timestamps[key] = now
return result
wrapper.cache_info = cached_func.cache_info
wrapper.cache_clear = cached_func.cache_clear
return wrapper
return decorator
@cached_with_expiry(maxsize=10, ttl=30)
def get_data(n):
return n ** 2
الگوریتم LRU در داخل کش
برای درک بهتر، ببینید وقتی کش پر میشود چه اتفاقی میافتد:
from functools import lru_cache
@lru_cache(maxsize=3)
def demo(key):
return f"Value: {key}"
demo(1) # miss
demo(2) # miss
demo(3) # miss
print(demo.cache_info())
# currsize=3
demo(4) # miss - چون کش پر شده، کمترین استفاده اخیر (key=1) حذف میشود
print(demo.cache_info())
# currsize=3 - هنوز 3 آیتم هست
کاربردهای رایج
- بهینهسازی توابع بازگشتی مانند فیبوناچی
- کش کردن نتایج APIهای خارجی
- کش کردن نتایج پرسوجوهای دیتابیس
- کش کردن نتایج محاسبات سنگین ریاضی
- بهینهسازی جستجوهای تکراری در دادههای بزرگ
خلاصه پارامترها
| پارامتر | نوع | پیشفرض | توضیح |
|---|---|---|---|
| maxsize | int یا None | 128 | حداکثر تعداد آیتمهای کش. None یعنی بدون محدودیت |
| typed | bool | False | اگر True باشد، نوع آرگومانها هم در کلید کش حساب میشود |
نکات تکمیلی
- برای پروژههای با نیازهای کش پیشرفته، کتابخانههایی مثل cachetools و functools_lru_cache وجود دارند.
- دکوراتور
@cache(بدون lru) در پایتون 3.9 اضافه شده که معادل@lru_cache(maxsize=None)است. - اگر تابع شما فقط آرگومانهای hashable میگیرد و محاسبات تکراری زیادی دارد، lru_cache میتواند عملکرد را تا هزاران برابر بهبود دهد.
- کش در طول عمر برنامه باقی میماند مگر اینکه صراحتاً پاک شود یا برنامه بسته شود.