go语言实现LRU队列 golang实现队列

Go语言list（列表）

2021-11-10

列表是一种非连续的存储容器，有多个节点组成，节点通过一些变量记录彼此之间的关系

单链表和双链表就是列表的两种方法。

原理：A、B、C三个人，B懂A的电话，C懂B的电话只是单方知道号码，这样就形成了一个单链表结构。

如果C把自己的号码给B，B把自己的号码给A，因为是双方都知道对方的号码，这样就形成了一个双链表结构

如果B换号码了，他需要通知AC，把自己的号码删了，这个过程就是列表的删除操作。

在Go语言中，列表使用 container/list 包来实现，内部的实现原理是双链表，列表能够高效地进行任意位置的元素插入和删除操作。

列表初始化的两种办法

列表没有给出具体的元素类型的限制，所以列表的元素可以是任意类型的，

例如给列表中放入了一个 interface{} 类型的值，取出值后，如果要将 interface{} 转换为其他类型将会发生宕机。

双链表支持从队列前方或后方插入元素，分别对应的方法是 PushFront 和 PushBack。

列表插入函数的返回值会提供一个 *list.Element 结构，这个结构记录着列表元素的值以及与其他节点之间的关系等信息，从列表中删除元素时，需要用到这个结构进行快速删除。

遍历完也能看到最后的结果

学习地址：

相关问答

Q1: go语言循环队列的实现

队列的概念在 顺序队列 中，而使用循环队列的目的主要是规避假溢出造成的空间浪费，在使用循环队列处理假溢出时，主要有三种解决方案

本文提供后两种解决方案。

顺序队和循环队列是一种特殊的线性表，与顺序栈类似，都是使用一组地址连续的存储单元依次存放自队头到队尾的数据元素，同时附设队头(front)和队尾(rear)两个指针，但我们要明白一点，这个指针并不是指针变量，而是用来表示数组当中元素下标的位置。

本文使用切片来完成的循环队列，由于一开始使用三个参数的make关键字创建切片，在输出的结果中不包含nil值(看起来很舒服)，而且在验证的过程中发现使用append()函数时切片内置的cap会发生变化，在消除了种种障碍后得到了一个四不像的循环队列，即设置的指针是顺序队列的指针，但实际上进行的操作是顺序队列的操作。最后是对make()函数和append()函数的一些使用体验和小结，队列的应用放在链队好了。

官方描述(片段)

即切片是一个抽象层，底层是对数组的引用。

当我们使用

构建出来的切片的每个位置的值都被赋为interface类型的初始值nil，但是nil值也是有大小的。

而使用

来进行初始化时，虽然生成的切片中不包含nil值，但是无法通过设置的指针变量来完成入队和出队的操作，只能使用append()函数来进行操作

在go语言中，切片是一片连续的内存空间加上长度与容量的标识，比数组更为常用。使用 append 关键字向切片中追加元素也是常见的切片操作

正是基于此，在使用go语言完成循环队列时，首先想到的就是使用make(type, len, cap)关键字方式完成切片初始化，然后使用append()函数来操作该切片，但这一方式出现了很多问题。在使用append()函数时，切片的cap可能会发生变化，用不好就会发生扩容或收缩。最终造成的结果是一个四不像的结果，入队和出队操作变得与指针变量无关，失去了作为循环队列的意义，用在顺序队列还算合适。

参考博客：

Go语言中的Nil

Golang之nil

Go 语言设计与实现

Q2: Go语言——goroutine并发模型

参考：

Goroutine并发调度模型深度解析手撸一个协程池

Golang 的 goroutine 是如何实现的？

Golang - 调度剖析【第二部分】

OS线程初始栈为2MB。Go语言中，每个goroutine采用动态扩容方式，初始2KB，按需增长，最大1G。此外GC会收缩栈空间。

BTW，增长扩容都是有代价的，需要copy数据到新的stack，所以初始2KB可能有些性能问题。

更多关于stack的内容，可以参见大佬的文章。 聊一聊goroutine stack

用户线程的调度以及生命周期管理都是用户层面，Go语言自己实现的，不借助OS系统调用，减少系统资源消耗。

Go语言采用两级线程模型，即用户线程与内核线程KSE（kernel scheduling entity）是M:N的。最终goroutine还是会交给OS线程执行，但是需要一个中介，提供上下文。这就是G-M-P模型

Go调度器有两个不同的运行队列：

go1.10\src\runtime\runtime2.go

Go调度器根据事件进行上下文切换。

调度的目的就是防止M堵塞，空闲，系统进程切换。

详见 Golang - 调度剖析【第二部分】

Linux可以通过epoll实现网络调用，统称网络轮询器N（Net Poller）。

文件IO操作

上面都是防止M堵塞，任务窃取是防止M空闲

