Go实现LRU算法

这篇具有很好参考价值的文章主要介绍了Go实现LRU算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LRU是什么?

  LRU是内存淘汰策略,LRU (Least recently used:最近最少使用)算法在缓存写满的时候,会根据所有数据的访问记录,淘汰掉未来被访问几率最低的数据。也就是说该算法认为,最近被访问过的数据,在将来被访问的几率最大。
那LRU使用什么实现的呢?双链表的话,那查询的时间复杂度不就是O(n)了,那应该怎么办,于是可以用双链表加Map的方式进行插入和查询,在插入的时候,把key,value 存到map中,那么这样查询的时候时间复杂读不就是O(n)了
假如现在我设定的内存就能存放5个数据块,现在进行插入

Go实现LRU算法,go 面试题,golang,算法,开发语言  下面一次性插入五个数据块,此时,如果再有元素想插入应该怎么办?
Go实现LRU算法,go 面试题,golang,算法,开发语言
  如果内存被读满,那么他就会淘汰链表的最后一个元素,如果读取链表中的元素,他就会加载到链表的头部

Go实现LRU算法,go 面试题,golang,算法,开发语言

代码的具体实现

代码和双链表的思想一样,只不过加入了一个hashmap文章来源地址https://www.toymoban.com/news/detail-824144.html

package main

import (
	"fmt"
)

// LruNode创建双链表的节点
type LruNode struct {
	next, prev *LruNode
	Value      any
	Key        string
	list       *LRU
}
type LRU struct {
	Length   uint
	maxBytes uint
	Cache    map[string]*LruNode
	root     LruNode
}

func NewLRU() *LRU {
	return new(LRU).Init()
}
func (l *LRU) Init() *LRU {
	l.root.next = &l.root
	l.maxBytes = 5
	l.root.prev = &l.root
	l.Cache = make(map[string]*LruNode)
	l.Length = 0
	return l
}

// FrontBack 前插
func (l *LRU) FrontBack(k string, v any) {
	if node, ok := l.Cache[k]; !ok {
		nodeNow := &LruNode{Value: v, Key: k}
		l.Cache[k] = nodeNow
		l.insert(nodeNow, &l.root)
		if l.Length+1 > l.maxBytes {
			delete(l.Cache, l.root.prev.Key)
			l.delete(l.root.prev)
		}
	} else {
		delete(l.Cache, k)
		nodeNow := &LruNode{Value: v, Key: k}
		l.Cache[k] = node
		l.insert(nodeNow, &l.root)
	}

}

// GetValue 查找k,v
func (l *LRU) GetValue(k string) (val any, ok bool) {
	if node, ok := l.Cache[k]; ok {
		l.delete(node)
		l.insert(node, &l.root)
		return node.Value, ok
	}
	return nil, ok
}
func (l *LRU) insert(node, root *LruNode) {
	node.prev = root
	node.next = root.next
	node.prev.next = node
	node.next.prev = node
	l.Length++
	node.list = l
}
func (l *LRU) delete(node *LruNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
	l.Length--
}

// PrintlnDList 打印双链表的所有元素
func (l *LRU) PrintlnDList1() {
	if l.Length == 0 {
	}
	prev := l.root.next
	index := 0
	for prev.Value != nil {
		fmt.Printf("下标index: %d 元素 Element: %d\n", index, prev.Value)
		prev = prev.next
		index++
	}
	return
}
func main() {
	a := NewLRU()
	a.FrontBack("1", 1)
	a.FrontBack("2", 2)
	a.FrontBack("3", 3)
	a.FrontBack("4", 4)
	a.FrontBack("5", 5)
	a.FrontBack("5", 5)
	a.FrontBack("6", 6)
	a.FrontBack("7", 7)
	a.GetValue("4")
	a.PrintlnDList1()
}

