开发公司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]*listNode，key到节点的映射; 其中 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)}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85

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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

伪代码

  • 读缓存
    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}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147

  • 作者微信：foolish_is_me

  • 作者邮箱：

网站建设定制开发 软件系统开发定制 定制软件开发 软件开发定制 定制app开发 app开发定制 app开发定制公司 电商商城定制开发 定制小程序开发 定制开发小程序 客户管理系统开发定制 定制网站 定制开发 crm开发定制 开发公司 小程序开发定制 定制软件 收款定制开发 企业网站定制开发 定制化开发 android系统定制开发 定制小程序开发费用 定制设计 专注app软件定制开发 软件开发定制定制 知名网站建设定制 软件定制开发供应商 应用系统定制开发 软件系统定制开发 企业管理系统定制开发 系统定制开发