So implementieren Sie ein Cache-System des LRU-Algorithmus in Golang

LRU (Least Recent Used) ist ein Caching-Algorithmus, der kürzlich verwendete Daten zuerst zwischenspeichern und Daten, die längere Zeit nicht verwendet wurden, bei begrenzter Cache-Kapazität eliminieren kann, wodurch eine effiziente Nutzung des Cache-Speicherplatzes erreicht und die Datenzugriffsgeschwindigkeit verbessert wird.

Go-Sprache (Golang) ist eine effiziente Programmiersprache, die von Entwicklern wegen ihrer hervorragenden Parallelitäts- und Speicherverwaltungsfunktionen bevorzugt wird. In diesem Artikel implementieren wir ein Caching-System für den LRU-Algorithmus und verwenden zur Implementierung die Go-Sprache.

Designideen

Bevor wir ein LRU-Cache-System implementieren, müssen wir die Systemanforderungen und Designideen ermitteln.

Zunächst benötigen wir eine Datenstruktur zum Speichern zwischengespeicherter Daten. Diese Datenstruktur muss einen schnellen Zugriff und Aktualisierungen unterstützen und außerdem die Löschung von Daten entsprechend der Nutzungsdauer unterstützen. Zu den häufig verwendeten Datenstrukturen gehören verknüpfte Listen, Hash-Tabellen, doppelt verknüpfte Listen usw. Unter diesen sind doppelt verknüpfte Listen die beste Wahl für die Implementierung des LRU-Algorithmus.

Zweitens benötigen wir einige Vorgänge, um auf diese Datenstruktur zuzugreifen und sie zu aktualisieren. Zu den üblichen Vorgängen gehören: zwischengespeicherte Daten lesen, zwischengespeicherte Daten schreiben, zwischengespeicherte Daten aktualisieren, zwischengespeicherte Daten löschen usw.

Schließlich benötigen wir einige Caching-Strategien, um die Größe des Caches zu kontrollieren und zu verhindern, dass der Cache den gesamten Speicher füllt. Zu den häufig verwendeten Strategien gehören FIFO (first in, first out), LFU (am wenigsten häufig verwendet), LRU (am wenigsten kürzlich verwendet) usw. Unter diesen ist LRU die beste Wahl für die Implementierung eines LRU-Cache-Systems.

Code-Implementierung

Jetzt haben wir eine klare Designidee und können mit der Implementierung unseres LRU-Cache-Systems beginnen. Der Code lautet wie folgt:

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)
        }
    }
}

Anwendungsbeispiel

Jetzt haben wir ein einfaches LRU-Cache-System implementiert. Wir können es mit dem folgenden Beispielcode verwenden:

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())
}

Im obigen Beispielcode definieren wir einen stringValue类型，实现了Value接口，用来表示缓存中的值。然后，我们创建了一个LRU缓存系统，添加了4个缓存项，其中MaxBytes表示缓存的最大容量。接着，我们通过Get方法获取了缓存中key1 entsprechenden Wert, fügen dann ein neues Cache-Element hinzu und löschen schließlich das älteste Cache-Element.

Zusammenfassung

Bisher haben wir erfolgreich ein LRU-Cache-System implementiert. Durch diesen Artikel haben wir nicht nur die Implementierung des LRU-Cache-Algorithmus gelernt, sondern auch gelernt, wie man die Go-Sprache zum Implementieren des Cache-Systems verwendet. In der tatsächlichen Entwicklung kann die rationelle Nutzung des Cache-Systems die Programmleistung erheblich verbessern und die Systemlast verringern. Daher ist das Caching-System eine der wichtigen Fähigkeiten, die jeder Entwickler verstehen und beherrschen sollte.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie ein Cache-System des LRU-Algorithmus in Golang. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!