Ar turite patirties įgyvendinant mažiausiai neseniai naudotų elementų (LRU) talpyklos algoritmą?

Taip, mažiausiai neseniai naudoto (LRU) talpyklos algoritmą galima įgyvendinti Go kalba naudojant duomenų struktūrą, kuri užtikrina greitą prieigą ir naudojimo tvarkos atnaujinimą. Paprastai tam naudojama maišos lentelė ir dvipusė sąrašas:

Paprastas LRU talpyklos pavyzdys Go kalba:

package main

import "container/list"

// LRUCache struktūra
// capacity - maksimalus dydis
// cache - greitos prieigos maišos lentelė
// list - dvipusis sąrašas naudojimo tvarkai

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 int, 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
}

func main() {
    cache := NewLRUCache(2)
    cache.Put(1, 1)
    cache.Put(2, 2)
    val, ok := cache.Get(1) // val=1, ok=true
    cache.Put(3, 3)         // ištrins raktą 2
    _, ok2 := cache.Get(2)  // ok2=false
    _ = val
    _ = ok2
}

Šiame pavyzdyje, pridedant naują elementą, jei talpykla pilna, ištrinamas mažiausiai neseniai naudotas elementas (sąrašo pabaiga). Kai pasiekiamas elementas, jis perkeliama į sąrašo pradžią, rodant, kad jis yra naujausiai naudotas.