# Caches: LRU with OrderedDict and functools — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/a-lru

> Build and use least-recently-used caches.

## Remembering what is likely to be needed again

A **cache** stores results so that repeated requests are fast. Because memory is limited, a cache needs an **eviction policy**; **least recently used (LRU)** evicts the entry that has gone unused the longest, a good default for many workloads. A classic LRU cache achieves **O(1)** `get` and `put` by combining a **hash map** (key to node) with a **doubly linked list** ordered by recency: on access, move the node to the front; on overflow, remove from the back. In Python, **`collections.OrderedDict`** provides both pieces: `move_to_end(key)` marks an entry as recently used and `popitem(last=False)` evicts the oldest. For caching **function results**, the standard library offers **`functools.lru_cache(maxsize=...)`** and **`functools.cache`** (unbounded, Python 3.9+), with `cache_info()` statistics and `cache_clear()`. Arguments must be hashable. Be careful with methods (the cache holds references to `self`), with mutable return values (callers can modify the cached object) and with functions whose results change over time; for expiring entries, use a **TTL** cache such as those in the `cachetools` library.

## An LRU cache class and lru_cache on a function

OrderedDict for O(1) LRU, and memoising an expensive function.

```python
from collections import OrderedDict
from functools import lru_cache

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data: OrderedDict[str, str] = OrderedDict()

    def get(self, key: str) -> str | None:
        if key not in self.data:
            return None
        self.data.move_to_end(key)                  # mark as most recently used
        return self.data[key]

    def put(self, key: str, value: str) -> None:
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)           # evict the least recently used

cache = LRUCache(2)
cache.put("user:1", "Asha")
cache.put("user:2", "Ravi")
cache.get("user:1")                                 # user:1 is now most recent
cache.put("user:3", "Meera")                        # evicts user:2
print(list(cache.data))                             # ['user:1', 'user:3']

@lru_cache(maxsize=1024)
def shipping_quote(pincode: str, weight_grams: int) -> int:
    # imagine a slow API call or heavy computation here
    zone = int(pincode[0])
    return 4000 + zone * 500 + (weight_grams // 500) * 1500

print(shipping_quote("411001", 1200))               # computed: 4000 + 2000 + 3000 = 9000
print(shipping_quote("411001", 1200))               # served from the cache
print(shipping_quote.cache_info())                  # hits=1, misses=1, maxsize=1024, currsize=1
```

## The front of your desk

An LRU cache is a small desk: papers you touched recently stay on top, and when the desk is full, the paper at the bottom of the pile (untouched the longest) goes back to the filing cabinet.

**Quiz:** Which two OrderedDict methods make an O(1) LRU cache straightforward?

- [ ] sort and reverse
- [ ] append and pop(0)
- [ ] keys and values
- [x] move_to_end and popitem(last=False)

*Answer:* move_to_end and popitem(last=False). move_to_end updates recency and popitem(last=False) evicts the oldest entry.