implémentation de Golang Lru

LRU (Least Récemment Utilisé) est une stratégie courante de remplacement du cache. Lorsque le cache atteint la limite prédéfinie, le cache élimine automatiquement les données les moins récemment utilisées pour libérer de l'espace.

Dans Golang, nous pouvons utiliser des listes doublement chaînées et des tables de hachage pour implémenter le cache LRU. Dans cet article, nous décrivons comment implémenter un cache LRU en utilisant ces deux structures de données.

La fonction de la liste doublement chaînée est de maintenir l'ordre des données mises en cache chaque fois que de nouvelles données sont insérées ou que des données sont consultées, les données seront avancées. Dans le même temps, lorsque le cache atteint la limite supérieure, nous pouvons supprimer les données les moins récemment utilisées de la fin de la liste chaînée.

La fonction de la table de hachage est d'accélérer la recherche de données. Chaque fois que des données sont accédées, nous pouvons trouver rapidement les données mises en cache correspondantes grâce à l'index de données stocké dans la table de hachage. Par conséquent, nous opérerons sur des tables de hachage lors de l’implémentation.

Ensuite, nous expliquerons comment implémenter le cache LRU basé sur des listes doublement chaînées et des tables de hachage. Nous définissons une structure LRUCache et déclarons les pointeurs de tête et de queue de la liste chaînée, ainsi que la carte de la table de hachage et la capacité du cache.

type LRUCache struct {
    head, tail *entry  // 链表头和链表尾指针
    cache      map[int]*entry  // 哈希表存储缓存中的数据
    capacity   int     // 缓存容量
}

Ensuite, nous définirons la structure du nœud de liste doublement chaîné.

type entry struct {
    key, value int        // 存储节点的键值对
    prev, next *entry    // 前驱和后继指针
}

Ici, nous utilisons prev et next pour représenter respectivement les pointeurs prédécesseur et successeur du nœud, et key et value représentent respectivement la paire clé-valeur du nœud.

Ensuite, nous définirons le constructeur NewLRUCache de LRUCache et lui transmettrons la capacité du cache.

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

Dans le constructeur, nous allons initialiser la table de hachage et la capacité du cache.

Ensuite, nous définirons les méthodes Get et Put de LRUCache pour accéder et stocker les données.

Implémentation de la méthode Get :

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

Tout d'abord, nous vérifions si les données correspondantes existent à partir de la table de hachage. Si elles existent, déplacez le nœud en tête de la liste chaînée. , et renvoie la valeur stockée par le nœud. Sinon, -1 est renvoyé.

Ce qui suit est l'implémentation de la méthode moveToHead :

func (c *LRUCache) moveToHead(elem *entry) {
    if elem == c.head {
        return
    } else if elem == c.tail {
        c.tail = elem.prev
    } else {
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
    }

    elem.prev = nil
    elem.next = c.head
    c.head.prev = elem
    c.head = elem
}

Cette méthode reçoit un élément de pointeur de nœud, qui est utilisé pour déplacer le nœud vers la tête de la liste chaînée. Premièrement, si le nœud est déjà en tête de la liste chaînée, retournez ; sinon, si le nœud est en queue de la liste chaînée, mettez à jour le pointeur de queue de la liste chaînée, sinon supprimez le nœud de la liste chaînée ; placez le nœud en tête de la liste chaînée.

Implémentation de la méthode Put :

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.value = value
        c.moveToHead(elem)
    } else {
        // 创建新节点
        elem := &entry{key: key, value: value}
        c.cache[key] = elem
        if c.head == nil {
            c.head = elem
            c.tail = elem
        } else {
            // 在链表头部插入新节点
            elem.next = c.head
            c.head.prev = elem
            c.head = elem
        }
        // 判断缓存是否达到预设上限
        if len(c.cache) > c.capacity {
            // 删除链表尾部节点和哈希表中的数据
            delete(c.cache, c.tail.key)
            c.tail = c.tail.prev
            c.tail.next = nil
        }
    }
}

Tout d'abord, nous déterminons si les données correspondantes existent à partir de la table de hachage. Si elles existent, mettons à jour la valeur stockée dans le nœud et appelons la méthode moveToHead. déplace le nœud en tête de la liste chaînée. Sinon, créez un nouveau nœud et insérez-le en tête de la liste chaînée. Si le cache atteint la limite supérieure prédéfinie, supprimez le nœud de queue de la liste chaînée et les données de la table de hachage.

Enfin, nous avons rassemblé le code complet :

type LRUCache struct {
    head, tail *entry
    cache      map[int]*entry
    capacity   int
}

type entry struct {
    key, value int
    prev, next *entry
}

func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        cache:    make(map[int]*entry),
        capacity: capacity,
    }
}

func (c *LRUCache) Get(key int) int {
    if elem, ok := c.cache[key]; ok {
        // 更新节点位置
        c.moveToHead(elem)
        return elem.value
    }
    return -1
}

func (c *LRUCache) moveToHead(elem *entry) {
    if elem == c.head {
        return
    } else if elem == c.tail {
        c.tail = elem.prev
    } else {
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
    }

    elem.prev = nil
    elem.next = c.head
    c.head.prev = elem
    c.head = elem
}

func (c *LRUCache) Put(key, value int) {
    if elem, ok := c.cache[key]; ok {
        elem.value = value
        c.moveToHead(elem)
    } else {
        // 创建新节点
        elem := &entry{key: key, value: value}
        c.cache[key] = elem
        if c.head == nil {
            c.head = elem
            c.tail = elem
        } else {
            // 在链表头部插入新节点
            elem.next = c.head
            c.head.prev = elem
            c.head = elem
        }
        // 判断缓存是否达到预设上限
        if len(c.cache) > c.capacity {
            // 删除链表尾部节点和哈希表中的数据
            delete(c.cache, c.tail.key)
            c.tail = c.tail.prev
            c.tail.next = nil
        }
    }
}

Dans cet article, nous avons présenté comment utiliser des listes doublement chaînées et des tables de hachage pour implémenter l'algorithme de cache LRU. Grâce à la mise en œuvre de cet algorithme, nous pouvons gérer efficacement le cache et optimiser l'efficacité de l'accès aux données.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!