乐趣区

关于golang:LRU和LFU-算法页面置换算法

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 是淘汰最长工夫没有被应用的页面

性能

  1. 缓存容量 capacity 为正整数,缓存的 key、value 均为 int 类型
  2. 读缓存func get(key int) int

    • key 已存在,返回对应 value
    • key 不存在,返回 -1
  3. 写缓存 func put(key int, value int):

    • key 已存在,批改对应 value
    • key 不存在,写入该组缓存,若写入前缓存容量已达下限,则应淘汰最久未应用的缓存(强调:读、写缓存均视为应用)

数据结构

  • 应用双向链表保护缓存的上一次应用工夫:

    • 约定:链表正方向(从头部到尾部)节点依照应用工夫排序——越早应用(即久未应用)的节点,越凑近链表尾部
    • 保护:每应用一次缓存,就将该缓存对应的链表节点挪动到链表头部;缓存淘汰时,只须要删除尾部节点即可
  • 减少一个 map,记录 key链表节点 的映射关系; 解决如果只应用双向链表,每次判断 key 是否存在时,都要遍历链表
  1. cache:map[int]*listNodekey到节点的映射; 其中 listNode data:key, value
  2. list:*listNode,双向链表,保护缓存的上一次应用工夫
  3. capacity:int,链表容量

伪代码

  • 读缓存

    1. key 存在:

      • 在原链表中删除该缓存节点,从新插入到链表头部,
      • 返回对应的 value
    2. key 不存在:

      • 返回 -1
  • 写缓存(更新缓存)

    1. Key 存在:

      • 更新缓存节点的 value 值
      • 在原链表中删除该缓存节点,并把该从新插入到链表头部
    2. Key 不存在:

      1. 容量已达下限:

        • 在链表中删除尾部节点(记录该节点的 key)
        • 依据上一步中记录的 key,删除对应的映射关系
        • 依据输出参数结构新的节点:
        • 将新的节点插入链表头部
        • 新增 key 到新的节点的映射关系
      2. 容量未达下限:

        • 依据输出参数结构新的节点:
        • 将新的节点插入链表头部
        • 新增 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 (起码次)

性能

  1. 缓存容量 capacity、缓存的 key 和 value 均为自然数(能够为 0,代码中独自解决)
  2. 读缓存 func get(key int) int:(与 lru 雷同)

    • key 已存在,返回对应 value
    • key 不存在,返回 -1
  3. 写缓存 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                     // 容量
}

伪代码

  • 读缓存

    1. 存在:(记节点 frequency 为 n)

      • 若存在其余 frequency = n+ 1 的节点,则将节点挪动到所有 frequency = n+ 1 的节点的后面;
      • 否则,若存在其余 frequency = n 的节点,且以后节点不是最近节点,则将节点挪动到所有 frequency = n 的节点的后面;
      • 否则,不挪动节点(该状况下,节点就应该呆在它当初的地位)
      • 更新 recent
      • 更新 count
      • 将节点 frequency +1
      • 返回节点的 value
    2. 不存在:返回 -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
退出移动版