每个M都有一个特殊的G，g0。用于执行调度，gc，栈管理等任务，所以g0的栈称为调度栈。g0的栈不会自动增长，不会被gc，来自os线程的栈。

go1.10\src\runtime\proc.go

G没办法自己运行，必须通过M运行

M通过通过调度，执行G

从M挂载P的runq中找到G，执行G

Q3: FIFO和LRU小结

 一:FIFO算法

     1.0,FIFO (First in First out) 先进先出(核心原则:最先进来的,最先淘汰); 其实在操作系统的设计理念中很多地方都是利用到了先进先出的思想就是因为这个原则简单切符合人们的惯性思维,具备公平性实现起来也简单,直接使用数据结构中的队列即可实现

     1.1,在FIFO 中应该支持这些操作: 一,get(key),如果Cache中存在该key,则返回对应的value值,否则返回 -1; 二,set(key,value),如果Cache中存在该key,则重置value值,如果不存在则将该key插入到Cache中,若Cache已满则淘汰最先进入Cache的数据

     1.2,那么利用什么数据结构来实现呢?有这一种思路, 利用一个双向链表保存数据,当来了新数据之后便添加到链表末尾,如果Cache存满数据,则把链表头部数据删除,然后把次年数据添加到链表末尾,在访问数据的时候,如果在Cache中存在该数据的话,则返回对应的value值,否则返回 -1,如果想提高访问效率,可以利用hashmap来保存每个key在链表中的位置(参考下面拓展)

     二:LRU算法

     1.0,LRU (Least recently used) 最近最久未使用调度,其核心思想是"如果数据最近被访问过,那么将来被访问的几率也更高"; 最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:

       1,新数据插入到链表头部

       2,每当缓存命中(即缓存数据被访问),则将数据移到链表头部;

       3,当链表满的时候,将链表尾部的数据丢弃

     1.1,LRU的优缺点 1.命中率,当存在热点数据时,LRU的效率很好,但偶发性的,周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重 2,实现相对简单 3,命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部

     2.0,LRU-K K代表最近使用的次数,因此LRU也可以认为是LRU-1,它主要是为了解决LRU算法"缓存污染"的问题,其核心思想是将"最近使用过1次"的判断标准扩展为"最近使用过K次"; 相比LRU要多维护一个队列,用于记录所有缓存数据被访问的历史,只有当数据的访问次数达到K次的时候,才将数据放入缓存.当需要淘汰数据时,LRU-k会淘汰第K次访问时间距离当前时间最大的数据.详细实现如下:

     2.1,一,数据第一次被访问,加入到访问历史列表; 二,如果数据在访问历史列表里后达到K次访问,则按照一定(FIFO, LRU)淘汰; 三,当访问历史队列中的数据访问次数达到k次后,将数据l索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序; 四,缓存数据队列中被再次访问后,重新排序; 五,需要淘汰数据时,淘汰缓存队列中排在末尾的数据(即:淘汰倒数第K次访问离现在最久的数据)

     2.2,LRU-K具有LRU的优点,同时能够避免LRU的缺点,实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,需要大量的数据访问才能将历史记录缓存或者清除掉

     2.3优缺,LRU-K降低了"缓存污染"带来的问题,命中率比LRU要高,但LRU-K队列是一个优先级队列,算法复杂度和代价相对LRU较高,并且LRU需要记录那些被访问过,但是没有达到K次也就是还没有放入缓存的对象,因此b内存消耗会比LRU要多,当然如果数据量很大的时候,内存消耗会比较可观

     3.0,Two queues (2Q) 算法类似于LRU-2,不同点在于2Q将LRU-2算法中的访问历史队列(历史队列,还没有缓存数据)改为一个FIFO缓存队列,即: 2Q算法有两个缓存队列,一个是FIFO队列,一个是LRU队列.

     3.1,当数据第一次访问时,2Q算法会将数据缓存在FIFO队列里面,当数据第二次被访问时,则将数据从FIFO队列移到LRU队列里面,两个队列各自按照自己的方法淘汰数据; 一,新访问的数据插入到FIFO队列, 二,如果数据在FIFO队列中一直没有被再次访问,则最终按照FOFO规则淘汰, 三,如果数据在FIFO队列中被再次访问,则将数据移到LRU队列头部, 四,如果数据在LRU队列再次被访问,则将数据移到LRU队列头部, 五,LRU队列淘汰末尾的数据

     3.2,可能会感觉FIFO队列比LRU队列短,但并不代表这是算法的要求,实际应用中两者比例没有硬性要求

     3.3,2Q算法命中率高于LRU,切需要两个队列,但两个队列本身都比较简单,代价是FIFO和LRU代价之和; 2Q算法和LRU-2算法命中率类似,内存消耗也比较接近,但对于最后的缓存数据来说,2Q减少一次从原始储存读取数据或者计算数据的操作

     4.0,Multi Queue (MQ) 算法根据访问频率将数据划分为多个队列,不同的队列具有不同的访问优先级,其核心思想是:优先缓存访问次数多的数据

     4.1,MQ算法将缓存划分为多个LRU队列,每个队列对应不同的访问优先级,访问优先级是根据访问次数计算出来的,详情: 一,新插入的数据放入Q0; 二,每个队列按照LRU管理数据; 三,当数据访问次数达到一定次数需要提升优先级时将数据从当前队列删除,加入到高一级的队列头部; 四,为了防止高优先级数据永远不被淘汰,每个队列淘汰数据时,将数据从缓存中删除,将数据加入Q-history头部; 五,需要淘汰数据时,从最低一级队列开始按照LRU淘汰,每个队列淘汰数据时,将数据从缓存中删除,将数据索引加入Q-history头部; 六,如果数据在Q-history中被重新访问,则重新计算其优先级,移到目标队列的头部; 七,Q-history按照LRU淘汰数据的索引

     4.2,MQ降低了"缓存污染"带来的问题,命中率比LRU高,但MQ需要维护多个队列,切需要维护每个数据的访问时间,复杂度比较高,并且MQ需要记录每个数据的访问时间,需要定时扫码所有队列,代价也比较高

     4.3,虽然MQ的队列看起来数量比较多,但由于所有队列之和受限于缓存容量的大小,因此这里多个队列长度之和和一个LRU队列是一样的,因此队列扫码性能接近

     小结: 命中率  LRU-2 MQ(2) 2Q LRU ; 复杂度 LRU-2 MQ(2) 2Q LRU ; 代价 LRU-2 MQ(2) 2Q LRU ; 需要注意的是,命中率并不是越高越好,实际中应该根据业务需求和对数据的访问情况进行分析选择,LRU虽然看起来命中率低一些,切存在"缓存污染"的问题,但其简单切代价小,实际中反而应用更多

     拓展:基于 双链表的 LRU 实现: 一,传统意义的LRU算法是每一个Cache对象设置一个定时器,每次Cache命中则给定时器 +1,而Cache用完需要淘汰旧内容,放置新内容时就查看所有的计时器,并将使用的内容替换掉; 其弊端很明显,如果Cache的数量少,问题不大,但如果Cache的空间过大,达到10W或者100W以上,一旦需要淘汰,则需要遍历所有计时器,其性能与资源消耗巨大,效率也就非常的慢了; 二,双链表原理,将Cache的所有位置都用双链表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入Cache直接加到链表头中,这样在多次进行Cache操作后,最近被命中的就会被向链表头方向移动,而没有命中的则向链表后部移动,链表尾则表示最近最少命中的Cache,当需要替换内容时我们只需要淘汰链表最后的部分即可!

