الگوریتم‌های جایگزینی کش
الگوریتم‌های جایگزینی کش: LRU، LFU و FIFO — پیاده‌سازی کامل LRU با OrderedDict و ساختار دوگانه
مسئله: کش پر شد!
کش ظرفیت محدود دارد؛ وقتی پر شد و درخواست جدید آمد، چه چیزی را بیاندازیم؟ — الگوریتم جایگزینی (Eviction) تصمیم می‌گیرد.
سه الگوریتم اصلی
| الگوریتم | ایده | مناسب | عیب |
|---|---|---|---|
| FIFO | اولین وارد، اولین خارج | ساده | به تازگی اهمیت نمی‌دهد |
| LRU | کم‌ترین استفاده اخیر خارج | اکثر موارد ✓✓ | داده قدیمی پرکاربرد ممکن است برود |
| LFU | کم‌ترین فراوانی کل خارج | الگوهای پایدار | داده «روزهای اوج» گیر می‌کند |
LRU — پادشاه عملی
فرض: «چیزی که اخیراً استفاده شده، به‌احتمال زیاد دوباره استفاده می‌شود» (محلی بودن زمانی). پس قدیمی‌ترین استفاده‌نشده را حذف کن.
مثال (ظرفیت ۳):
دسترسی: A B C D A
A B C در کش
D می‌آید → پر! → LRU = B (قدیمی‌ترین استفاده) → حذف B
A می‌آید → hit! (و A تازه می‌شود)پیاده‌سازی O(1)
ترفند: هش‌مپ + لیست دوپیوندی:
- هش‌مپ: کلید → گره (دسترسی O(1))
- لیست دوپیوندی: ترتیب استفاده (MRU جلو، LRU عقب)
- هر دسترسی: گره را به جلو ببر — O(1)
- حذف: از عقب — O(1)
در پایتون: OrderedDict همین ساختار را آماده دارد!
LRU در دنیای واقعی
- Redis: الگوریتم تقریبی LRU (نمونه‌گیری برای کارایی)
- CPU Cache، صفحه‌بندی OS، CDN: همه LRU-گونه
- سؤال مصاحبه کدنویسی: پیاده‌سازی LRU Cache — کلاسیک!
نکته: در مصاحبه System Design وقتی کش می‌گویید، بگویید «با سیاست LRU و TTL» — همین دو کلمه نشان می‌دهد جزئیات را می‌دانید!
جمع‌بندی
- کش پر → جایگزینی: FIFO/LRU/LFU
- LRU: محلی بودن زمانی — استاندارد عملی
- پیاده‌سازی O(1): هش + لیست دوپیوندی
- OrderedDict پایتون = LRU آماده
این مبحث بخشی از دوره آموزش کامل طراحی سیستم (System Design) است.