LFU 是一个著名的缓存算法
对于容量为 k 的缓存,如果缓存已满,并且需要逐出其中的密钥,则最少使用的密钥将被踢出。
实现 LFU 中的 set
和 get
输入:
LFUCache(3)
set(2,2)
set(1,1)
get(2)
get(1)
get(2)
set(3,3)
set(4,4)
get(3)
get(2)
get(1)
get(4)
输出:
2
1
2
-1
2
1
4
解题思路是这个,想说 get 计不计算一次增加 frequency 的操作?能不能言简意赅说一下?
1
swulling 2019-05-27 18:28:12 +08:00 via iPhone
get 肯定算啊,不算缓存的意义就没有了
|
2
shawndev 2019-05-27 23:04:02 +08:00
如果缓存命中都不能说明 frequency 增加,那还要什么 LFU 淘汰算法
|