I have a need where I need to implement NRU (Not Recently Free) algorithm. Current data structure is just simple map, something like
map[string]bool
Basically this is hashmap for string to availability. But instead of just being bool, I want to include some timestamp so that along with whether a particular string is avail or not, I also will pick Not Recently Freed (Oldest) string. Wondering about how to modify the Go's Data structure.
I am thinking of
map[string]bool+timestamp
That way, if let's say highest bit is set, that shows available or not and timestamp will help me to search through based on time.
If you want to store two types in the value part of a map you can do so by creating a new struct type:
type Value struct {
avail bool
timestamp time.Time
}
Then you can create a map as follows:
m := map[string] Value{}
And add to the map:
m["some-value"] = Value{avail:true, timestamp: time.Now()}
It's a little unusual to want to keep empty slots in a map. If you want to remove an element from a map, you can delete it, and then you can use the two-result form index expression to test whether something is in the map or not.
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")
}
Usually you need more than just a map of key to value to implement least-recently-used; you need some other side data structure like a doubly-linked list to remember which order they've been used in. (If you do have some persistent value like a timestamp, a heap would work too.) You could store pairs of actual values and timestamps in the map values, but then you have to search through the whole list to find the oldest one.
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)
}
}