资讯专栏INFORMATION COLUMN

[LeetCode] 460. LFU Cache

yacheng / 3299人阅读

Problem

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example

LFUCache cache = new LFUCache( 2 / capacity / );

</>复制代码

  1. cache.put(1, 1);
  2. cache.put(2, 2);
  3. cache.get(1); // returns 1
  4. cache.put(3, 3); // evicts key 2
  5. cache.get(2); // returns -1 (not found)
  6. cache.get(3); // returns 3.
  7. cache.put(4, 4); // evicts key 1.
  8. cache.get(1); // returns -1 (not found)
  9. cache.get(3); // returns 3
  10. cache.get(4); // returns 4
Solution

</>复制代码

  1. class LFUCache {
  2. Map valMap;
  3. Map freqMap;
  4. Map> kSetMap;
  5. int size;
  6. int min;
  7. public LFUCache(int capacity) {
  8. min = 0;
  9. size = capacity;
  10. valMap = new HashMap<>();
  11. freqMap = new HashMap<>();
  12. kSetMap = new HashMap<>();
  13. kSetMap.put(1, new LinkedHashSet<>());
  14. }
  15. public int get(int key) {
  16. if (!valMap.containsKey(key)) return -1;
  17. //get frequency, then update freqMap, kSetMap, min
  18. int frequency = freqMap.get(key);
  19. freqMap.put(key, frequency+1);
  20. kSetMap.get(frequency).remove(key);
  21. if (!kSetMap.containsKey(frequency+1)) {
  22. kSetMap.put(frequency+1, new LinkedHashSet<>());
  23. }
  24. kSetMap.get(frequency+1).add(key);
  25. if (min == frequency && kSetMap.get(frequency).size() == 0) {
  26. min++;
  27. }
  28. return valMap.get(key);
  29. }
  30. public void put(int key, int value) {
  31. if (size <= 0) return;
  32. //when key is existed, just update valMap value,
  33. //and call get(key) to update freqmap, kSetMap and min
  34. if (valMap.containsKey(key)) {
  35. valMap.put(key, value);
  36. get(key);
  37. return;
  38. }
  39. //when reached capacity, remove min in all 3 maps
  40. if (valMap.size() == size) {
  41. int minKey = kSetMap.get(min).iterator().next();
  42. valMap.remove(minKey);
  43. freqMap.remove(minKey);
  44. kSetMap.get(min).remove(minKey);
  45. }
  46. //add the fresh k-v pair to all 3 maps
  47. valMap.put(key, value);
  48. freqMap.put(key, 1);
  49. kSetMap.get(1).add(key);
  50. }
  51. }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/77218.html

相关文章

  • LRU & LFU Cache

    摘要:首先要做到是,能想到的数据结构只有两三种,一个是,一个是,是,还有一个,是。不太可能,因为长度要而且不可变,题目也没说长度固定。可以做到和都是。因为还有函数,要可以,所以还需要一个数据结构来记录顺序,自然想到。 LRU Cache 题目链接:https://leetcode.com/problems... 这个题要求O(1)的复杂度。首先要做到get(key)是O(1),能想到的数据结...

    wenshi11019 评论0 收藏0
  • 论文《TinyLFU: A Highly Ecient Cache Admission Polic

    摘要:在静态的频率分布下,性能也落后于因为其不再为不在缓存中的数据维护任何频率数据。可以详见的准入淘汰策略是新增一个新的元素时,判断使用该元素替换一个旧元素,是否可以提升缓存命中率。 1. Introduction LFU的局限: LFU实现需要维护大而复杂的元数据(频次统计数据等) 大多数实际工作负载中,访问频率随着时间的推移而发生根本变化(这是外卖业务不适合朴素LFU的根本原因) 针...

    高璐 评论0 收藏0
  • 论文《TinyLFU: A Highly Ecient Cache Admission Polic

    摘要:在静态的频率分布下,性能也落后于因为其不再为不在缓存中的数据维护任何频率数据。可以详见的准入淘汰策略是新增一个新的元素时,判断使用该元素替换一个旧元素,是否可以提升缓存命中率。 1. Introduction LFU的局限: LFU实现需要维护大而复杂的元数据(频次统计数据等) 大多数实际工作负载中,访问频率随着时间的推移而发生根本变化(这是外卖业务不适合朴素LFU的根本原因) 针...

    RobinQu 评论0 收藏0
  • LFU

    摘要:如果每一个频率放在一个里面,每个也有头尾两个指针,指向相邻的。实际上相邻的可以由的第一可以由的最后一个唯一确认。也就是说,在的设计基础上。也就是说频率为的点,指向的下一个是频率为的点移除和一样。里存在的点,加到尾部的后一个。 只个代码由LRU改进得到。如果每一个频率放在一个LRU里面,每个LRU也有头尾两个指针,指向相邻的LRU。实际上相邻的LRU可以由frequency = t+1的...

    whidy 评论0 收藏0
  • 笔记|缓存

    摘要:缓存算法我是,我会统计每一个缓存数据的使用频率,我会把使用最少的缓存替换出缓存区。浏览器就是使用了我作为缓存算法。在缓存系统中找出最少最近的对象是需要较高的时空成本。再来一次机会的缓存算法,是对的优化。直到新的缓存对象被放入。 缓存 什么是缓存? showImg(https://segmentfault.com/img/bVusZg); 存贮数据(使用频繁的数据)的临时地方,因为取原始...

    elliott_hu 评论0 收藏0

发表评论

0条评论

yacheng

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<