LRU cache
A fixed-size cache that, when full, throws out the entry that has gone unused the longest.
In more detail
The classic implementation combines a dict, for O(1) lookup, with a doubly linked list kept in order of use, for O(1) moves and evictions. Every hit moves an entry to the front; every insert past capacity drops the entry at the back. Python's functools.lru_cache applies this to function results.
Related terms
- doubly linked list — A linked list in which each node points to both the next and the previous node, so it can be walked either way and any held node removed in O(1).
- functools.lru_cache — A Python decorator from the functools module that memoises a function, remembering results for arguments it has seen.
- memoisation — Caching a function's results by its arguments so that repeated calls return the stored answer instead of recomputing it.
Taught in
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers