- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
请你为最不经常使用(LFU)缓存算法设计并实现数据结构。
实现 LFUCache 类:
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键 key 存在于缓存中,则获取键的值,否则返回 -1 。
void put(int key, int value) - 如果键 key 已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量 capacity 时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该去除 最近最久未使用 的键。
为了确定最不常使用的键,可以为缓存中的每个键维护一个使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时,它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作,使用计数器的值将会递增。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例:
输入:
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释:
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序(最左边的元素是最近的)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 去除键 2 ,因为 cnt(2)=1 ,使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // 返回 -1(未找到)
lfu.get(3); // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // 去除键 1 ,1 和 3 的 cnt 相同,但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // 返回 -1(未找到)
lfu.get(3); // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
提示:
0 <= capacity <= 104
0 <= key <= 105
0 <= value <= 109
最多调用 2 * 105 次 get 和 put 方法
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lfu-cache
(1)数据结构设计
思路参考算法题就像搭乐高:手把手带你拆解 LFU 算法。
//思路1————数据结构设计
class LFUCache {
//LFU 缓存的最大容量
int capacity;
//LFU 缓存最小的频次
int minFreq;
//key 到 value 的映射
HashMap<Integer, Integer> keyToValue;
//key 到 freq 的映射
HashMap<Integer, Integer> keyToFreq;
//freq 到 key 列表的映射
HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
public LFUCache(int capacity) {
//初始化
this.capacity = capacity;
this.minFreq = 0;
this.keyToValue = new HashMap<>();
this.keyToFreq = new HashMap<>();
this.freqToKeys = new HashMap<>();
}
public int get(int key) {
if (keyToValue.containsKey(key) == false) {
//未找到该 key
return -1;
} else {
//找到该 key,则其频率加一
increaseFreq(key);
return keyToValue.get(key);
}
}
public void put(int key, int value) {
if (this.capacity <= 0) {
return;
}
if (keyToValue.containsKey(key)) {
/*若 key 已存在,修改其对应的 value 即可*/
keyToValue.put(key, value);
//key 的频率加一
increaseFreq(key);
return;
}
/*若 key 不存在,则需要将其插入*/
if (this.capacity <= keyToValue.size()) {
//LFU 缓存容量已满,则需要淘汰一个 freq 最小的 key
removeMinFreqKey();
}
//将 (key, value) 加入到 keyToValue 中
keyToValue.put(key, value);
//将 (key, 1) 加入到 keyToFreq 中
keyToFreq.put(key, 1);
//更新 freqToKeys
freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
freqToKeys.get(1).add(key);
//插入新 key 后 minFreq 肯定是 1
this.minFreq = 1;
}
//key的频率加一
public void increaseFreq(int key) {
//更新 keyToFreq
int freq = keyToFreq.get(key);
keyToFreq.put(key, freq + 1);
//将 key 从 freq 对应的列表中删除
freqToKeys.get(freq).remove(key);
//将 key 加入 freq + 1 对应的列表中
freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
freqToKeys.get(freq + 1).add(key);
//如果 freq 对应的列表为空,则移除这个 freq
if (freqToKeys.get(freq).isEmpty()) {
freqToKeys.remove(freq);
//如果这个 freq 恰好是 minFreq,则更新 minFreq
if (freq == this.minFreq) {
this.minFreq++;
}
}
}
//淘汰一个 freq 最小的 key
public void removeMinFreqKey() {
//从 freqToKeys 中找到 freq = minFreq 的列表‘
LinkedHashSet<Integer> keysList = freqToKeys.get(this.minFreq);
//keysList 中最先加入的 key 就是应该被淘汰的 key
int removedKey = keysList.iterator().next();
keysList.remove(removedKey);
if (keysList.isEmpty()) {
//删除 removedKey 后,keysList 为空
freqToKeys.remove(this.minFreq);
/*
此处不需要更新 minFreq,具体原因如下:
removeMinFreqKey() 在 put() 中插入新 key 时可能会调用,而 put() 的代码中,
插入新 key 时一定会把 minFreq 更新成 1,所以此处无需更新 minFreq
*/
}
//删除 keyToValue 中的 removedKey
keyToValue.remove(removedKey);
//删除 keyToFreq 中的 removedKey
keyToFreq.remove(removedKey);
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
1.题目 请你为最不经常使用(LFU)缓存算法设计并实现数据结构。 实现 LFUCache 类: LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 in
我正在尝试设计一个缓存服务器,它将存储数据库查询的查询和结果键,从而减轻它的负载。 它可能是这样的: if Cache.isSet(query): return Cache.get(qu
最不常用 (LFU) 是一种用于管理计算机内存的缓存算法。这种方法的标准特征涉及系统跟踪一个 block 在内存中被引用的次数。当缓存已满并需要更多空间时,系统将清除引用频率最低的项目。 用 Java
LRU 和 LFU 缓存实现有什么区别? 我知道LRU可以使用LinkedHashMap来实现。但如何实现LFU缓存呢? 最佳答案 让我们考虑缓存容量为 3 的恒定缓存请求流,如下所示: A, B,
这个问题已经有答案了: What is the difference between LRU and LFU (4 个回答) 已关闭 7 年前。 我在一次采访中被问到这个问题,他首先问了 LRU 和
我在网上发现 LFU 是一种堆栈算法,但是当我问我的讲师他说它患有 belady 异常,但我已经尝试了很多例子,但没有找到任何证据来证明这一点,所以有人可以告诉我是否可以真的患上了吗?还是堆栈算法?如
C# 中是否有现成的 LFU 缓存? 最佳答案 Java 有大量的 LFU 缓存实现,应该很容易移植到 C#,例如:http://faq.javaranch.com/view?CachingStrat
我正在使用具有 3 个实例的 Redis 4,一个主实例和两个副本实例。 使用 allkeys-lfu 策略将主实例配置为具有最大内存限制。 我想知道我是否应该将我的读取查询也转发给主实例以使 LFU
性能测试,在编写代码后,单元测试及性能测试是重要的验收点,好的性能测试可以让我们提前发现程序中存在的问题。 测试用例 在Rust中,测试通常有两部分,一部分是文档测试,一部分是模块测试。 通常我们
我一直试图找到一个很好的案例,其中 LFU 比 LRU 更好,但我不确定。 我设法做的(但不确定这是否是一个很好的例子)是当您有一个容量为 3 的缓存并且缓存请求为 4(如 A B C D)但 C 和
我在我的 springboot 应用程序中使用了 redis。内存策略是 lfu 并且想查看热键的统计信息。 一种方法是连接到redis并运行./redis-cli --hotkeys 但最好监控前
准备面试时,我遇到了一些事情,这让我质疑我对大 O 常数时间算法的理解。 LeetCode 上的一个问题要求创建 LFU 缓存问题的解决方案。 有3种实现方法: 构造器 - 输入:int 容量 得到
是否可以从 Redis 数据库中检索所有 LFU key ?如果是,请提供示例命令行建议。 感谢一百万,穆格拉比 最佳答案 您可以使用 OBJECT IDLETIME 获取读取或写入操作未请求 key
我正在使用 Redis 并在配置中设置了一个 allkeys-lfu 以用于逐出。 然而,有一个 key 我想确保永远不会被驱逐,我可以手动设置该 key 的“保护”,以便它在任何情况下都不会被驱逐,
当 redis 通过 spring boot (spring-boot-starter-data-redis) 用作缓存技术时,我看到很少有像 TTL 这样的属性可以在 application.pro
我是一名优秀的程序员,十分优秀!