Имали ли сте опит с реализирането на алгоритъм за кеш с най-малко наскоро използвани елементи (LRU)?

Да, алгоритъмът за кеш с най-малко наскоро използвани елементи (LRU) може да бъде реализиран в Go с помощта на структура от данни, която поддържа бърз достъп и актуализира реда на използване на елементите. Обикновено се използва комбинация от хеш таблица и двусвързана листа.

Пример за проста реализация на LRU кеш в Go:

package main

import "container/list"

// Структура на LRUCache
// capacity - максимален размер
// cache - хеш таблица за бърз достъп
// 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 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)         // ще премахне ключ 2
    _, ok2 := cache.Get(2)  // ok2=false
    _ = val
    _ = ok2
}

В този пример, при добавяне на нов елемент, ако кешът е пълен, се премахва най-малко използваният елемент (край на списъка). При достъп до елемент, той се преместват в началото на списъка, което отразява неговата недавна употреба.