LRU-K
LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。也就是说没有到达K次访问的数据并不会被缓存，这也意味着需要对于缓存数据的访问次数进行计数，并且访问记录不能无限记录，也需要使用替换算法进行替换。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
缺点
缺点是需要一块空间存储history
之前我们学的LRU算法其实就是LRU-1, 一般会考虑才用LRU-2
核心思想
有两个存储空间，一块叫历史空间，存储访问次数低于K的缓存；另一块叫缓存空间，存储超过K次的数据。历史空间按照一定的算法淘汰过期数据（FIFO, LRU，文章中采用的是LRU），当数据访问次数达到K次，则将其加入到缓存空间中，并从历史空间中删除。
代码
package main
import (
"container/list"
"fmt"
)
type Item struct {
k int
v int
visit int
}
func NewItem(k int, v int, visit int) *Item {
return &Item{k: k, v: v, visit: visit}
}
type LRUKCache struct {
k int
historyCap int
history *list.List
historyData map[int]*list.Element
cacheCap int
cache *list.List
cacheData map[int]*list.Element
}
func NewLRUKCache(k int, historyCap int, cacheCap int) LRUKCache {
return LRUKCache{
k: k,
historyCap: historyCap,
history: list.New(),
historyData: make(map[int]*list.Element),
cacheCap: historyCap,
cache: list.New(),
cacheData: make(map[int]*list.Element),
}
}
func (ll *LRUKCache) Get(k int) int {
item, ok := ll.cacheData[k]
if ok {
ll.cache.MoveToFront(item)
return item.Value.(*Item).v
}
item, ok = ll.historyData[k]
if ok {
node := item.Value.(*Item)
node.visit++
if node.visit == ll.k {
ll.addCache(item)
}
return node.v
}
return -1
}
func (ll *LRUKCache) Put(k int, v int) {
if ll.cacheCap == 0 {
return
}
item, ok := ll.cacheData[k]
if ok {
item.Value.(*Item).v = v
ll.cache.MoveToFront(item)
return
}
item, ok = ll.historyData[k]
if ok {
node := item.Value.(*Item)
node.v = v
node.visit++
if node.visit == k {
ll.addCache(item)
}
return
}
node := NewItem(k, v, 1)
ll.addHistory(k, node)
}
func (ll *LRUKCache) addHistory(k int, item interface{}) {
if ll.history.Len() == ll.historyCap {
oldItem := ll.history.Back()
ll.history.Remove(oldItem)
delete(ll.historyData, oldItem.Value.(*Item).k)
}
ele := ll.history.PushFront(item)
ll.historyData[k] = ele
}
func (ll *LRUKCache) addCache(item *list.Element) {
node := item.Value.(*Item)
if ll.cache.Len() == ll.cacheCap {
oldItem := ll.cache.Back()
ll.cache.Remove(oldItem)
delete(ll.cacheData, oldItem.Value.(*Item).k)
}
ele := ll.cache.PushFront(node)
ll.cacheData[node.k] = ele
ll.history.Remove(item)
delete(ll.historyData, node.k)
}