题目描述：LFU缓存
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
一个项目的使用次数就是该项目被插入后对其调用 get 和 put 函数的次数之和。使用次数会在对应项目被移除后置为 0。
进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？
示例：
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
思路
首先知道LFU的定义，就是在一个容器中，当容量不够的时候，就把访问次数最少的删除掉。
最不经常使用算法（LFU）：这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法，最低访问数的条目首先被移除。这个方法并不经常使用，因为它无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责。
我们要用两个变量记录访问次数和时间戳，然后当访问次数一样时，时间戳早的先删，不一样就先删访问次数少的。可以用一个哈希表和一个Set来维护。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
struct Node
{
// 查询次数、时间戳、k、v
int cnt, time, key, value;
Node(int _cnt, int _time, int _key, int _value) : cnt(_cnt), time(_time), key(_key), value(_value) {}
bool operator<(const Node &rhs) const
{
return cnt == rhs.cnt ? time < rhs.time : cnt < rhs.cnt;
}
};
class LFUCache
{
// 缓存容量，时间戳
int capacity, time;
unordered_map<int, Node> key_table;
set<Node> S;
public:
LFUCache(int _capacity)
{
capacity = _capacity;
time = 0;
key_table.clear();
S.clear();
}
int get(int key)
{
if (capacity == 0)
return -1;
auto it = key_table.find(key);
// 如果哈希表中没有键 key，返回 -1
if (it == key_table.end())
return -1;
// 从哈希表中得到旧的缓存
Node cache = it->second;
// 从平衡二叉树中删除旧的缓存
S.erase(cache);
// 将旧缓存更新
cache.cnt += 1;
cache.time = ++time;
// 将新缓存重新放入哈希表和平衡二叉树中
S.insert(cache);
it->second = cache;
return cache.value;
}
void put(int key, int value)
{
if (capacity == 0)
return;
auto it = key_table.find(key);
if (it == key_table.end())
{
// 如果到达缓存容量上限
if (key_table.size() == capacity)
{
// 从哈希表和平衡二叉树中删除最近最少使用的缓存
key_table.erase(S.begin()->key);
S.erase(S.begin());
}
// 创建新的缓存
Node cache = Node(1, ++time, key, value);
// 将新缓存放入哈希表和平衡二叉树中
key_table.insert(make_pair(key, cache));
S.insert(cache);
}
else
{
// 这里和 get() 函数类似
Node cache = it->second;
S.erase(cache);
cache.cnt += 1;
cache.time = ++time;
cache.value = value;
S.insert(cache);
it->second = cache;
}
}
};
|
最后修改于 2020-04-06
本作品采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。