Python实现LRU算法的2种方法

LRU算法是一种常见的缓存淘汰策略，它可以用于实现缓存系统。在本文中，我们将讲解Python实现LRU算法的2种方法，包括使用Python标准库的collections模块和手实现LRU算法。同时，我们还将提供两个示例说明，以帮助读者更好地理解LRU法的使用方法。

方法1：使用collections模块

Python标准库的collections模块提供了OrderedDict类，它可以用于实现LRU算法。具体来说，我们可以使用OrderedDict类来实现一个有限容量的LRU缓存，缓存达到最大容量时，我们会从缓存中删除最早的元素。

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

在这个示例中，我们使用了OrderedDict类来实现LRU缓存。我们使用了move_to_end方法来将最近使用的元素移动到字典的末尾，使用了popitem方法来删除最早的元素。我们使用了LRUCache类来表示LRU缓存，使用了get方法来获取缓存中的值，使用了put方法来设置缓存中的值。当缓存达到最大容量时，我们会从缓存中删除最早的元素。

示例1：使用collections模块实现LRU算法

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3)
print(cache.get(2))
cache.put(4, 4)
print(cache.get(1))
print(cache.get(3))
print(cache.get(4))

在这个示例中，我们使用了collections模块来实现LRU算法。我们创建了一个容量为2的LRU缓存，使用了put方法来设置缓存中的值，使用了get方法来获取缓存中的值。当缓存达到最大容量时，我们会从缓存中删除最早的元素。

方法2：手动实现LRU算法

除了使用collections模块外，我们还可以手动实现LRU算法。具体来说，我们可以使用双向链表和哈希表来实现LRU算法。双向链表用于存储缓存中的元素，哈希表用于快速查找缓存中的元素。缓存到最大容量时，我们会从链表的头部删除最早的元素。

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

class LRUCache:
    def __init__(self, capacity):
        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):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_end(node)
        return node.value

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_end(node)
        else:
            if len(self.cache) == self.capacity:
                node = self.head.next
                self.remove_node(node)
                del self.cache[node.key]
            node = ListNode(key, value)
            self.cache[key] = node
            self.add_to_end(node)

    def move_to_end(self, node):
        self.remove_node(node)
        self.add_to_end(node)

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

    def add_to_end(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

在这个示例中，我们手动实现了LRU算法。我们使用了双向链表存储缓存中的元素，使用了哈希表来快速查找缓存中的元素。我们使用了move_to_end方法来将最近使用的元素移动到链表末尾，使用了remove_node方法来删除链表中的元素，使用了add_to_end方法来添加元素到链表的末尾。使用了LRUCache类来表示LRU缓存，使用了get方法来获取缓存中的值，使用了put方法来设置缓存中的值。当缓存达到最大容量时，我们会从链表的头部删除最早的元素。

示例2：手动实现LRU算法

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))
cache.put(3, 3)
print(cache.get(2))
cache.put(4, 4)
print(cache.get(1))
print(cache.get(3))
print(cache.get(4))

在这个示例中，我们手动实现LRU算法。我们创建了一个容量为2的LRU缓存，使用了put方法来设置缓存中的值，使用了get方法来获取缓存中的值。当缓存达到最大容量时，我们会从缓存中删除最早的元素。