V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
qawsed2019
V2EX  ›  推广

快下班了, v 站大佬们不如一起来学习,讨论题目吧—>[LFU 缓存]!

  •  
  •   qawsed2019 · 2019-05-27 18:26:08 +08:00 · 1419 次点击
    这是一个创建于 1992 天前的主题,其中的信息可能已经有所发展或是发生改变。

    描述

    LFU 是一个著名的缓存算法 对于容量为 k 的缓存,如果缓存已满,并且需要逐出其中的密钥,则最少使用的密钥将被踢出。 实现 LFU 中的 setget

    样例

    输入:
    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 的操作?能不能言简意赅说一下?

    2 条回复    2019-05-27 23:04:02 +08:00
    swulling
        1
    swulling  
       2019-05-27 18:28:12 +08:00 via iPhone
    get 肯定算啊,不算缓存的意义就没有了
    shawndev
        2
    shawndev  
       2019-05-27 23:04:02 +08:00
    如果缓存命中都不能说明 frequency 增加,那还要什么 LFU 淘汰算法
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3380 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 10:37 · PVG 18:37 · LAX 02:37 · JFK 05:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.