Не недавно использованный алгоритм с использованием карты

Question

У меня есть потребность, где мне нужно реализовать алгоритм NRU (не недавно бесплатный).Текущая структура данных - это просто простая карта, что-то вроде

map[string]bool

По сути, это хэш-карта для строки доступности.Но вместо того, чтобы просто быть bool, я хочу включить некоторую временную метку, чтобы наряду с тем, есть ли конкретный string или нет, я также выберу строку Не недавно освобожден (самая старая).Хотите знать, как изменить структуру данных Go.

Я имею в виду

map[string]bool+timestamp 

Таким образом, если, скажем, установлен максимальный бит, он показывает, доступен или нет, а метка времени поможет мне осуществлять поиск по времени.

Answer 1

Немного необычно хотеть хранить пустые слоты на карте. Если вы хотите удалить элемент с карты, вы можете удалить его, а затем вы можете использовать индексное выражение формы с двумя результатами , чтобы проверить, есть ли что-то на карте или нет .

m := make(map[string]int)
m["x"] = 1
if _, ok := m["x"]; ok {
        fmt.Printf("x is there")
}
delete(m, "x")
if _, ok := m["x"]; !ok {
        fmt.Printf("x is not there")
}

Обычно вам нужно больше, чем просто карта ключ-значение для реализации наименее недавно использованного; вам нужна какая-то другая побочная структура данных, например, двусвязный список , чтобы запомнить, в каком порядке они использовались. (Если у вас есть какое-то постоянное значение, такое как временная метка, куча тоже будет работать.) может хранить пары фактических значений и временных меток в значениях карты, но тогда вам придется искать по всему списку, чтобы найти самый старый.

import "container/list"

type CacheValue struct {
        Key string
        Value int
}

type Cache struct {
        values map[string]*list.Element
        lru *list.List
}

func makeCache() *Cache {
        return &Cache{
                values: make(map[string]*list.Element),
                lru: list.New(),
        }
}

func (c *Cache) Put(k string, v int) {
        cv := CacheValue{Key: k, Value: v}
        el := c.lru.PushFront(&cv)
        c.values[k] = el
}

func (c *Cache) Get(k string) int {
        el, ok := c.values[k]
        if ok {
                c.lru.MoveToFront(el)
                return el.Value.(*CacheValue).Value
        }
        return 0
}

func (c *Cache) DeleteOldest() {
        el := c.lru.Back()
        if el != nil {
                delete(c.values, el.Value.(*CacheValue).Key)
                c.lru.Remove(el)
        }
}

Answer 2

Если вы хотите сохранить два типа в части значений карты, вы можете сделать это, создав новый тип структуры:

type Value struct {
  avail bool
  timestamp time.Time
}

Затем вы можете создать карту следующим образом:

m := map[string] Value{}

И добавить на карту:

m["some-value"] = Value{avail:true, timestamp: time.Now()}