如何在O(1)时间复杂度下实现LRU

用户7685359

发布于 2020-08-22 10:03:18

64100

代码可运行

文章被收录于专栏：FluentStudyFluentStudy

运行总次数：0

代码可运行

一、题意分析

通常我们会把频繁用到的数据放到缓存里，这样取数据比较快，但内存有限，所以经常会有一些淘汰策略，LRU就是其中一种，他的原理是：我们认为最近访问（包括 get 和 set）操作的数据，最有可能是接下来即将用到的数据，当达到一定数量时，我们淘汰掉最近都没有访问的数据

这里需要注意的是，get 操作也算是“访问”了一次数据，显然 put 也算，因为最近插入的数据，极大可能是我马上要用到的数据

其实想要单纯实现是比较简单的，题目难点在于存取时间复杂度的要求是 O(1)

二、实现原理

主要是数据结构的选取，我们可以简单来分析下：

首先存数据，时间复杂度为 O(1)，如果是简单的追加数据，链表和数组都可以，但因为需要体现“最近访问”，所以很大可能需要移动数据，那这时候数组就不是很适合了，链接倒是一个不错的选择

其次取数据，数组按下标取出，时间复杂度确实是 O(1)，但显然我们这里是根据 key 去取对应的 value，很容易想到 python 里的 dict 类型

综上，我们采用的是链表 + 字典的组合。

链表存数据，字典也存在数据，这样显然会有很多问题，比如怎么快速根据 key 找到对应的链表？因此我们换一种思路，链表存取数据，包括key 和 value，而字典格式为 {key: node}，即 key 和对应的链表结点，这样就符合题目要求了

三、呈上代码

下面的实现还是有点不科学，首结点和尾结点没有用到循环链表(因为一开始指针问题思考错误，所以没有科学用于循环链表)，但还是实现了，勉强可看：

class CircleLinkNode:
    """
    双向链接，最先访问的放至尾部
    """
    def __init__(self, key, value):
        self.value = value
        self.key = key
        self.previous = None
        self.next = None


    def insert(self, node):
        """
        尾部插入
        """
        self.next = node
        node.previous = self

    def remove_to_end(self, last_node, root_node):
        """
        将当前结点移至最后
        """
        # 如果当前结点是尾部结点，直接return
        if self.next is None:
            return

        # 如果是头部结点
        if self.previous is None:
            root_node.next = self.next
            self.next.previous = None
            self.next = None
            self.previous = last_node.previous
            last_node.previous.next = self
            last_node.previous = self
            return

        self.previous.next = self.next
        self.next.previous = self.previous      
        self.previous = last_node.previous
        last_node.previous.next = self
        self.next = None
        last_node.previous = self


class LRUCache:

    def __init__(self, capacity: int):
        self._root_node = CircleLinkNode(None, None)  # 头结点
        self._cnode = CircleLinkNode(None, None)  # 当前结点
        self._res_dict = {}
        self._cur_len = 0
        self._capacity = capacity

    def get(self, key: int) -> int:
        # 更新链表结构
        cur_node = self._res_dict.get(key)
        if cur_node:
            cur_node.remove_to_end(self._cnode, self._root_node)
            return cur_node.value
        return self._res_dict.get(key, -1)

    def put(self, key: int, value: int) -> None:
        # 如果当前不存在值
        if self._cur_len == 0:
            new_node = CircleLinkNode(key, value)
            self._cnode.previous = new_node
            self._root_node.next = new_node
            self._res_dict[key] = new_node
            self._cur_len += 1
            return

        # 如果put的值在缓存中存在
        cur_node = self._res_dict.get(key)
        if cur_node:
            # 将当前结点移至尾部结点
            cur_node.value = value
            cur_node.remove_to_end(self._cnode, self._root_node)
            return

        # 如果put的值不在缓存中不存在并且长度不饱和
        if self._cur_len < self._capacity:
            self._cur_len += 1
            new_node = CircleLinkNode(key, value)
            self._cnode.previous.insert(new_node)
            self._cnode.previous = new_node
            self._res_dict[key] = new_node
            return

        # 如果put的值不在缓存中，且长度饱和
        # 先向后追加
        new_node = CircleLinkNode(key, value)
        self._cnode.previous.insert(new_node)
        self._cnode.previous = new_node
        temp_node = self._root_node.next
        self._res_dict[key] = new_node

        self._root_node.next = temp_node.next
        temp_node.next.previous = None
        temp_node.next = None  
        del self._res_dict[temp_node.key]