likes
comments
collection
share

LRU缓存

作者站长头像
站长
· 阅读数 13

LRU缓存

LRU缓存是一种常见的缓存淘汰算法，LRU的全称是Least Recently Used，即最近最少使用。在LRU缓存中，当缓存空间已满时，会根据缓存数据的访问时间（即最近一次被访问的时间）淘汰最近最少使用的缓存数据。

一种常见的实现方式是使用哈希表和双向链表。哈希表用于快速查找缓存数据，而双向链表用于维护缓存数据的访问时间顺序。具体实现步骤如下：

  1. 初始化一个哈希表和一个双向链表。

  2. 当有新的缓存数据需要被添加到缓存中时，先在哈希表中查找该缓存数据是否已存在：

    • 如果存在，将该缓存数据移动到链表头部，并更新哈希表中该缓存数据的位置；
    • 如果不存在，将该缓存数据添加到链表头部，并在哈希表中添加该缓存数据的位置。如果此时缓存已满，删除链表尾部的数据，并从哈希表中删除该缓存数据的位置。

  3. 当需要访问缓存数据时，先在哈希表中查找该缓存数据是否存在：

    • 如果不存在，返回-1；
    • 如果存在，将该缓存数据移动到链表头部，并更新哈希表中该缓存数据的位置。

  4. 当缓存数据被访问后，需要更新该缓存数据的访问时间，即将该缓存数据移动到链表头部。

时间复杂度： 添加缓存数据、访问缓存数据的时间复杂度均为 O(1)。

空间复杂度： 最坏情况下需要存储所有缓存数据，空间复杂度为 O(capacity)，其中 capacity 为缓存容量。

OrderedDict

道理我都讲了，如果你愿意，你可以用双向链表自己实现一个，如果你不愿意，你可以直接用python的OrderedDict。

OrderedDict是Python的标准库collections中的一个类，它是一个有序字典，具有普通字典的所有功能，并保持字典键的插入顺序。OrderedDict中的键值对是按照插入顺序来排序的。

OrderedDict与普通字典的区别在于，OrderedDict中的元素会按照插入顺序进行排序，而不是按照键的哈希值。OrderedDict的功能基本上与字典一样，但是有几个额外的方法和参数，使得OrderedDict比字典更加灵活和有用。

常用的OrderedDict方法：

  1. OrderedDict.popitem(last=True)： 返回并删除字典中的一个键值对。如果last为True，则删除最后一个插入的键值对，否则删除第一个插入的键值对。

  2. OrderedDict.move_to_end(key, last=True)： 将指定的键移到字典的开头或结尾。如果last为True，则将键移到结尾，否则将键移到开头。

  3. OrderedDict.clear()： 删除OrderedDict中的所有元素。

  4. OrderedDict.copy()： 返回一个OrderedDict的浅拷贝。

  5. OrderedDict.fromkeys(seq[, value])： 创建一个新的OrderedDict，其中包含seq中所有元素作为键，所有键的值都设置为value（默认为None）。

  6. OrderedDict.items()： 返回一个包含OrderedDict所有键值对的元组列表。

  7. OrderedDict.keys()： 返回一个包含OrderedDict所有键的列表。

  8. OrderedDict.values()： 返回一个包含OrderedDict所有值的列表。

試一下：LRU 缓存

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

 

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

 

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put
class LRUCache:

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

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

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



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

该代码实现了一个LRU缓存的数据结构，使用了Python中的OrderedDict类。

在初始化时，使用capacity参数来确定缓存的容量，并创建一个空的OrderedDict对象作为缓存。

在get方法中，如果给定的key在缓存中，则将其移动到OrderedDict的末尾（最近使用的位置），并返回该key对应的value值。否则，返回-1表示缓存中没有该key。

在put方法中，如果给定的key已经在缓存中，则将其移动到OrderedDict的末尾（最近使用的位置），并将其对应的value更新为给定的value。否则，在缓存中添加新的key-value对，并将其放置在OrderedDict的末尾（表示最近使用）。如果添加新的key-value对后，缓存大小超过了容量限制，就从OrderedDict的开头（最旧的位置）删除一个key-value对，以维持缓存的容量不超过设定的值。

整个LRU缓存的实现通过OrderedDict类实现，使用了move_to_end()和popitem()方法，以及OrderedDict的默认行为（即按照添加顺序维护key-value对的顺序）来维护缓存中key-value对的顺序。时间复杂度为O(1)，与OrderedDict类实现的算法时间复杂度一致。