LRU缓存与LFU缓存实现

LRU

最近在LeetCode刷算法题，主要刷Mid和Easy难度的，找找感觉，结果刷到一道Mid题，居然是实现LRU缓存！

这道题印象蛮深的，因为好像CPU里就有LRU缓存，记忆里还是一道Hard难度的难题，所以没有实现，看了下它的题解，没想到几年过去，变成Mid难度了。

这道题我试着做了下，它要求实现一个LRUCache类，这个类提供Get，Put两个方法，有一个容量限制。一般缓存用字典表就可以实现快读读写，但LRU缓存，要求在容量满时，不是拒绝再增加元素，而是从已有元素中踢掉一个最近没有访问过的元素,然后再加新元素进来。

这样的要求，就不能仅仅靠字典了。需要有一个新的结构来维护表中元素的最近使用关系。这里想到一个叫做队列的结构。

队列是一个先进先出的结构。假如我们往队尾塞元素，那么队头就出元素。那么只要我们每次在用户访问元素的时候，从队列中把这个元素揪出来，再塞回队尾，这样一来自然排在队头的，就是最近都没有用户访问的元素，那么当需要移除时，我们就removeFirst，把这个元素踢了就好。

因为这个队列我们需要频繁的修改元素的相对位置，所以适合用双向链表来实现。我们定义一个双向链表，节点和方法如下所示：

class Node:
    def __init__(self,key,value):
        self.key = key 
        self.value = value 
        self.prev = None
        self.next = None

class DoubleList:
    def __init__(self):
        self.head = Node(-1,-1)
        self.tail = Node(-1,-1)
        self.head.next = self.tail
        self.tail.prev = self.head 
    def add2last(self,aim):
        beforeTail = self.tail.prev
        beforeTail.next = aim 
        aim.prev = beforeTail
        aim.next = self.tail
        self.tail.prev = aim 
    def removeNode(self,aim):
        beforeAim = aim.prev
        afterAim = aim.next
        beforeAim.next = afterAim
        afterAim.prev = beforeAim
    def popFirst(self):
        if self.head.next == self.tail:
            return None
        else:
            aim = self.head.next
            self.removeNode(aim)
            return aim 

所谓双向链表，就是Node定义里，我们有prev和next，两个属性，定义节点之前，和之后连接的Node。双向链表在你需要移除指定Node时，可以轻松找到其前后Node，然后将其前后指向修改到对方，这样不再有指向到本Node，自然也就实现了删除。而增加Node时也方便，找到需要插入的位置，修改其前后元素的指向把Node加进来即可。像我们这个需求，只需要在队尾增加。所以只要在队列中增加一个标记队尾的Tail节点。增加Node时加到Tail前面即可。

双向链表和字典关联

双向链表可以解决我们维护访问顺序的功能。但是它不能替代原本的字典的快速取存功能。所以咱这个实现里面，需要同时使用双向链表和字典。这里我的操作，是在字典的保存的Value中，不存储用户输入的Value，而是存储Node（key,value）这个节点。该节点放在字典中以确保用户按key读取时可以迅速找到这个Node，而这个Node同时将被塞进双向链表中。这样当我们需要移动这个Node时，就不需要遍历链表查找它了，而是直接从字典中拿到Node对象，直接进行操作。如此将两种结构的优点都发挥出来了。

class Node:
    def __init__(self,key,value):
        self.key = key 
        self.value = value 
        self.prev = None
        self.next = None

class DoubleList:
    def __init__(self):
        self.head = Node(-1,-1)
        self.tail = Node(-1,-1)
        self.head.next = self.tail
        self.tail.prev = self.head 
    def add2last(self,aim):
        beforeTail = self.tail.prev
        beforeTail.next = aim 
        aim.prev = beforeTail
        aim.next = self.tail
        self.tail.prev = aim 
    def removeNode(self,aim):
        beforeAim = aim.prev
        afterAim = aim.next
        beforeAim.next = afterAim
        afterAim.prev = beforeAim
    def popFirst(self):
        if self.head.next == self.tail:
            return None
        else:
            aim = self.head.next
            self.removeNode(aim)
            return aim 



