Kannst du das Funktionsprinzip des LRU-Caches erklären und in welchen Situationen er angewendet wird?

Der LRU-Cache (Least Recently Used) ist eine Datenstruktur, die eine begrenzte Anzahl von Elementen speichert und beim Überlauf das am längsten nicht verwendete Element entfernt.

Funktionsprinzip:

• Beim Zugriff auf ein Element wird es zum "neueren".
• Wenn der Cache voll ist und ein neues Element hinzugefügt werden soll, wird das am längsten nicht verwendete Element entfernt.

Dies ermöglicht eine effiziente Nutzung des Speichers, indem die relevantesten Daten behalten werden.

Anwendungen:

• Caching von Datenbankabfrageergebnissen.
• Caching von Bildern oder Dateien im Speicher.
• In ressourcenbeschränkten Systemen zur Optimierung des Datenzugriffs.

Beispiel in Go (vereinfachte Version):

// Verwendung des container/list zur Verwaltung der Nutzungsreihenfolge
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
}