What is an LRU cache?

LRU (Least Recently Used) cache is a data structure used for temporarily storing a limited set of data to improve performance. When a new element is added and the cache is full, it evicts the least recently used element.

Working principle:

• Each time an element is accessed (read or write), it is marked as "recently used" and moved to the front of the list or structure representing the usage order.
• When the cache overflows, the element at the "tail" — the one accessed the longest ago — is removed.

Implementation often uses a combination of a dictionary (for quick access by key) and a doubly linked list (to maintain the usage order).

Example in Python (functools.lru_cache):

# Import decorator
from functools import lru_cache

# Decorator limiting cache to the last 128 calls
@lru_cache(maxsize=128)
def fibonacci(n):
  # Recursive Fibonacci function with caching
  if n < 2:
    return n
  return fibonacci(n-1) + fibonacci(n-2)

# Function calls
fibonacci(10)

Advantages:

• Accelerates access to frequently used data.
• Efficient use of limited cache memory.

Disadvantages:

• May be inefficient for data with uniform or random access.
• Overhead for maintaining usage order.