资讯专栏INFORMATION COLUMN

LRU & LFU Cache

wenshi11019 / 1763人阅读

摘要:首先要做到是,能想到的数据结构只有两三种,一个是,一个是,是,还有一个,是。不太可能,因为长度要而且不可变,题目也没说长度固定。可以做到和都是。因为还有函数,要可以,所以还需要一个数据结构来记录顺序,自然想到。

LRU Cache

题目链接:https://leetcode.com/problems...

这个题要求O(1)的复杂度。首先要做到get(key)是O(1),能想到的数据结构只有两三种,一个是HashMap,一个是List,key是index,还有一个Array[value], key是index。array不太可能,因为长度要initial而且不可变,题目也没说长度固定。list也不行,因为有put操作,list的insert操作是O(N)的。hashmap可以做到get和put都是O(1)。因为还有put函数,要可以remove least recently used cache,所以还需要一个数据结构来记录顺序,自然想到list。set以及delete操作在LinkedList里面都是O(1),就是要找到已存在的key这个操作在list是O(N),因为即要删除least recently的,也要加most recently的,所以是个double linked list。可以把map里面的value信息改成key在list里面该key对应的list node,然后在list里面存value信息。这其实也就是LinkedHashMap可以做的。

public class LRUCache {
    class ListNode {
        ListNode prev;
        ListNode next;
        int val = 0;
        int key = 0;
        ListNode() {}
        ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    // new node(most recently) add to the tail part
    public void append(ListNode node) {
        node.prev = tail.prev;
        tail.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }
    
    // least recently node need to be remove from head
    public void remove() {
        remove(head.next);
    }

    // remove the certain node
    public void remove(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    ListNode head, tail;
    Map map;
    int remain;
    public LRUCache(int capacity) {
        remain = capacity;
        // map for get
        map = new HashMap();
        // list for put 
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if(map.containsKey(key)) {
            // remove the key node to the tail
            int value = map.get(key).val;
            put(key, value);
            return value;
        }
        else return -1;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)) {
            ListNode node = map.get(key);
            node.val = value;
            remove(node);
            append(node);
        }
        else {
            // not contain, check if count > capacity
            // remove the least recent node in list & map
            if(remain == 0) {
                map.remove(head.next.key);
                remove();
                remain++;
            }
            ListNode node = new ListNode(key, value);
            append(node);
            map.put(key, node);
            remain--;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
LFU Cache

题目链接:https://leetcode.com/problems...

上一题是只考虑出现的时间,这题加了frequency。那么再加一个map存freq应该是可行的。现在node除了要保存顺序还得保存freq,感觉上像是个二维的,先按freq排序再考虑出现顺序。每次得保存下这个freq出现最早的值,再出现的时候,要从这freq里删了,移到下一个freq的tail上。想了下感觉还是不太好做,看了网上的答案。
参考这个博客:
http://bookshadow.com/weblog/...

first -> point to the freqNode with freq = 1
Map freqMap
relation between freqNode:
first(freq 0) <-> freq 1 <-> freq 2 <-> ......
Map keyMap

get(key):

case 1: return -1

case 2: exist =>

find keyNode and remove from freqNode, if cur freqNode has no element, remove freqNode

find freqNode through freqMap,

find next freqNode(freq + 1) through freqNode,

add keyNode to the tail of next freqNode

put(key, value)

case 1: not exist in keyMap => add to the tail of freqNode with freq = 1

case 2: exist =>

find keyNode, set value and remove from freqNode, if cur freqNode has no element, remove freqNode

find freqNode through freqMap,

find next freqNode(freq + 1) through freqNode,

add keyNode to the tail of next freqNode

其中,keyNode和keyMap和上一题一样都是可以用LinkedHashMap来实现的。那么这里可以稍微改一下,把keyMap里面直接放然后用一个LinkedHashSet来存所有有相同freq的keyNode,只需要存key即可。

public class LFUCache {
    class freqNode {
        int freq = 0;
        freqNode prev, next;
        // store keys
        LinkedHashSet keyNodes = new LinkedHashSet();
        freqNode() {}
        freqNode(int freq) { this.freq = freq; }
        
        public int delete() {
            // if(keyNodes.isEmpty()) return;
            int key = keyNodes.iterator().next();
            keyNodes.remove(key);
            return key;
        }
        public void delete(int key) {
            // if(!keyNodes.contains(key)) return;
            keyNodes.remove(key);
        }
        public void append(int key) {
            keyNodes.add(key);
        }
    }
    
    int remain;
    // key, freqNode pair
    Map freqMap;
    // key, value pair
    Map keyMap;
    freqNode first;
    freqNode last;
    public LFUCache(int capacity) {
        this.remain = capacity;
        freqMap = new HashMap();
        keyMap = new HashMap();
        first = new freqNode();
        last = new freqNode();
        first.next = last;
        last.next = first;
    }
    
    public int get(int key) {
        if(!keyMap.containsKey(key)) return -1;
        else {
            updateFreq(key);
            return keyMap.get(key);
        }
    }
    
    public void put(int key, int value) {
        if(!keyMap.containsKey(key)) {
            if(remain == 0) {
                if(first.next.freq == 0) return;
                // remove the least frequent
                int del = first.next.delete();
                keyMap.remove(del);
                freqMap.remove(del);
                remain++;
            }
            // update map and add node
            keyMap.put(key, value);
            update(first, key);
            remain--;
        }
        else {
            updateFreq(key);
            keyMap.put(key, value);
        }
    }
    
    
    
    private void updateFreq(int key) {
        freqNode node = freqMap.get(key);
        update(node, key);
        
        // remove current node if has no keyNodes
        node.delete(key);
        if(node.keyNodes.size() == 0) {
            removeNode(node);
        }
    }
    
    private void update(freqNode node, int key) {
        // append to the next freq
        addAfterNode(node);
        node.next.append(key);
        // update freqMap key with next freqNode
        freqMap.put(key, node.next);
    }
    
    private void addAfterNode(freqNode node) {
        if(node.next.freq != node.freq + 1) {
            freqNode newNode = new freqNode(node.freq + 1);
            freqNode temp = node.next;
            node.next = newNode;
            newNode.prev = node;
            temp.prev = newNode;
            newNode.next = temp;
            node = null;
        }
    }
    
    private void removeNode(freqNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
}

/**
 * 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);
 */

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

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

相关文章

  • 论文《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条评论

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