Привет! В этой статье я хочу поделиться своим опытом работы с MRU (most recently used) кешем. Эта структура данных очень полезна, когда нам нужно хранить элементы с определенным ограничением по размеру и автоматически удалять самые старые элементы при достижении этого ограничения.Для начала, я хотел бы представить вам структуру MRUCache. Она представляет собой кеш с определенным размером, который мы задаем при создании нового инстанса кеша. Вот как она выглядит в коде⁚
go
type MRUCache struct {
// Ваш код здесь
}
Теперь давайте посмотрим на сигнатуру функций этой структуры. В методе `NewMRUCache` мы создаем и возвращаем новый инстанс кеша с заданным размером⁚
go
func NewMRUCache(capacity int) *MRUCache {
// Ваш код здесь
}
Метод `Set` используется для установки значения `value` по ключу `key` в нашем кеше⁚
go
func (c *MRUCache) Set(key, value string) {
// Ваш код здесь
}
И, наконец, метод `Get` используется для получения значения и флага его наличия по ключу `key`⁚
go
func (c *MRUCache) Get(key string) (string, bool) {
// Ваш код здесь
}
Когда я столкнулся с необходимостью использования MRU кеша, я реализовал его следующим образом. У меня был срез `cache`, который хранил все элементы в порядке их использования (наиболее недавно использованный элемент был первым). Каждый элемент в этом срезе являлся структурой `CacheItem`, которая хранила ключ `key` и значение `value`.При вызове метода `Set`, я сначала проверял, есть ли уже такой ключ `key` в нашем кеше. Если ключ существует, я обновлял его значение и перемещал его в начало среза, чтобы показать, что он был недавно использован. Если ключ не существует, я проверял, достигнуто ли максимальное значение размера кеша `capacity`. Если достигнуто, я удалял последний элемент в срезе, так как он был самым старым, и добавлял новый элемент в начало среза. Если максимальное значение размера кеша не достигнуто, я просто добавлял новый элемент в начало среза.
При вызове метода `Get`, я искал элемент с заданным ключом `key` в нашем срезе. Если элемент найден, я возвращал его значение и устанавливал флаг наличия в `true`. Также я перемещал этот элемент в начало среза, чтобы показать, что он был недавно использован. Если элемент не найден, я возвращал пустое значение и флаг наличия в `false`.Вот как это выглядело в моей реализации⁚
go
type CacheItem struct {
key string
value string
}
type MRUCache struct {
capacity int
cache []CacheItem
}
func NewMRUCache(capacity int) *MRUCache {
return nMRUCache{
capacity⁚ capacity,
cache⁚ []CacheItem{},
}
}
func (c *MRUCache) Set(key, value string) {
for i, item ⁚ range c.cache {
if item.key key {
c.cache[i].value value
c.moveToFront(i)
return
}
}
if len(c.cache) > c.capacity {
c;cache c.cache[⁚len(c.cache)-1]
}
newItem ⁚ CacheItem{key⁚ key, value⁚ value}
c.cache append([]CacheItem{newItem}, c.cache...)
}
func (c *MRUCache) Get(key string) (string, bool) {
for i, item ⁚ range c.cache {
if item.key key {
c.moveToFront(i)
return item.value, true
}
}
return ″″, false
}
func (c *MRUCache) moveToFront(index int) {
item ⁚ c.cache[index]
c.cache append(c.cache[⁚index], c.cache[index 1⁚]...)
c.cache append([]CacheItem{item}, c.cache...)
}
Вот и все! Я надеюсь, что этот опыт работы с MRU кешем будет полезным для вас. Эта структура данных очень эффективна, когда нам нужно хранить недавно использованные элементы с ограничением по размеру. Благодаря этому кешу мы можем эффективно управлять памятью и ускорить нашу программу.