LRU缓存
LRU缓存
LRU缓存是一种常见的缓存淘汰算法,LRU的全称是Least Recently Used,即最近最少使用。在LRU缓存中,当缓存空间已满时,会根据缓存数据的访问时间(即最近一次被访问的时间)淘汰最近最少使用的缓存数据。
一种常见的实现方式是使用哈希表和双向链表。哈希表用于快速查找缓存数据,而双向链表用于维护缓存数据的访问时间顺序。具体实现步骤如下:
-
初始化一个哈希表和一个双向链表。
-
当有新的缓存数据需要被添加到缓存中时,先在哈希表中查找该缓存数据是否已存在:
- 如果存在,将该缓存数据移动到链表头部,并更新哈希表中该缓存数据的位置;
- 如果不存在,将该缓存数据添加到链表头部,并在哈希表中添加该缓存数据的位置。如果此时缓存已满,删除链表尾部的数据,并从哈希表中删除该缓存数据的位置。
-
当需要访问缓存数据时,先在哈希表中查找该缓存数据是否存在:
- 如果不存在,返回-1;
- 如果存在,将该缓存数据移动到链表头部,并更新哈希表中该缓存数据的位置。
-
当缓存数据被访问后,需要更新该缓存数据的访问时间,即将该缓存数据移动到链表头部。
时间复杂度: 添加缓存数据、访问缓存数据的时间复杂度均为 O(1)。
空间复杂度: 最坏情况下需要存储所有缓存数据,空间复杂度为 O(capacity),其中 capacity 为缓存容量。
OrderedDict
道理我都讲了,如果你愿意,你可以用双向链表自己实现一个,如果你不愿意,你可以直接用python的OrderedDict
。
OrderedDict是Python的标准库collections中的一个类,它是一个有序字典,具有普通字典的所有功能,并保持字典键的插入顺序。OrderedDict中的键值对是按照插入顺序来排序的。
OrderedDict与普通字典的区别在于,OrderedDict中的元素会按照插入顺序进行排序,而不是按照键的哈希值。OrderedDict的功能基本上与字典一样,但是有几个额外的方法和参数,使得OrderedDict比字典更加灵活和有用。
常用的OrderedDict方法:
-
OrderedDict.popitem(last=True): 返回并删除字典中的一个键值对。如果last为True,则删除最后一个插入的键值对,否则删除第一个插入的键值对。
-
OrderedDict.move_to_end(key, last=True): 将指定的键移到字典的开头或结尾。如果last为True,则将键移到结尾,否则将键移到开头。
-
OrderedDict.clear(): 删除OrderedDict中的所有元素。
-
OrderedDict.copy(): 返回一个OrderedDict的浅拷贝。
-
OrderedDict.fromkeys(seq[, value]): 创建一个新的OrderedDict,其中包含seq中所有元素作为键,所有键的值都设置为value(默认为None)。
-
OrderedDict.items(): 返回一个包含OrderedDict所有键值对的元组列表。
-
OrderedDict.keys(): 返回一个包含OrderedDict所有键的列表。
-
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类实现的算法时间复杂度一致。
转载自:https://juejin.cn/post/7226004363993808951