Java基础、中级、高级、架构面试资料

Go 语言实现 LFU 算法

业余杂谈 herman 3505浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog2,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog2,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领
腾讯云】1核2G5M轻量应用服务器50元首年,高性价比,助您轻松上云

LFU(Least Frequently Used ,最近最少使用算法)也是一种常见的缓存算法。

顾名思义,LFU算法的思想是:如果一个数据在最近一段时间很少被访问到,那么可以认为在将来它被访问的可能性也很小。因此,当空间满时,最小频率访问的数据最先被淘汰。

LFU 算法的描述:

设计一种缓存结构,该结构在构造时确定大小,假设大小为 K,并有两个功能:

  • set(key,value):将记录(key,value)插入该结构。当缓存满时,将访问频率最低的数据置换掉。
  • get(key):返回key对应的value值。

算法实现策略:考虑到 LFU 会淘汰访问频率最小的数据,我们需要一种合适的方法按大小顺序维护数据访问的频率。LFU 算法本质上可以看做是一个 top K 问题(K = 1),即选出频率最小的元素,因此我们很容易想到可以用二项堆来选择频率最小的元素,这样的实现比较高效。最终实现策略为小顶堆+哈希表。

LFU golang 实现
package problem0460

// LRU: Least Recently Used,缓存满的时候,删除缓存里最久未使用的数据,然后放入新元素
// LFU: Least Frequently Used,缓存满的时候,删除缓存里使用次数最少的元素,然后放入新元素,如果使用频率一样,删除缓存最久的元素

// 节点:包含key, value, frequent访问次数, pre前驱指针, next后继指针
type Node struct {
  key, value, frequent int
  pre, next            *Node
}

// 双向链表:包含head头指针, tail尾指针, size尺寸
type ListNode struct {
  head, tail *Node
  size       int
}

// 双向链表辅助函数:添加一个节点到头节点后
func (this *ListNode) addNode(node *Node) {
  head := this.head
  node.next = head.next
  node.next.pre = node
  node.pre = head
  head.next = node
}

// 双向链表辅助函数,删除一个节点
func (this *ListNode) removeNode(node *Node) {
  node.pre.next = node.next
  node.next.pre = node.pre
}

// LFUCache结构:包含capacity容量, size当前容量, minFrequent当前最少访问频次, cacheMap缓存哈希表, frequentMap频次哈希表
// minFrequent当前最少访问频次:
// 1. 插入一个新节点时,之前肯定没访问过,minFrequent = 1
// 2. put和get时,如果移除后双向链表节点个数为0,且恰好是最小访问链表, minFrequent++
type LFUCache struct {
  capacity, size, minFrequent int
  cacheMap                    map[int]*Node
  frequentMap                 map[int]*ListNode
}

func Constructor(capacity int) LFUCache {
  return LFUCache{
    capacity:    capacity,
    size:        0,
    minFrequent: 0,
    cacheMap:    make(map[int]*Node),
    frequentMap: make(map[int]*ListNode),
  }
}

// LFUCache辅助函数:将节点从对应的频次双向链表中删除
func (this *LFUCache) remove(node *Node) {
  this.frequentMap[node.frequent].removeNode(node)
  this.frequentMap[node.frequent].size--
}

// LFUCache辅助函数:将节点添加进对应的频次双向链表,没有则创建
func (this *LFUCache) add(node *Node) {
  if listNode, exist := this.frequentMap[node.frequent]; exist {
    listNode.addNode(node)
    listNode.size++
  } else {
    listNode = &ListNode{&Node{}, &Node{}, 0}
    listNode.head.next = listNode.tail
    listNode.tail.pre = listNode.head
    listNode.addNode(node)
    listNode.size++
    this.frequentMap[node.frequent] = listNode
  }
}

// LFUCache辅助函数:移除一个key
func (this *LFUCache) evictNode() {
  listNode := this.frequentMap[this.minFrequent]
  delete(this.cacheMap, listNode.tail.pre.key)
  listNode.removeNode(listNode.tail.pre)
  listNode.size--
}

// LFUCache辅助函数:获取一个key和修改一个key都会增加对应key的访问频次,可以独立为一个方法,完成如下任务:
// 1. 将对应node从频次列表中移出
// 2. 维护minFrequent
// 3. 该节点访问频次++,移动进下一个访问频次链表
func (this *LFUCache) triggerVisit(node *Node) {
  this.remove(node)
  if node.frequent == this.minFrequent && this.frequentMap[node.frequent].size == 0 {
    this.minFrequent++
  }
  node.frequent++
  this.add(node)
}

func (this *LFUCache) Get(key int) int {
  if node, exist := this.cacheMap[key]; exist {
    this.triggerVisit(node)
    return node.value
  }
  return -1
}

func (this *LFUCache) Put(key int, value int) {
  if this.capacity == 0 {
    return
  }
  if node, exist := this.cacheMap[key]; exist {
    this.triggerVisit(node)
    this.cacheMap[key].value = value
  } else {
    newNode := &Node{key, value, 1, nil, nil}
    if this.size < this.capacity {
      this.add(newNode)
      this.size++
      this.minFrequent = 1
    } else {
      this.evictNode()
      this.add(newNode)
      this.minFrequent = 1
    }
    this.cacheMap[key] = newNode
  }
}

代码加注释,相信大家都能一目了然!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号:xttblog2。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » Go 语言实现 LFU 算法