到了这里,关于Go实现LRU算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Golang:Go语言结构

    在我们开始学习 Go 编程语言的基础构建模块前,让我们先来了解 Go 语言最简单程序的结构。 Go 语言的基础组成有以下几个部分: 包声明 引入包 函数 变量 语句 表达式 注释 接下来让我们来看下简单的代码,该代码输出了\\\"Hello World!\\\": 让我们来看下以上程序的各个部分: 第一

    2024年02月10日
    浏览(59)
  • Go学习圣经:Go语言实现高并发CRUD业务开发

    现在 拿到offer超级难 ,甚至连面试电话,一个都搞不到。 尼恩的技术社群中(50+),很多小伙伴凭借 “左手云原生+右手大数据”的绝活,拿到了offer,并且是非常优质的offer, 据说年终奖都足足18个月 。 第二个案例就是:前段时间,一个2年小伙伴希望涨薪到18K, 尼恩把

    2024年02月11日
    浏览(53)
  • 掌握Go语言:探索Go语言递归函数的高级奥秘,优化性能、实现并发、解决算法难题(28)

    递归函数在Go语言中是一种强大的工具,能够解决许多复杂的问题。除了基本的递归用法外,Go语言还提供了一些高级用法,使得递归函数更加灵活和强大。本文将深入探讨Go语言递归函数的高级用法,包括尾递归优化、并发递归和记忆化递归等。 尾递归优化 尾递归是一种特

    2024年04月10日
    浏览(53)
  • Go 语言实现冒泡排序算法的简单示例

    以下是使用 Go 语言实现冒泡排序算法的简单示例: 在这个例子中, bubbleSort 函数接收一个整数切片,对切片中的元素进行冒泡排序。在 main 函数中,我们定义了一个示例数组,调用 bubbleSort 函数对其进行排序,并输出结果。 注意,冒泡排序算法的时间复杂度为 O(n^2),因此对

    2024年01月23日
    浏览(47)
  • 【Golang】三分钟让你快速了解Go语言&为什么我们需要Go语言?

    博主简介: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:数据结构、Go,Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: Go语言核心编程 近期目标: 写好专栏的每一篇文章 Go 语言从 2009 年 9 月 21 日开始作为谷歌公司 20% 兼职项目,即相关

    2023年04月21日
    浏览(62)
  • 【GoLang】MAC安装Go语言环境

    小试牛刀 首先安装VScode软件 或者pycharm mac安装brew软件  brew install go 报了一个错误 不提供这个支持  重新brew install go 之后又重新brew reinstall go 使用go version 可以看到go 的版本 使用go env  可以看到go安装后的配置 配置一个环境变量 vim ~/.zshrc,  

    2024年02月15日
    浏览(60)
  • Go语言(Golang)数据库编程

    要想连接到 SQL 数据库,首先需要加载目标数据库的驱动,驱动里面包含着于该数据库交互的逻辑。 sql.Open() 数据库驱动的名称 数据源名称 得到一个指向 sql.DB 这个 struct 的指针 sql.DB 是用来操作数据库的,它代表了0个或者多个底层连接的池,这些连接由sql 包来维护,sql 包会

    2024年02月03日
    浏览(93)
  • 【Golang】VScode配置Go语言环境

    安装VScode请参考我的上一篇博客:VScode安装_㫪548的博客-CSDN博客 接下来我们直接进入正题: Go语言(又称Golang)是一种开源的编程语言,由Google开发并于2009年首次发布。Go语言具有简洁、高效、可靠和易于阅读的特点,被设计用于解决大型项目的开发需求。它结合了静态类型

    2024年02月03日
    浏览(66)
  • Go 语言实现归并排序算法的简单示例(附上源码)

    以下是使用 Go 语言实现归并排序算法的简单示例: 在这个例子中, mergeSort 函数接收一个整数切片,使用递归的方式进行归并排序。 merge 函数用于合并两个已排序的切片。在 main 函数中,我们定义了一个示例数组,调用 mergeSort 函数对其进行排序,并输出结果。 归并排序算

    2024年01月21日
    浏览(45)
  • Golang(Go语言)IP地址转换函数

    String形式的IP地址和Int类型互转函数 代码 输出如下:  

    2024年02月05日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包