如果错误或者建议,欢迎下方留言,谢谢!

Q4: Go语言设计与实现（上）

基本设计思路：

类型转换、类型断言、动态派发。iface，eface。

反射对象具有的方法：

编译优化：

内部实现：

实现 Context 接口有以下几个类型（空实现就忽略了）：

互斥锁的控制逻辑：

设计思路：

（以上为写被读阻塞，下面是读被写阻塞）

总结，读写锁的设计还是非常巧妙的：

设计思路：

WaitGroup 有三个暴露的函数:

部件：

设计思路：

结构：

Once 只暴露了一个方法：

实现：

三个关键点：

细节：

让多协程任务的开始执行时间可控（按顺序或归一）。（Context 是控制结束时间）

设计思路： 通过一个锁和内置的 notifyList 队列实现，Wait() 会生成票据，并将等待协程信息加入链表中，等待控制协程中发送信号通知一个（Signal()）或所有（Boardcast()）等待者（内部实现是通过票据通知的）来控制协程解除阻塞。

暴露四个函数：

实现细节：

部件：

包： golang.org/x/sync/errgroup

作用：开启 func() error 函数签名的协程，在同 Group 下协程并发执行过程并收集首次 err 错误。通过 Context 的传入，还可以控制在首次 err 出现时就终止组内各协程。

设计思路：

结构：

暴露的方法：

实现细节：

注意问题：

包： "golang.org/x/sync/semaphore"

作用：排队借资源（如钱，有借有还）的一种场景。此包相当于对底层信号量的一种暴露。

设计思路：有一定数量的资源 Weight，每一个 waiter 携带一个 channel 和要借的数量 n。通过队列排队执行借贷。

结构：

暴露方法：

细节：

部件：

细节：

包： "golang.org/x/sync/singleflight"

作用：防击穿。瞬时的相同请求只调用一次，response 被所有相同请求共享。

设计思路：按请求的 key 分组（一个 *call 是一个组，用 map 映射存储组），每个组只进行一次访问，组内每个协程会获得对应结果的一个拷贝。

结构：

逻辑：

细节：

部件：

如有错误，请批评指正。

关于go语言实现LRU队列和golang实现队列的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。