LFU Cache

update Aug 24, 2017 23:14

LeetCode

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

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Basic Idea:

这里 有一个非常不错的分析文章。

在我的实现中，整个数据结构示意图：

基本思想就是：

• 外层： 维护FreqNode系统，保证O(1)时间找到任何freq的fnode（利用FreqMap），同时要做到产生新的freq时候要增加fnode，内部 dnode 为空时候要删除 fnode；

• 内层： 在每个 fnode 下面维护 DataNode 的链表。当某 dnode 的 freq 提升时（该key被set或者get），要将其移动到 freq+1 的 fnode 下。同时在每个 fnode 内部的链表中保持 LRU 原则，即从tail插入，从head删除；

• 另外，当cache满，需要删除现有dnode时候，选择最左边 fnode 下的 dnode 进行删除。

Java Code:

    public class LFUCache {
        private class FreqNode {
            int freq;
            FreqNode prev = null;
            FreqNode next = null;
            DataNode head = null;
            DataNode tail = null;
            public FreqNode(int freq) {
                this.freq = freq;
                head = new DataNode(-1, -1);
                tail = new DataNode(-1, -1);
                head.next = tail;
                tail.prev = head;
            }
        }

        private class DataNode {
            int key;
            int val;
            int freq = 1;
            DataNode prev = null;
            DataNode next = null;
            public DataNode(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }

        private Map<Integer, FreqNode> FreqMap;
        private Map<Integer, DataNode> DataMap;
        private FreqNode head;
        private FreqNode tail;
        private int capacity;

        public LFUCache(int capacity) {
            this.capacity = capacity;
            FreqMap = new HashMap<>();
            DataMap = new HashMap<>();
            head = new FreqNode(0);
            tail = new FreqNode(0);
            head.next = tail;
            tail.prev = head;
        }

        public void put(int key, int value) {
            if (capacity == 0) return;
            if (DataMap.containsKey(key)) {
                DataNode dnode = DataMap.get(key);
                dnode.val = value;
                updateFreq(dnode);
            } else {
                // 若cache已满, 删除head.next freqnode中的第一个datanode（最老的）
                // 如果移去之后，当前freqnode为空，则删去
                if (DataMap.size() == capacity) {
                    FreqNode fnode = head.next;
                    DataNode dnode = fnode.head.next;
                    DataMap.remove(dnode.key);
                    removeDataNode(dnode);
                    if (fnode.head.next == fnode.tail) {
                        FreqMap.remove(fnode.freq);
                        removeFreqNode(fnode);
                    }
                }
                // 新建新的datanode，插入freq为1的freqnode的tail前(如果没有freq=1，则要新建)
                ensureFirstFreqNode();
                FreqNode fnode = FreqMap.get(1);
                DataNode dnode = new DataNode(key, value);
                DataMap.put(key, dnode);
                insertDataNode(dnode, fnode);
            }
        }

        public int get(int key) {
            if (! DataMap.containsKey(key)) return -1;
            DataNode dnode = DataMap.get(key);
            updateFreq(dnode);
            return dnode.val;
        }

        // 确保当前结构中有freq=1的fnode
        private void ensureFirstFreqNode() {
            if (FreqMap.containsKey(1)) return;
            FreqNode fnode = new FreqNode(1);
            fnode.next = head.next;
            fnode.prev = head;
            fnode.next.prev = fnode;
            head.next = fnode;
            FreqMap.put(1, fnode);
        }

        // 令当前datanode的freq+=1，完成相关所有操作
        private void updateFreq(DataNode dnode) {
            // 先看freq+1是否存在，若不存在，则新建之后插入
            int new_freq = dnode.freq + 1;
            FreqNode new_fnode = null;
            FreqNode prev_fnode = FreqMap.get(dnode.freq);
            if (! FreqMap.containsKey(new_freq)) {
                new_fnode = new FreqNode(new_freq);
                FreqMap.put(new_freq, new_fnode);
                new_fnode.prev = prev_fnode;
                new_fnode.next = prev_fnode.next;
                prev_fnode.next = new_fnode;
                new_fnode.next.prev = new_fnode;
            }
            // 在原fnode中删去dnode，如果之后原fnode为空，则删去fnode
            removeDataNode(dnode);
            if (prev_fnode.head.next == prev_fnode.tail) {
                removeFreqNode(prev_fnode);
                FreqMap.remove(prev_fnode.freq);
            }
            // 更新dnode的freq，并插入新freq对应的fnode
            dnode.freq++;
            new_fnode = FreqMap.get(dnode.freq);
            insertDataNode(dnode, new_fnode);
        }

        // 把datanode插入当前freqnode的tail前
        private void insertDataNode(DataNode dnode, FreqNode fnode) {
            dnode.prev = fnode.tail.prev;
            dnode.next = fnode.tail;
            fnode.tail.prev = dnode;
            dnode.prev.next = dnode;
        }

        private void removeFreqNode(FreqNode fnode) {
            fnode.prev.next = fnode.next;
            fnode.next.prev = fnode.prev;
        }

        private void removeDataNode(DataNode dnode) {
            dnode.prev.next = dnode.next;
            dnode.next.prev = dnode.prev;
        }
    }

Python Code

class FreqNode(object):
    def __init__(self, freq):
        self.freq = freq
        self.prev = None
        self.next = None
        self.head = DataNode(-1, -1)
        self.tail = DataNode(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

class DataNode(object):
    def __init__(self, key, value):
        self.key = key
        self.val = value
        self.freq = 1
        self.prev = None
        self.next = None

class LFUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.head = FreqNode(0)
        self.tail = FreqNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.FreqMap = {}
        self.DataMap = {}

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.DataMap:
            return -1
        dnode = self.DataMap[key]
        self.updateFreq(dnode)
        return dnode.val


    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if self.capacity == 0:
            return
        if key in self.DataMap:
            dnode = self.DataMap[key]
            dnode.val = value
            self.updateFreq(dnode)
        else:
            # 若已满，则移除freq最小的fnode中靠近head的dnode
            if len(self.DataMap) == self.capacity:
                fnode = self.head.next
                dnode = fnode.head.next
                del self.DataMap[dnode.key]
                self.removeDataNode(dnode)
                if self.isEmpty(fnode):
                    del self.FreqMap[fnode.freq]
                    self.removeFreqNode(fnode)

            self.ensureFirstFreq()
            fnode = self.FreqMap[1]
            dnode = DataNode(key, value)
            self.DataMap[key] = dnode
            self.insertDataNode(dnode, fnode)


    def isEmpty(self, fnode):
        return fnode.head.next == fnode.tail

    def ensureFirstFreq(self):
        if self.head.next.freq == 1:
            return
        fnode = FreqNode(1)
        self.FreqMap[1] = fnode
        fnode.next = self.head.next
        fnode.prev = self.head
        self.head.next = fnode
        fnode.next.prev = fnode

    def insertDataNode(self, dnode, fnode):
        # 把dnode插入到fnode中的tail之前
        dnode.next = fnode.tail
        dnode.prev = fnode.tail.prev
        dnode.next.prev = dnode
        dnode.prev.next = dnode

    def removeFreqNode(self, fnode):
        fnode.prev.next = fnode.next
        fnode.next.prev = fnode.prev

    def removeDataNode(self, dnode):
        dnode.prev.next = dnode.next
        dnode.next.prev = dnode.prev

    def updateFreq(self, dnode):
        prev_fnode = self.FreqMap[dnode.freq]
        # 检查freq+1是否存在，若存在，则移动，否则先建freq+1的node
        if dnode.freq + 1 not in self.FreqMap:
            new_fnode = FreqNode(dnode.freq + 1)
            new_fnode.prev = prev_fnode
            new_fnode.next = prev_fnode.next
            new_fnode.prev.next = new_fnode;
            new_fnode.next.prev = new_fnode;
            self.FreqMap[dnode.freq + 1] = new_fnode

        new_fnode = self.FreqMap[dnode.freq + 1]
        self.removeDataNode(dnode)
        self.insertDataNode(dnode, new_fnode)
        if self.isEmpty(prev_fnode):
            del self.FreqMap[dnode.freq]
            self.removeFreqNode(prev_fnode)
        dnode.freq += 1