LRU和LFU的区别
LRU和LFU都是内存治理的页面置换算法。
LRU：最近起码应用(最长工夫)淘汰算法（Least Recently Used）。LRU是淘汰最长工夫没有被应用的页面。
LFU：最不常常应用(起码次)淘汰算法（Least Frequently Used）。LFU是淘汰一段时间内，应用次数起码的页面。
-
例子
假如LFU办法的期间T为10分钟，拜访如下页面所花的工夫正好为10分钟，内存块大小为3。若所需页面程序顺次如下：
2 1 2 1 2 3 4
—————————————->
- 当须要应用页面4时，内存块中存储着1、2、3，内存块中没有页面4，就会产生缺页中断，而且此时内存块已满，须要进行页面置换。
- 若按LRU算法，应替换掉页面1。因为页面1是最长工夫没有被应用的了，页面2和3都在它前面被应用过。
- 若按LFU算法，应换页面3。因为在这段时间内，页面1被拜访了2次，页面2被拜访了3次，而页面3只被拜访了1次，一段时间内被拜访的次数起码。
LRU 要害是看页面最初一次被应用到产生替换的工夫长短，工夫越长，页面就会被置换；
LFU要害是看肯定时间段内页面被应用的频率（次数），应用频率越低，页面就会被置换。
- LRU算法适宜：较大的文件比方游戏客户端（最近加载的地图文件）;
- LFU算法适宜：较小的文件和系统的文件比方系统文件、应用程序文件 ;
- LRU耗费CPU资源较少，LFU耗费CPU资源较多。
LRU (最长工夫)
最近最久未应用算法, LRU是淘汰最长工夫没有被应用的页面
性能
- 缓存容量capacity为正整数，缓存的key、value均为int类型
-
读缓存
func get(key int) int：- key已存在，返回对应value
- key不存在，返回-1
-
写缓存func put(key int, value int)：
- key已存在，批改对应value
- key不存在，写入该组缓存，若写入前缓存容量已达下限，则应淘汰最久未应用的缓存（强调：读、写缓存均视为应用）
数据结构
应用双向链表保护缓存的上一次应用工夫：
- 约定：链表正方向（从头部到尾部）节点依照应用工夫排序——越早应用（即久未应用）的节点，越凑近链表尾部
- 保护：每应用一次缓存，就将该缓存对应的链表节点挪动到链表头部；缓存淘汰时，只须要删除尾部节点即可
- 减少一个map，记录
key到链表节点的映射关系; 解决如果只应用双向链表，每次判断key是否存在时，都要遍历链表
- cache：
map[int]*listNode，key到节点的映射; 其中 listNode data：key,value - list：
*listNode，双向链表，保护缓存的上一次应用工夫 - capacity：
int，链表容量
伪代码
-
读缓存
-
key存在：
- 在原链表中删除该缓存节点，从新插入到链表头部,
- 返回对应的value
-
key不存在:
- 返回-1
-
-
写缓存(更新缓存)
-
Key存在:
- 更新缓存节点的value值
- 在原链表中删除该缓存节点，并把该从新插入到链表头部
-
Key不存在:
-
容量已达下限：
- 在链表中删除尾部节点（记录该节点的key）
- 依据上一步中记录的key，删除对应的映射关系
- 依据输出参数结构新的节点：
- 将新的节点插入链表头部
- 新增key到新的节点的映射关系
-
容量未达下限：
- 依据输出参数结构新的节点：
- 将新的节点插入链表头部
- 新增key到新的节点的映射关系
-
-
Golang代码实现
// 双向链表节点
type doublyListNode struct {
key int
value int
prev *doublyListNode
next *doublyListNode
}
// 结构一个双向空链表(首尾几点都是空节点)
func newDoublyList() *doublyListNode {
headNode := &doublyListNode{}
tailNode := &doublyListNode{}
headNode.next = tailNode
tailNode.prev = headNode
return headNode
}
// 把节点增加到链表头部
func (dl *doublyListNode) addToHead(node *doublyListNode) {
dl.next.prev = node
node.next = dl.next
dl.next = node
node.prev = dl
}
// 删除链表中的节点
func removeNode(node *doublyListNode) {
node.next.prev = node.prev
node.prev.next = node.next
}
// LRUCache 具体的缓存
type LRUCache struct {
cache map[int]*doublyListNode
head *doublyListNode
tail *doublyListNode
capacity int
}
// Constructor 构建缓存容器
func Constructor(capacity int) LRUCache {
dl := newDoublyList()
return LRUCache{
cache: make(map[int]*doublyListNode),
head: dl,
tail: dl.next,
capacity: capacity,
}
}
func (lruCache *LRUCache) Get(key int) int {
// 依据key 获取缓存
v, ok := lruCache.cache[key]
// 如果没有缓存, 返回-1
if !ok {
return -1
}
// 如果有缓存
removeNode(v) // 移除该缓存
lruCache.head.addToHead(v) // 把缓存增加双向链表头部
return v.value
}
// Put 新建缓存
func (lruCache *LRUCache) Put(key int, value int) {
// 曾经有缓存
if v, ok := lruCache.cache[key]; ok { // v 是双链表中的节点
v.value = value // 更新链表节点中的值
lruCache.cache[key] = v // 更新缓存中映射关系
removeNode(v) // 移除该缓存
lruCache.head.addToHead(v) // 把缓存增加双向链表头部
return
}
// 缓存超长 淘汰缓存
if len(lruCache.cache) >= lruCache.capacity {
node := lruCache.tail.prev
removeNode(node) // 删除该节点
delete(lruCache.cache, node.key) // 革除 最近起码应用的缓存
}
newNode := &doublyListNode{
key: key,
value: value,
}
lruCache.cache[key] = newNode
lruCache.head.addToHead(newNode)
}LFU (起码次)
性能
- 缓存容量capacity、缓存的key和value均为自然数（能够为0，代码中独自解决）
-
读缓存func get(key int) int：（与lru雷同）
- key已存在，返回对应value
- key不存在，返回-1
-
写缓存func put(key int, value int)：
- key已存在，批改对应value
- key不存在，写入该组缓存，若写入前缓存容量已达下限，则应淘汰应用次数起码的缓存（记其应用次数为n）；
- 若应用次数为n的缓存数大于一个，则淘汰最久未应用的缓存（即，此时恪守lru规定）
数据结构
// LFUCache 具体的缓存 frequency 是应用次数
type LFUCache struct {
recent map[int]*doublyListNode // frequency 到应用次数为 frequency 的节点中，最近应用的一个的映射
count map[int]int // frequency 到对应频率的节点数量的映射
cache map[int]*doublyListNode // key到节点的映射
list *doublyList // 双向链表，保护缓存的应用次数（优先）和上一次应用工夫
capacity int // 容量
}伪代码
-
读缓存
-
存在：（记节点frequency为n）
- 若存在其余frequency = n+1的节点，则将节点挪动到所有frequency = n+1的节点的后面；
- 否则，若存在其余frequency = n的节点，且以后节点不是最近节点，则将节点挪动到所有frequency = n的节点的后面；
- 否则，不挪动节点（该状况下，节点就应该呆在它当初的地位）
- 更新recent
- 更新count
- 将节点frequency +1
- 返回节点的value
- 不存在：返回-1
-
-
写缓存
-
key存在
- 参考读缓存——key存在，额定批改对应的value即可
-
不存在：
-
若以后缓存容量已达下限：
- 淘汰尾部的缓存节点（记节点freq为n）
- 若不存在其余freq = n的节点，则将recent置空
- 更新cache
- 更新count
-
结构新节点：key，value，frequency = 1
- 是否存在其余frequency = 1的节点：
- 存在：插入到它们的后面
- 不存在：插入链表尾部
- 更新recent
- 更新cache
- 更新count
-
-
Golang代码实现
// 双向链表
type doublyList struct {
head *doublyListNode
tail *doublyListNode
}
// 删除尾结点
func (dl *doublyList) removeTail() {
pre := dl.tail.prev.prev
pre.next = dl.tail
dl.tail.prev = pre
}
// 链表是否为空
func (dl *doublyList) isEmpty() bool {
return dl.head.next == dl.tail
}
// 双向链表节点
type doublyListNode struct {
key int
value int
frequency int // 应用次数
prev *doublyListNode
next *doublyListNode
}
// 在某一个节点之前插入一个节点
func addBefore(currNode *doublyListNode, newNode *doublyListNode) {
pre := currNode.prev
pre.next = newNode
newNode.next = currNode
currNode.prev = newNode
newNode.prev = pre
}
// LFUCache 具体的缓存
type LFUCache struct {
recent map[int]*doublyListNode // frequency 到应用次数为 frequency 的节点中，最近应用的一个的映射
count map[int]int // frequency 到对应频率的节点数量的映射
cache map[int]*doublyListNode // key到节点的映射
list *doublyList // 双向链表，保护缓存的应用次数（优先）和上一次应用工夫
capacity int // 容量
}
func removeNode(node *doublyListNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
// Constructor 构建缓存容器
func Constructor(capacity int) LFUCache {
return LFUCache{
recent: make(map[int]*doublyListNode),
count: make(map[int]int),
cache: make(map[int]*doublyListNode),
list: newDoublyList(),
capacity: capacity,
}
}
func newDoublyList() *doublyList {
headNode := &doublyListNode{}
tailNode := &doublyListNode{}
headNode.next = tailNode
tailNode.prev = headNode
return &doublyList{
head: headNode,
tail: tailNode,
}
}
func (lfu *LFUCache) Get(key int) int {
if lfu.capacity == 0 {
return -1
}
node, ok := lfu.cache[key]
if !ok { // key不存在
return -1
}
// key已存在
next := node.next
if lfu.count[node.frequency+1] > 0 {
// 存在其余应用次数为n+1的缓存，将指定缓存挪动到所有应用次数为n+1的节点之前
removeNode(node)
addBefore(lfu.recent[node.frequency+1], node)
} else if lfu.count[node.frequency] > 1 && lfu.recent[node.frequency] != node {
// 不存在其余应用次数为n+1的缓存，但存在其余应用次数为n的缓存，且以后节点不是最近的节点
// 将指定缓存挪动到所有应用次数为n的节点之前
removeNode(node)
addBefore(lfu.recent[node.frequency], node)
}
// 更新recent
lfu.recent[node.frequency+1] = node
if lfu.count[node.frequency] <= 1 { // 不存在其余freq = n的节点，recent置空
lfu.recent[node.frequency] = nil
} else if lfu.recent[node.frequency] == node { // 存在其余freq = n的节点，且recent = node，将recent向后挪动一位
lfu.recent[node.frequency] = next
}
// 更新应用次数对应的节点数
lfu.count[node.frequency+1]++
lfu.count[node.frequency]--
// 更新缓存应用次数
node.frequency++
return node.value
}
// Put 新建缓存
func (lfu *LFUCache) Put(key int, value int) {
if lfu.capacity == 0 {
return
}
node, ok := lfu.cache[key]
if ok { // key已存在
lfu.Get(key)
node.value = value
return
}
// key不存在
if len(lfu.cache) >= lfu.capacity { // 缓存已满，删除最初一个节点，相应更新cache、count、recent（条件）
tailNode := lfu.list.tail.prev
lfu.list.removeTail()
if lfu.count[tailNode.frequency] <= 1 {
lfu.recent[tailNode.frequency] = nil
}
lfu.count[tailNode.frequency]--
delete(lfu.cache, tailNode.key)
}
newNode := &doublyListNode{
key: key,
value: value,
frequency: 1,
}
// 插入新的缓存节点
if lfu.count[1] > 0 {
addBefore(lfu.recent[1], newNode)
} else {
addBefore(lfu.list.tail, newNode)
}
// 更新recent、count、cache
lfu.recent[1] = newNode
lfu.count[1]++
lfu.cache[key] = newNode
}
- 作者微信：foolish_is_me
- 作者邮箱：big_ox@163.com
发表回复