Pouvez-vous expliquer le principe de fonctionnement du cache LRU et dans quelles situations il est utilisé?

La cache LRU (Least Recently Used) est une structure de données qui stocke un nombre limité d'éléments et, en cas de dépassement, supprime l'élément le plus ancien non utilisé.

Principe de fonctionnement :

• Lorsqu'un élément est accédé, il devient le "plus récent".
• Si la cache est pleine et qu'il faut ajouter un nouvel élément, l'élément le plus ancien non utilisé est supprimé.

Cela permet d'utiliser efficacement la mémoire en conservant les données les plus pertinentes.

Applications :

• Mise en cache des résultats de requêtes à une base de données.
• Mise en cache d'images ou de fichiers en mémoire.
• Dans les systèmes à ressources limitées pour optimiser l'accès aux données.

Exemple en Go (simplifié) :

// Utilisation du conteneur list pour maintenir l'ordre d'utilisation
import (
    "container/list"
)

type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    list     *list.List
}

type entry struct {
    key   int
    value int
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*list.Element),
        list:     list.New(),
    }
}

func (c *LRUCache) Get(key int) (int, bool) {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        return elem.Value.(*entry).value, true
    }
    return 0, false
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        c.list.MoveToFront(elem)
        elem.Value.(*entry).value = value
        return
    }
    if c.list.Len() == c.capacity {
        back := c.list.Back()
        if back != nil {
            c.list.Remove(back)
            delete(c.cache, back.Value.(*entry).key)
        }
    }
    elem := c.list.PushFront(&entry{key, value})
    c.cache[key] = elem
}