This an implementation of true LRU using C++ structs and pointers.
- The Problem with Standard LRU:
- Traditional LRU algorithms often make assumptions about "recency" that aren't always accurate.1 Specifically, they can misinterpret the significance of newly added items.
- A standard LRU will move a newly inserted item to the "most recently used" position, even if that item has never actually been accessed before. This can lead to the premature eviction of genuinely frequently used items.
- True LRU's Focus on "True Recency":
- "True LRU" aims to correct these inaccuracies by more precisely tracking the actual usage patterns of cached items.
- It distinguishes between:
- "Used and used" recency (how recently items that have been accessed were used).
- "Used and unused" recency (how recently used items relate to those that have been placed in the cache, but never yet used).
- "Unused and unused" recency (how to manage the order of items that have never been used).
- By considering these distinctions, true LRU strives to achieve a more accurate representation of which items are truly the least recently used.
