Comment implémenter un système de cache de l'algorithme LRU dans Golang

LRU (Least Récemment Utilisé) est un algorithme de mise en cache. Il peut d'abord mettre en cache les données récemment utilisées et éliminer les données qui n'ont pas été utilisées depuis longtemps avec une capacité de cache limitée, permettant ainsi une utilisation efficace de l'espace du cache et améliorant la vitesse d'accès aux données.

Le langage Go (golang) est un langage de programmation efficace qui est privilégié par les développeurs pour ses excellentes capacités de concurrence et de gestion de la mémoire. Dans cet article, nous allons implémenter un système de mise en cache pour l'algorithme LRU et utiliser le langage Go pour l'implémenter.

Idées de conception

Avant de mettre en œuvre un système de cache LRU, nous devons déterminer la configuration système requise et les idées de conception.

Tout d'abord, nous avons besoin d'une structure de données pour sauvegarder les données mises en cache. Cette structure de données doit prendre en charge un accès et des mises à jour rapides, et elle doit également prendre en charge l'élimination des données en fonction de la durée d'utilisation. Les structures de données couramment utilisées incluent les listes chaînées, les tables de hachage, les listes doublement chaînées, etc. Parmi elles, les listes doublement chaînées sont le meilleur choix pour implémenter l'algorithme LRU.

Deuxièmement, nous avons besoin de quelques opérations pour accéder et mettre à jour cette structure de données. Les opérations courantes incluent : la lecture des données du cache, l'écriture des données du cache, la mise à jour des données du cache, la suppression des données du cache, etc.

Enfin, nous avons besoin de stratégies de mise en cache pour contrôler la taille du cache et empêcher le cache de remplir toute la mémoire. Les stratégies couramment utilisées incluent FIFO (premier entré, premier sorti), LFU (le moins fréquemment utilisé), LRU (le moins récemment utilisé), etc. Parmi elles, LRU est le meilleur choix pour implémenter un système de cache LRU.

Implémentation du code

Maintenant, nous avons une idée de conception claire et pouvons commencer à implémenter notre système de cache LRU. Le code est le suivant :

package lruCache

import "container/list"

type Cache struct {
    MaxBytes  int64
    nBytes    int64
    ll        *list.List
    cache     map[string]*list.Element
    OnEvicted func(key string, value Value)
}

type entry struct {
    key   string
    value Value
}

type Value interface {
    Len() int
}

func (c *Cache) Add(key string, value Value) {
    if e, ok := c.cache[key]; ok {
        c.ll.MoveToFront(e)
        kv := e.Value.(*entry)
        c.nBytes += int64(value.Len()) - int64(kv.value.Len())
        kv.value = value
    } else {
        ele := c.ll.PushFront(&entry{key, value})
        c.cache[key] = ele
        c.nBytes += int64(len(key)) + int64(value.Len())
    }
    for c.MaxBytes != 0 && c.MaxBytes < c.nBytes {
        c.RemoveOldest()
    }
}

func (c *Cache) Get(key string) (value Value, ok bool) {
    if ele, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ele)
        kv := ele.Value.(*entry)
        return kv.value, true
    }
    return
}

func (c *Cache) RemoveOldest() {
    ele := c.ll.Back()
    if ele != nil {
        c.ll.Remove(ele)
        kv := ele.Value.(*entry)
        delete(c.cache, kv.key)
        c.nBytes -= int64(len(kv.key)) + int64(kv.value.Len())
        if c.OnEvicted != nil {
            c.OnEvicted(kv.key, kv.value)
        }
    }
}

Exemple d'utilisation

Maintenant, nous avons implémenté un système de cache LRU simple. Nous pouvons l'utiliser avec l'exemple de code suivant :

package main

import (
    "fmt"
    "go-lru-cache/lruCache"
)

type stringValue string

func (s stringValue) Len() int {
    return len(s)
}

func main() {
    cache := lruCache.Cache{
        MaxBytes: 1000,
        OnEvicted: func(key string, value lruCache.Value) {
            fmt.Printf("key=%s, value=%s is evicted\n", key, value)
        },
    }
    cache.Add("key1", stringValue("123"))
    cache.Add("key2", stringValue("456"))
    cache.Add("key3", stringValue("789"))
    if value, ok := cache.Get("key1"); ok {
        fmt.Println(value.(stringValue))
    }
    cache.Add("key4", stringValue("101"))
    fmt.Printf("cache.Len() = %d\n", cache.Len())
    cache.RemoveOldest()
    fmt.Printf("cache.Len() = %d\n", cache.Len())
}

Dans l'exemple de code ci-dessus, nous définissons une stringValue类型，实现了Value接口，用来表示缓存中的值。然后，我们创建了一个LRU缓存系统，添加了4个缓存项，其中MaxBytes表示缓存的最大容量。接着，我们通过Get方法获取了缓存中key1 valeur correspondante, puis ajoutons un nouvel élément de cache, et enfin supprimons l'élément de cache le plus ancien.

Résumé

Jusqu'à présent, nous avons implémenté avec succès un système de cache LRU. Grâce à cet article, nous avons non seulement appris l'implémentation de l'algorithme de cache LRU, mais également comment utiliser le langage Go pour implémenter le système de cache. Dans le développement réel, une utilisation rationnelle du système de cache peut améliorer considérablement les performances du programme et réduire la charge du système. Par conséquent, le système de mise en cache est l’une des compétences importantes que tout développeur doit comprendre et maîtriser.

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!