Golang实现LFU缓存
既然上一篇写了LRU，那这一篇我们就来搞一下LFU吧。LFU，Least Frequently Used，最近最少使用，其核心思想是，“如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小”。本文基于 LeetCode 460. LFU 缓存 进行，解法不是最优，但是实现了Get和Put操作的时间复杂度均为O(1)。这里我们使用一个HashMap实现Get操作的O...
既然上一篇写了LRU，那这一篇我们就来搞一下LFU吧。LFU，Least Frequently Used，最近最少使用，其核心思想是，“如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小”。本文基于 LeetCode 460. LFU 缓存 进行，解法不是最优，但是实现了Get和Put操作的时间复杂度均为O(1)。这里我们使用一个HashMap实现Get操作的O...
LRU，Least Recently Used的缩写，即“最近最少使用”，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。这里，我们基于 LeetCode 146. LRU 缓存 ，使用Golang实现，并使其Get、Put操作的时间复杂度均为O(1)。思路很简单，使用HashMap保存Cache，保证其Get的复杂度为O(1)，使用一个双向链表，保证Put操作维护使用顺序...
最近开始学习Raft算法，就简单记录一下吧。(本文及后续相关文章的实现基于 MIT 6.824 Lab 2: Raft 2022 进行。)背景知识复制状态机一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。图 1 ：复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令...
最近学校数据结构课程布置了一个作业，我觉得很有意思，这里记录一下题目布线问题：印刷电路板将布线区域划分为n×m个方格阵列。布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案要求：布线时电路只能沿直线或直角布线。已布线方格做上封闭标记，其他线路布线不允许穿过封闭区域。（如下图所示）算法实现这里使用队列式分支限界法来解决首先，记录起点步数为0，起点的上下左右中，可达的节点步数为1，并将...