Python实现LRU算法 - BBSMAP

Python实现LRU算法

Post published:2023年5月13日
Post category:Python

LRU（Least Recently Used）算法是一种常用的缓存淘汰算法，它根据数据的历史访问记录来淘汰最近最少使用的数据。在Python中，我们可以使用字典和双向链表来实现LRU算法。在本文中，我们将提供一些实现LRU算法的方法。

实现方法

1. 使用OrderedDict

Python中的OrderedDict类是一个有序字典，它可以按照插入顺序来迭代元素。我们可以使用OrderedDict来实现LRU算法。当一个元素被访问时，我们可以将它移到字典的末尾，这样最近访问的元素就会在字典的末尾，最近最少使用的元素就会在字典的开头。当字典的大小超过了缓存的大小时，我们可以从字典的开头删除最近最少使用的元素。

from collections import OrderedDict

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

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

    def put(self, key: int, value: int) -> None:
        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方法来删除字典的开头元素。

2. 使用双向链表和字典

我们也可以使用双向链表和字典来实现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: 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 not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_end(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_end(node)
        else:
            node = ListNode(key, value)
            self.cache[key] = node
            self.add_to_end(node)
            if len(self.cache) > self.capacity:
                node = self.remove_from_head()
                del self.cache[node.key]

    def move_to_end(self, node: ListNode) -> None:
        self.remove_node(node)
        self.add_to_end(node)

    def remove_node(self, node: ListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def add_to_end(self, node: ListNode) -> None:
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def remove_from_head(self) -> ListNode:
        node = self.head.next
        self.remove_node(node)
        return node

在这个示例中，我们使用了双向链表和字典来实现LRU算法。我们使用了move_to_end方法来将访问的元素移到链表的末尾，使用了add_to_end方法来将新元素添加到链表的末尾，使用了remove_from_head方法来删除链表的开头元素。

Tags: Python, 算法