// lfu.go
// description: a type of cache algorithm used to manage memory within a computer.
// details:
// The standard characteristics of this method involve the system keeping track of the number of times a block is referenced in memory.
// When the cache is full and requires more room the system will purge the item with the lowest reference frequency.
// ref: (https://en.wikipedia.org/wiki/Least_frequently_used)
// time complexity: O(N)
// space complexity: O(1)
// author: [CocaineCong](https://github.com/CocaineCong)
package cache
import (
"container/list"
"math"
)
// LFU the Least Frequently Used (LFU) page-replacement algorithm
type LFU struct {
len int // length
cap int // capacity
minFreq int // The element that operates least frequently in LFU
// key: key of element, value: value of element
itemMap map[string]*list.Element
// key: frequency of possible occurrences of all elements in the itemMap
// value: elements with the same frequency
freqMap map[int]*list.List
}
// NewLFU init the LFU cache with capacity
func NewLFU(capacity int) LFU {
return LFU{
len: 0,
cap: capacity,
minFreq: math.MaxInt,
itemMap: make(map[string]*list.Element),
freqMap: make(map[int]*list.List),
}
}
// initItem to init item for LFU
func initItem(k string, v any, f int) item {
return item{
key: k,
value: v,
freq: f,
}
}
// Get the key in cache by LFU
func (c *LFU) Get(key string) any {
// if existed, will return value
if e, ok := c.itemMap[key]; ok {
// the frequency of e +1 and change freqMap
c.increaseFreq(e)
obj := e.Value.(item)
return obj.value
}
// if not existed, return nil
return nil
}
// Put the key in LFU cache
func (c *LFU) Put(key string, value any) {
if e, ok := c.itemMap[key]; ok {
// if key existed, update the value
obj := e.Value.(item)
obj.value = value
c.increaseFreq(e)
} else {
// if key not existed
obj := initItem(key, value, 1)
// if the length of item gets to the top line
// remove the least frequently operated element
if c.len == c.cap {
c.eliminate()
c.len--
}
// insert in freqMap and itemMap
c.insertMap(obj)
// change minFreq to 1 because insert the newest one
c.minFreq = 1
// length++
c.len++
}
}
// increaseFreq increase the frequency if element
func (c *LFU) increaseFreq(e *list.Element) {
obj := e.Value.(item)
// remove from low frequency first
oldLost := c.freqMap[obj.freq]
oldLost.Remove(e)
// change the value of minFreq
if c.minFreq == obj.freq && oldLost.Len() == 0 {
// if it is the last node of the minimum frequency that is removed
c.minFreq++
}
// add to high frequency list
c.insertMap(obj)
}
// insertMap insert item in map
func (c *LFU) insertMap(obj item) {
// add in freqMap
l, ok := c.freqMap[obj.freq]
if !ok {
l = list.New()
c.freqMap[obj.freq] = l
}
e := l.PushFront(obj)
// update or add the value of itemMap key to e
c.itemMap[obj.key] = e
}
// eliminate clear the least frequently operated element
func (c *LFU) eliminate() {
l := c.freqMap[c.minFreq]
e := l.Back()
obj := e.Value.(item)
l.Remove(e)
delete(c.itemMap, obj.key)
}