LFU (Least Frequently Used) 是一种用于缓存管理的算法。它通过跟踪每个缓存项被访问的频率来决定哪些项应该被移除。LFU算法倾向于保留那些使用频率较高的项,而移除那些使用频率较低的项。以下是LFU算法的详细介绍:
LFU算法的实现可以使用多种数据结构,如哈希表、双向链表和优先队列。以下是一种常见的实现方法:
使用哈希表和优先队列:
具体步骤如下:
LFU算法适用于以下场景:
package lfu
import (
"container/list"
"sync"
)
type entry struct {
key any
value any
freq int
}
type LFUCache struct {
mtx sync.Mutex // protects the cache
capacity int
size int
minFreq int
cache map[any]*list.Element
frequency map[int]*list.List
}
// NewLFUCache creates a new LFU cache
func NewLFUCache(capacity int) *LFUCache {
return &LFUCache{
capacity: capacity,
cache: make(map[any]*list.Element),
frequency: make(map[int]*list.List),
}
}
// Get retrieves a value from the cache
func (c *LFUCache) Get(key any) any {
c.mtx.Lock()
defer c.mtx.Unlock()
if elem, found := c.cache[key]; found {
c.incrementFrequency(elem)
return elem.Value.(*entry).value
}
return nil
}
// Put inserts or updates a value in the cache
func (c *LFUCache) Put(key, value any) {
c.mtx.Lock()
defer c.mtx.Unlock()
if c.capacity == 0 {
return
}
if elem, found := c.cache[key]; found {
elem.Value.(*entry).value = value
c.incrementFrequency(elem)
} else {
if c.size == c.capacity {
c.evict()
}
newEntry := &entry{key, value, 1}
if c.frequency[1] == nil {
c.frequency[1] = list.New()
}
elem := c.frequency[1].PushFront(newEntry)
c.cache[key] = elem
c.minFreq = 1
c.size++
}
}
// incrementFrequency increases the frequency of a cache entry
func (c *LFUCache) incrementFrequency(elem *list.Element) {
e := elem.Value.(*entry)
oldFreq := e.freq
e.freq++
c.frequency[oldFreq].Remove(elem)
if c.frequency[oldFreq].Len() == 0 {
delete(c.frequency, oldFreq)
if c.minFreq == oldFreq {
c.minFreq++
}
}
if c.frequency[e.freq] == nil {
c.frequency[e.freq] = list.New()
}
newElem := c.frequency[e.freq].PushFront(e)
c.cache[e.key] = newElem
}
// evict removes the least frequently used cache entry
func (c *LFUCache) evict() {
list := c.frequency[c.minFreq]
elem := list.Back()
if elem != nil {
list.Remove(elem)
delete(c.cache, elem.Value.(*entry).key)
c.size--
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。