Publié · en amélioration
Algorithm
Un cache LRU évince l'entrée inutilisée depuis le plus longtemps quand il est plein ; table de hachage et liste doublement chaînée rendent get et put O(1).
Un cache LRU (least recently used, moins récemment utilisé) est un cache de capacité fixe qui, lorsqu'il est plein, évince l'entrée restée inutilisée le plus longtemps. Il s'appuie sur la localité temporelle, c'est-à-dire sur le fait que des données utilisées récemment le seront probablement de nouveau bientôt, et contrairement à FIFO il actualise la position d'une entrée à chaque lecture. L'implémentation classique associe une table de hachage, qui retrouve le nœud d'une clé, à une liste doublement chaînée qui garde l'ordre d'utilisation ; get et put s'exécutent alors en O(1) en moyenne.
LRU, exact ou approché, se retrouve à presque tous les niveaux d'un système : caches du processeur, cache de pages du système d'exploitation, buffer pools des bases de données, politiques d'éviction de Redis, CDN et caches des navigateurs. Les bibliothèques standard le proposent aussi, comme functools.lru_cache et OrderedDict en Python ou LinkedHashMap en Java. Comme il réunit table de hachage et liste chaînée dans une même conception, c'est aussi une question classique d'entretien technique.
Commencez par les différences entre politiques d'éviction comme FIFO, LRU, LFU et TTL et par la notion de taux de succès, puis suivez à la main une courte séquence de requêtes. Implémentez ensuite le cache vous-même avec un dictionnaire et une liste doublement chaînée à nœuds sentinelles, et comparez-le aux versions de bibliothèque comme OrderedDict et LinkedHashMap. Enfin, abordez des problèmes concrets : sûreté entre threads, invalidation de cache et combinaison avec une durée d'expiration.
Chaque get ou put réussi déplace l'entrée vers l'extrémité la plus récente ; quand la place manque, l'entrée de l'autre extrémité est évincée.
La table retrouve directement le nœud d'une clé, et la liste détache puis réinsère les nœuds en O(1) pour garder l'ordre.
get et put ne modifient qu'un nombre constant de pointeurs, d'où un temps moyen constant ; la mémoire croît avec la capacité.
Les systèmes réels utilisent souvent CLOCK, pseudo-LRU, LRU par échantillonnage, 2Q ou W-TinyLFU pour réduire le coût ou résister aux grands parcours.
Un dict associe les clés aux nœuds, et une liste doublement chaînée entre les sentinelles head et tail garde l'ordre d'utilisation. get déplace le nœud en tête ; put évince le nœud juste avant tail quand le cache est plein. python lru_cache.py évince "b" et affiche None 1 3.
lru_cache.py
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # key -> Node
self.head, self.tail = Node(), Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key, default=None):
node = self.map.get(key)
if node is None:
return default
self._unlink(node) # touch: move to the front
self._push_front(node)
return node.value
def put(self, key, value):
if self.capacity <= 0:
return
node = self.map.get(key)
if node is not None:
node.value = value
self._unlink(node)
self._push_front(node)
return
if len(self.map) >= self.capacity: # evict the least recently used
lru = self.tail.prev
self._unlink(lru)
del self.map[lru.key]
node = Node(key, value)
self.map[key] = node
self._push_front(node)
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # "a" is now the most recent
cache.put("c", 3) # full: evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c")) # None 1 3
python lru_cache.pySix chapitres pour aller de l'installation aux notions essentielles de Cache LRU.
Posez vos questions, partagez votre expérience et échangez vos avis sur Cache LRU.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.