Python实现的最近最少使用算法

Python实现最近最少使用算法

最近最少使用算法（Least Recently Used，LRU）是一种缓存淘汰策略，用于在缓存已满时选择要被淘汰的缓存块。该算法的基本思想是，当缓存已满时，淘汰最近最少使用的缓存块。

下面我们将通过python代码实现LRU算法的主要思想，并提供两个示例说明。

算法思路

LRU算法需要同时维护两个数据结构。

• 记录最近访问顺序的双向链表：每次访问缓存块时，将其移动到链表头，链表尾为最近最少使用的缓存块。
• 存储数据的哈希表：哈希表中记录每个缓存块的键和值。

针对一个缓存请求，算法的主要流程如下：

1. 如果缓存已经存在于哈希表中，则将其移动到链表头；
2. 如果缓存不在哈希表中，则将其加入哈希表和链表头；
3. 如果缓存容量已满，则删除链表尾部的缓存块，并在哈希表中删除对应数据；
4. 返回缓存数据。

Python代码实现

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.cache:
            # 移动节点到头部
            node = self.cache[key]
            self.move_to_head(node)
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self.move_to_head(node)
        else:
            node = ListNode(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            if len(self.cache) > self.capacity:
                # 删除尾节点
                removed = self.remove_tail()
                del self.cache[removed.key]

    def add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def move_to_head(self, node):
        self.remove_node(node)
        self.add_to_head(node)

    def remove_tail(self):
        node = self.tail.prev
        self.remove_node(node)
        return node

示例说明

下面我们以一个缓存示例说明该算法的使用。

cache = LRUCache(2)

cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 1

# 这里之所以删除2，是因为插入3后，缓存容量已经满了
cache.put(3, 3)
print(cache.get(2)) # -1

cache.put(4, 4)
print(cache.get(1)) # 1
print(cache.get(3)) # -1
print(cache.get(4)) # 4

在上面的示例中，我们创建了一个容量为2的缓存，先插入了两个值，然后测试了一下get方法，再插入一个值进行覆盖测试，之后调用get方法进行查询。

通过以上示例，我们可以验证LRU算法具备“淘汰最近最少使用缓存块”的功能。