/*
@Time : 2022/2/25 12:13 下午
@Author : yuyunqing
@File : lfu_lru
@Software: GoLand
*/
package lfu_lru
import (
"log"
"time"
)
// LRU缓存机制（Least Recently Used）（看时间）
//
//在缓存满的时候，删除缓存里最久未使用的数据，然后再放入新元素；
//数据的访问时间很重要，访问时间距离现在越近，就越不容易被删除；
//就是喜新厌旧，淘汰在缓存里呆的时间最久的元素。在删除元素的时候，只看「时间」这一个维度。
//
//LFU缓存机制（Least Frequently Used）（看访问次数）
//
//在缓存满的时候，删除缓存里使用次数最少的元素，然后在缓存中放入新元素；
//数据的访问次数很重要，访问次数越多，就越不容易被删除，即淘汰访问次数最少的；
//核心思想：先考虑访问次数，在访问次数相同的情况下，再考虑缓存的时间。
//
//核心逻辑就是根据规则进行 key 的排序，然后从尾部删除key
//定义内存数据map
var Data map[string]*Node //主要为了方便实现和适配两种策略
var Max = 10 //存储数据上限 ，超出存储上限执行对应的策略删除数据
var lfu *LFU
//采用通用节点数据结构体
type Node struct {
key string
value string
count int
use_time time.Time // 其实不用，直接根据数据在链表位置判断即可
}
//定义lfu记录结构体 双向链表
type LFU_Node struct {
node *Node // 当前节点的数据指针
next *LFU_Node //下一个节点
pre *LFU_Node// 上一个节点
}
//记录双向链表起止点
type LFU struct {
count int
head *LFU_Node
tail *LFU_Node
count_list map[int]*LFU_Node //记录 固定次数区块的数据节点开始信息
}
func Init() {
lfu = CreateLFU()
Data = make(map[string]*Node )
}
func Set(key ,value string) {
if _,ok:= Data[key] ;ok {
log.Println("已存在key")
return
}
node := &Node{
key:key,
value: value,
count: 0,
use_time: time.Now(),
}
Data[key] = node
lfu.Add(node)
//同时检测是否超过最大值，同时删除
remove_node := lfu.remove()
if remove_node != nil {
delete(Data,remove_node.key)
}
}
func Get(key string) string {
if _,ok:= Data[key] ;ok {
log.Println(Data[key])
lfu.Update(Data[key])
}else {
log.Println("数据不存在异常")
}
return ""
}
func Loop() {
lfu.loop()
}
/*
@Time : 2022/2/25 2:49 下午
@Author : yuyunqing
@File : LRU
@Software: GoLand
*/
package lfu_lru
import "log"
/**
* @Author yuyunqing
* @Description //TODO 创建一个LFU
* @Date 2:59 下午 2022/2/25
**/
func CreateLFU() *LFU {
//创建链表头尾信息
head := &LFU_Node{}
tail := &LFU_Node{}
head.next = tail
tail.pre = head
return &LFU{
count: 0,
head: head,
tail: tail,
count_list: make(map[int]*LFU_Node),
}
}
/**
* @Author yuyunqing
* @Description //TODO 构造一个LFU 节点
* @Date 3:02 下午 2022/2/25
**/
func createLFUNode(node *Node) *LFU_Node {
return &LFU_Node{
node: node,
}
}
/**
* @Author yuyunqing
* @Description //TODO 写入节点
* @Date 3:00 下午 2022/2/25
**/
func (f *LFU) Add (node *Node) {
//新增数据默认访问次数为0
lfu_node := createLFUNode(node)
old := f.getLfuNodeByTime(0)
lfu_node.setLfuNode(old)
f.count_list[0] = lfu_node
f.count++
log.Println(f.count)
}
/**
* @Author yuyunqing
* @Description //TODO 新增修改时 ，根据访问次数获取 区块起始节点
* @Date 3:12 下午 2022/2/25
**/
func (f *LFU ) getLfuNodeByTime(count int) *LFU_Node {
start := f.tail
if _,ok := f.count_list[count] ;ok {
//获取访问次数为0的数据区块开头指针
start = f.count_list[count]
}else {
//找到一个比当前count 小的最大的key 简单来说 ， 如果count =4 [1,5,6,3] 中找到3
min_key := -1
for i, _ := range f.count_list {
if i > min_key && min_key < count {
min_key = i
}
}
//当数据不为默认值时 标识找到了 ,否则即为当前值为最小key
if min_key != -1 {
start = f.count_list[min_key]
}
}
return start
}
/**
* @Author yuyunqing
* @Description //TODO 将当前的节点插入旧节点前面
* @Date 3:28 下午 2022/2/25
**/
func (fn *LFU_Node)setLfuNode(old *LFU_Node) {
//插入逻辑
//1当前节点的前置指针，指向旧节点的前置
//旧节点的前置指针，指向当前节点
fn.pre = old.pre
old.pre = fn
//2当前节点的后置指针，指向旧节点
fn.next = old
//3当前节点的前置节点 的 后置指针指向当前节点
fn.pre.next = fn
// 0 : before <- old
// 0 : before -> old
// 当 new 加入的时候
// 1 ： before <- new <- old
// 1 ： before -> old
// 2 ： before <- new <- old
// 2 ： before(->old) new -> old
// 3 ： before <- new <- old
// 3 ： before -> new -> old
}
/**
* @Author yuyunqing
* @Description //TODO 用户访问后更新key权重
* @Date 3:43 下午 2022/2/25
**/
func (f *LFU) Update( node *Node) {
old_lfu_node := f.getLufNodeByNode(node)
node.count++
//新建一个节点，并删除原始节点
lfu_node := createLFUNode(node)
//找到位置插入新节点
old := f.getLfuNodeByTime(node.count)
lfu_node.setLfuNode(old)
f.count_list[node.count] = lfu_node
//删除老节点
f.delete(old_lfu_node ,node.count -1)
}
/**
* @Author yuyunqing
* @Description //TODO 根据key 和 访问次数获取 lfu节点
* @Date 3:48 下午 2022/2/25
**/
func (f *LFU)getLufNodeByNode(node *Node) *LFU_Node {
start := f.head
if _,ok := f.count_list[node.count] ;ok{
start = f.count_list[node.count]
}else{
return nil
}
for start.node.key != node.key {
start = start.next
if start.next == nil {
return nil
}
}
return start
}
/**
* @Author yuyunqing
* @Description //TODO 删除节点
* @Date 4:44 下午 2022/2/25
**/
func (f *LFU) delete(fn *LFU_Node , count int) {
if fn == nil {
log.Println("删除节点失败，未获取到可删除节点")
return
}
//从环中删除。
//当前节点前置的后置指针，指向当前节点的后置
//当前节点后置的前置指针，指向当前节点的前置
fn.next.pre = fn.pre
fn.pre.next = fn.next
//判断
if _,ok := f.count_list[count] ;ok{
start := f.count_list[count]
// 如果 当前节点不是 count_list中区块的头节点不操作
if start.node.key == fn.node.key {
//如果下一个节点依旧是对应次数区块
if fn.next.node != nil && fn.next.node.count == count {
f.count_list[count] = fn.next
}else{
delete(f.count_list, count)
}
}
}else{
log.Println("删除节点失败，删除时未发现原始节点count_list区块")
return
}
}
/**
* @Author yuyunqing
* @Description //TODO 从尾部弹出，过期key
* @Date 9:30 上午 2022/2/28
**/
func (f *LFU) remove() *Node {
if f.count > Max {
lfu_node := f.tail.pre
f.tail.pre = lfu_node.pre
lfu_node.pre.next = f.tail
//如果 访问次数列表中的 区块头对应了当前节点，则删除
if f.count_list[lfu_node.node.count].node.key == lfu_node.node.key {
delete(f.count_list,lfu_node.node.count )
}
log.Println("超过最大限制删除节点:" ,lfu_node.node.key)
f.count --
return lfu_node.node
}else {
return nil
}
}
func (f *LFU) loop() {
log.Println("循环查看 -----开始")
start := f.head.next
for start.next.next != nil {
log.Println(start.node.key , start.node.value,start.node.count)
start =start.next
}
log.Println(start.node.key , start.node.value,start.node.count)
log.Println("循环查看 -----结束")
}
package main
import "golangany/lfu_lru"
func main() {
lfu_lru.Init()
lfu_lru.Set("zhangsan1","1")
lfu_lru.Set("zhangsan2","2")
lfu_lru.Set("zhangsan3","3")
lfu_lru.Set("zhangsan4","4")
lfu_lru.Set("zhangsan5","1")
lfu_lru.Set("zhangsan6","2")
lfu_lru.Set("zhangsan7","3")
lfu_lru.Set("zhangsan8","4")
lfu_lru.Set("zhangsan9","1")
lfu_lru.Set("zhangsan10","2")
lfu_lru.Loop()
lfu_lru.Get("zhangsan3")
lfu_lru.Loop()
lfu_lru.Get("zhangsan3")
lfu_lru.Get("zhangsan4")
lfu_lru.Get("zhangsan4")
lfu_lru.Loop()
lfu_lru.Set("zhangsan11","2")
}
2022/02/28 10:24:43 1
2022/02/28 10:24:43 2
2022/02/28 10:24:43 3
2022/02/28 10:24:43 4
2022/02/28 10:24:43 5
2022/02/28 10:24:43 6
2022/02/28 10:24:43 7
2022/02/28 10:24:43 8
2022/02/28 10:24:43 9
2022/02/28 10:24:43 10
2022/02/28 10:24:43 循环查看 -----开始
2022/02/28 10:24:43 zhangsan10 2 0
2022/02/28 10:24:43 zhangsan9 1 0
2022/02/28 10:24:43 zhangsan8 4 0
2022/02/28 10:24:43 zhangsan7 3 0
2022/02/28 10:24:43 zhangsan6 2 0
2022/02/28 10:24:43 zhangsan5 1 0
2022/02/28 10:24:43 zhangsan4 4 0
2022/02/28 10:24:43 zhangsan3 3 0
2022/02/28 10:24:43 zhangsan2 2 0
2022/02/28 10:24:43 zhangsan1 1 0
2022/02/28 10:24:43 循环查看 -----结束
2022/02/28 10:24:43 &{zhangsan3 3 0 {13870852084508947200 262534 0x117e180}}
2022/02/28 10:24:43 循环查看 -----开始
2022/02/28 10:24:43 zhangsan3 3 1
2022/02/28 10:24:43 zhangsan10 2 0
2022/02/28 10:24:43 zhangsan9 1 0
2022/02/28 10:24:43 zhangsan8 4 0
2022/02/28 10:24:43 zhangsan7 3 0
2022/02/28 10:24:43 zhangsan6 2 0
2022/02/28 10:24:43 zhangsan5 1 0
2022/02/28 10:24:43 zhangsan4 4 0
2022/02/28 10:24:43 zhangsan2 2 0
2022/02/28 10:24:43 zhangsan1 1 0
2022/02/28 10:24:43 循环查看 -----结束
2022/02/28 10:24:43 &{zhangsan3 3 1 {13870852084508947200 262534 0x117e180}}
2022/02/28 10:24:43 &{zhangsan4 4 0 {13870852084508949200 265378 0x117e180}}
2022/02/28 10:24:43 &{zhangsan4 4 1 {13870852084508949200 265378 0x117e180}}
2022/02/28 10:24:43 循环查看 -----开始
2022/02/28 10:24:43 zhangsan4 4 2
2022/02/28 10:24:43 zhangsan3 3 2
2022/02/28 10:24:43 zhangsan10 2 0
2022/02/28 10:24:43 zhangsan9 1 0
2022/02/28 10:24:43 zhangsan8 4 0
2022/02/28 10:24:43 zhangsan7 3 0
2022/02/28 10:24:43 zhangsan6 2 0
2022/02/28 10:24:43 zhangsan5 1 0
2022/02/28 10:24:43 zhangsan2 2 0
2022/02/28 10:24:43 zhangsan1 1 0
2022/02/28 10:24:43 循环查看 -----结束
2022/02/28 10:24:43 11
2022/02/28 10:24:43 超过最大限制删除节点: zhangsan1
