TopolearnBuilding LRU caches and order-sensitive structures is simplest with OrderedDict's extra operations.
Since Python 3.7, plain dict keeps insertion order, so OrderedDict is no longer needed just for ordering. It remains useful for its extra operations:
od.move_to_end(key)moves a key to the end (or the front withlast=False) in O(1).od.popitem(last=False)removes the first item (FIFO); plaindict.popitem()only removes the last.- Equality between two OrderedDicts is order-sensitive:
OrderedDict(a=1, b=2) != OrderedDict(b=2, a=1). Compared with a plain dict, order is ignored.
These make it the classic building block for an LRU cache (least recently used): on every access, move_to_end(key); when the cache is full, popitem(last=False) evicts the oldest entry.
In everyday code, prefer plain dicts: they're faster and use less memory. For caching function results, functools.lru_cache is ready-made; reach for OrderedDict when you need custom eviction policies or caches keyed by something other than function arguments.
You can reorder a plain dict only by rebuilding it, for example dict(sorted(d.items())).
Example
from collections import OrderedDict
class LRU:
def __init__(self, capacity):
self.data, self.capacity = OrderedDict(), capacity
def get(self, key):
if key not in self.data:
return None
self.data.move_to_end(key) # mark as recently used
return self.data[key]
def put(self, key, value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False) # evict least recently used
cache = LRU(2)
cache.put("a", 1); cache.put("b", 2)
cache.get("a")
cache.put("c", 3) # evicts "b"
print(list(cache.data)) # ['a', 'c']
print(OrderedDict(a=1, b=2) == OrderedDict(b=2, a=1)) # False
print(OrderedDict(a=1, b=2) == dict(b=2, a=1)) # TrueRemember
- Plain dicts are insertion-ordered; OrderedDict adds
move_to_endandpopitem(last=False) - OrderedDict equality is order-sensitive with other OrderedDicts
- It's the classic structure for custom LRU caches
Watch out for
- Using OrderedDict everywhere just for ordering, which plain dicts already provide.