class LRUCache:
    '''
    解题思路说明
    该问题需要我们实现LRU缓存数据结构，要求在快速查询的基础上，在写入时，如果缓存已满，自行找到“最不常用”的已有元素，将其剔除，然后写入新的元素。
    这么一来，首先为了满足缓存基本的快速查找功能，需要使用到常用数据结构中的哈希表（也就是Python中的字典）。这种结构将数据写入后，支持直接按key查找元素返回。读取数据时，我们就直接从字典中读。
    那么接下来就是如何维护LRU缓存中元素所谓的“最久未使用”的顺序。这里我们考虑使用队列。
    因为队列有个先进先出的性质，当容量满的时候，会将头部元素移除，再把新元素加到尾部。那我们通过算法，将最不常用的元素，挪到头部，常用元素挪到尾部，在放入新元素时，自动踢掉头部元素就可以满足要求了。
    1. 当放入新元素时，如果容器不满，直接放入尾部
    2. 当查询某元素时，将这个元素，改到队尾，相当于刷新它的活跃度。
    3. 当修改某元素时，修改它的值，看面试要求，是否要刷新它的活跃度，本题是需要的，也就是说修改时也要把它移到尾部。
    如此一来，队列头部的元素，就是最近没有使用的元素，所以被挤到最前面了。
    4. 此时再放入新元素，如果容器满，就把队头元素踢了。再加到末尾

    我们将字典表和队列里的元素，关联起来，这样通过查询字典表，可以直接定位到该元素在队列中的位置，然后对其作修改。同样的，从队列中踢元素时，
    根据队列中元素的key，将其在字典中删除。

    队列的实现，采用双向链表，这样换位置比较方便，只要把前后元素头尾连起来，再弄两个夹板标记头尾，这样获取头元素和增加到尾元素也很方便
    '''
    def __init__(self, capacity: int):
        self.doubleList = DoubleList()
        self._dict = {}
        self.capacity = capacity
        self.count = 0


    def move2last(self,aim):
        self.doubleList.removeNode(aim)
        self.doubleList.add2last(aim)
    def get(self, key: int) -> int:
        if key in self._dict:
            aim = self._dict[key]
            self.move2last(aim)
            return aim.value
        return -1
    def put(self, key: int, value: int) -> None:
        if key in self._dict:
            aim = self._dict[key]
            aim.value = value
            self.move2last(aim)

        elif self.count == self.capacity:
            tobeRemoved = self.doubleList.popFirst()
            del self._dict[tobeRemoved.key]

            newNode = Node(key,value)
            self._dict[key] = newNode
            self.doubleList.add2last(newNode)
        else:
            newNode = Node(key,value)
            self._dict[key] = newNode
            self.doubleList.add2last(newNode)
            self.count+=1

剩下就是按照题目的要求进行Get Put方法的编写：

Get方法

1. 去字典中按key找元素，如果不存在，按题目要求返回-1。
2. 如果存在，拿到对应的Node，把Node移动到双向链表的队尾
3. 从Node中取出value，返回

Put方法

1. 去字典中按key找元素，如果存在，修改Node中value，按题目隐含要求，将其也移动到双向链表队尾。
2. 如果不存在，则为新增，此时判断缓存是否满，
3. 如果未满，正常添加，count+1
4. 如果已满，则从双向链表中removeFirst，此时拿到该Node，根据其key，回字典中将其删掉。
5. 然后再正常添加。

LFU

既然LRU不是Hard，那应该有个题目取代了它的位置，我想应该就是LFU。

LFUCache跟LRUCache很像，它也是要求容量满的时候删元素，不过进一步的，它要求统计对象使用频率，先从使用频率低的开始删。题目中有一个暗示，当频率相同时，还是按最近未访问来删。

那就说明这个题目应该还是可以用双向链表来实现同一频率下的状态维护。那么自然想到，我们不再是一个双向队列，而是根据元素使用频率，有几个频率，我们维护几个双向队列。

队列中都是同一使用频率的Node。

所以这里我们定义Node时，增加一个freq属性，记录该node的访问频率。doubelist逻辑我们不改，复用LRUCache。

