淘汰算法-LRU
原创
LRU(Least Recently Used)：优先淘汰最久使用的缓存 。 LFU(least frequently used)：优先淘汰最少使用的缓存，平局淘汰最近最久未使用的。
题目：
设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
⚠️函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
时间复杂度： O(1):x轴无论是多少y都是1，线性与x轴成平行线。map.key，slice.index O(n):x轴与y轴成正比，x轴值越大y轴数值越高，线性x轴成斜线。查找slice某个值，查找listnode某个node 总结：有循环是O（n），没有循环是O（1） 时间复杂度是度量算法执行时间的长短；空间复杂度是指算法所需存储空间的大小。
示例：
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
slice
type LRUCache struct {
Data map[int]int
Temp []int
Count int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
Data: make(map[int]int),
Temp: make([]int, 0),
Count: capacity,
}
}
func (this *LRUCache) Get(key int) int {
if _, ok := this.Data[key]; !ok {
return -1
}
this.DealTemp(key)
return this.Data[key]
}
func (this *LRUCache) DealTemp(key int) {
if len(this.Temp) > 1 {
for k, v := range this.Temp {
if v == key {
if k != len(this.Temp)-1 {
for j := k; j < len(this.Temp)-1; j++ {
this.Temp[j], this.Temp[j+1] = this.Temp[j+1], this.Temp[j]
}
}
}
}
}
}
func (this *LRUCache) Put(key int, value int) {
if _, ok := this.Data[key]; !ok {
if this.Count == len(this.Temp) {
delete(this.Data, this.Temp[0])
this.Temp = append(this.Temp[1:])
}
this.Temp = append(this.Temp, key)
} else {
this.DealTemp(key)
}
this.Data[key] = value
}链表
type LRUCache struct {
front *linkedList // 虚头节点
back *linkedList // 虚尾节点
record map[int]*linkedList // 节点记录
cap int // 总容量
size int // 已使用大小
}
// 链表节点
type linkedList struct {
key, value int
prev, next *linkedList
}
func Constructor(capacity int) LRUCache {
back := &linkedList{}
front := &linkedList{next: back}
back.prev = front
return LRUCache{
front: front,
back: back,
record: make(map[int]*linkedList),
cap: capacity,
}
}
func (c *LRUCache) Get(key int) int {
// 查询缓存时直接通过节点记录索引到对应节点
node, has := c.record[key]
if !has {
return -1
}
// 查询到缓存后需要把对应的缓存节点移到链表头
c.moveToFront(node)
return node.value
}
func (c *LRUCache) Put(key int, value int) {
// 如果要插入的缓存已经存在就更新对应的值然后将节点移至头部
if node, has := c.record[key]; has {
node.value = value
c.moveToFront(node)
return
}
// 所有可用容量都已经使用完的时候删除尾节点（即虚尾节点的前驱）
if c.size == c.cap {
c.remove(c.back.prev)
}
// 记得记录下新的节点
c.record[key] = &linkedList{key: key, value: value}
c.insertToFront(c.record[key])
}
// 移动节点到链表头
func (c *LRUCache) moveToFront(node *linkedList) {
node.prev.next = node.next
node.next.prev = node.prev
node.next = c.front.next
c.front.next.prev = node
c.front.next = node
node.prev = c.front
}
// 插入新的节点
func (c *LRUCache) insertToFront(node *linkedList) {
c.front.next.prev = node
node.next = c.front.next
c.front.next = node
node.prev = c.front
c.size++
}
// 从链表中删除节点
func (c *LRUCache) remove(node *linkedList) {
node.prev.next = node.next
node.next.prev = node.prev
c.size--
delete(c.record, node.key)
}执行效率
说明：前两个为链表结果，第三个为slice结果，该算法链表实现效率高。
应用场景-Redis
Redis3.0-近似LRU
算法会维护一个缓存池（大小为16），池中的数据根据访问时间进行排序，第一次随机选取的5个key都会放入池中（可以通过maxmemory-samples参数修改采样数量， 如：maxmemory-samples 10。maxmenory-samples配置的越大，淘汰的结果越接近于严格的LRU算法，但因此耗费的CPU也很高。），随后每次随机选取的key只有在访问时间早于池中最早的时间才会放入池中，直到候选池被放满。当放满后，如果有新的key需要放入，则将池中最后访问时间最晚，也就是最近被访问的移除。
当需要淘汰的时候，则直接从池中选取最久没被访问的key淘汰掉就行。
附：Redis4.0-LFU
LFU的核心思想是根据key的最近被访问的频率进行淘汰，很少被访问的优先被淘汰，被访问的多的则被留下来。
LFU算法能更好的表示一个key被访问的热度。假如你使用的是LRU算法，一个key很久没有被访问到，只刚刚是偶尔被访问了一次，那么它就被认为是热点数据，不会被淘汰，而有些key将来是很有可能被访问到的则被淘汰了。如果使用LFU算法则不会出现这种情况，因为使用一次并不会使一个key成为热点数据。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。