重点是在LFUCache定义里，增加一个字典表，名为Freq_table。这个表每个key是代表访问频率，value就是一个doublelist。

这样一来，当某个Node被访问时，将该Node从原doublelist移除，然后Freq+1,根据新的Freq找到对应的doublelist，再添加进去。如果新Freq没有doublelist存在，那么就创建一个。

这样Get和Put方法里面移动Node的逻辑就基本OK了。

不过这里少了点什么，就是当我们removeFirst时，会发现，由于不知道目前freq_table表里面最小的freq是哪个，所以不方便。因此这里我们新建一个标记量叫做miniest_freq。

这个值在两个地方修改，第一个是加入新元素时，新元素的freq == 1 ，所以miniest_freq也会变成1；另一个就是移动Node的时候，在删除Node时，我们判断所在的doublelist上还有没有元素，如果无元素（head.next == tail），miniest_freq就不能是这个值了。

class Node:
    def __init__(self,key,value,freq):
        self.key = key
        self.value= value
        self.freq = 1
        self.head = None
        self.tail = None
class DoubleList:
    def __init__(self):
        self.head = Node(0,0,0)
        self.tail = Node(0,0,0)
        self.head.next = self.tail
        self.tail.prev = self.head
    def add2last(self,aim):
        beforeTail = self.tail.prev
        beforeTail.next = aim 
        aim.prev=beforeTail
        aim.next = self.tail
        self.tail.prev = aim

    def removeNode(self,aim):
        beforeAim = aim.prev
        afterAim = aim.next
        beforeAim.next = afterAim
        afterAim.prev = beforeAim
    def removeFirst(self):
        if self.head.next == self.tail:
            return None
        else:
            aim = self.head.next
            self.removeNode(aim)
            return aim
class LFUCache:
    '''
    LFU缓存，是在LRU缓存基础上，增加了调用频率统计的方式
    主要区别就是弹出元素时，先将调用次数最少的元素弹出。
    所以这里基本就是在LRU的一个队列的基础上，增加一个字典，保存不同频率的队列，同时节点中也保存调用次数，这样在元素容量满的时候，再插入元素，就从调取次数最少的队列中，踢出队头元素。
    '''
    def __init__(self, capacity: int):
        self.cache = {}
        self.freq_table={}
        self.miniest_freq = 0
        self.count =0
        self.capacity = capacity
    def moveItem(self,aim):
        self.freq_table[aim.freq].removeNode(aim)
        new_freq = aim.freq+1
        if new_freq not in self.freq_table:
            self.freq_table[new_freq] = DoubleList()
        aim.freq = new_freq
        self.freq_table[new_freq].add2last(aim)

        if aim.freq == 1:
            self.miniest_freq=1
        elif self.miniest_freq == aim.freq-1:
            lastfreq_list = self.freq_table[aim.freq-1]
            if lastfreq_list.head.next == lastfreq_list.tail:
                # 说明这个list为空
                self.miniest_freq = aim.freq
    def get(self, key: int) -> int:
        if key in self.cache:
            aim = self.cache[key]
            self.moveItem(aim)
            return aim.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 老元素更新:
            aim = self.cache[key]
            self.moveItem(aim)
            aim.value = value
        else:
            if self.count<self.capacity:
                if 1 not in self.freq_table:
                    self.freq_table[1] = DoubleList()
                new_node = Node(key,value,1)
                self.cache[key] = new_node
                self.freq_table[1].add2last(new_node)
                self.miniest_freq=1
                self.count+=1
            else:
                aim = self.freq_table[self.miniest_freq].removeFirst()
                del self.cache[aim.key]
                new_node = Node(key,value,1)
                self.cache[key] = new_node
                self.freq_table[1].add2last(new_node)
                self.miniest_freq=1

这两道题目，代码都很长，Python已经是比较简约的语言，还是一坨坨。因为有一部分是实现数据结构的，实际上字典+双向链表的组合，在某些语言是有现成的定义的，如果用那些就可以省一大坨。但刷题算法更多还是看思维过程，以及对于这两道题而言，严谨的逻辑，流程的梳理，写出正确的接口实现，不少东西（比如LFU中最小freq的维护），是更重要的。