Python大厂笔试题：手写 LRU 缓存淘汰算法

大家好，我是锋哥。今天分享关于【Python大厂笔试题：手写 LRU 缓存淘汰算法】面试题。希望对大家有帮助；

Python大厂笔试题：手写 LRU 缓存淘汰算法

LRU（Least Recently Used，最少使用）缓存淘汰算法是一种常见的缓存管理策略，它的主要思想是：当缓存达到最大容量时，淘汰最久未被使用的缓存项。在一些实际应用中，比如数据库缓存、浏览器缓存等，LRU算法能有效提高缓存命中率，避免频繁地从磁盘或者数据库读取数据。

在Python中，我们可以通过不同的方式手写实现LRU缓存算法。下面将介绍如何使用Python实现LRU缓存，并给出代码示例。

LRU缓存的实现思路

1. 数据结构的选择：

   • 为了高效地实现LRU缓存，我们需要在O(1)的时间复杂度内完成插入、删除以及查询操作。因此，可以使用双向链表（Doubly Linked List）和哈希表（Hash Map）的组合来实现LRU缓存。
     • 双向链表：可以让我们在O(1)时间内移除最久未使用的缓存项（即链表尾部）以及将缓存项移到最前面（表示最近使用）。
     • 哈希表：可以让我们在O(1)时间内访问缓存项。

2. 操作说明：

   • get(key)：返回缓存中存储的值，如果缓存中没有该key，返回-1。
   • put(key, value)：插入缓存项，如果缓存已满，删除最久未使用的缓存项。

Python实现LRU缓存

我们将使用OrderedDict来实现LRU缓存，OrderedDict是Python内置的一个字典，它保持元素插入顺序。我们可以利用它提供的move_to_end方法来模拟LRU缓存中的访问顺序。

代码实现：

from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): """ 初始化LRU缓存 :param capacity: 缓存的最大容量 """ self.capacity = capacity # 使用OrderedDict来保持缓存项的顺序 self.cache = OrderedDict() def get(self, key: int) -> int: """ 获取缓存中key对应的值，如果缓存中没有该key，返回-1 :param key: 键值 :return: 如果key存在则返回对应的值，否则返回-1 """ if key not in self.cache: return -1 else: # 将该key移动到OrderedDict的末尾，表示最近访问 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) -> None: """ 将key-value插入缓存 :param key: 键值 :param value: 值 """ if key in self.cache: # 如果缓存中已有该key，更新其值并将其移动到末尾 self.cache.move_to_end(key) elif len(self.cache) >= self.capacity: # 如果缓存满了，删除最旧的缓存（即OrderedDict的第一个元素） self.cache.popitem(last=False) # 将新的key-value添加到OrderedDict末尾 self.cache[key] = value # 示例使用： lru_cache = LRUCache(3) lru_cache.put(1, 1) # 缓存 = {1=1} lru_cache.put(2, 2) # 缓存 = {1=1, 2=2} lru_cache.put(3, 3) # 缓存 = {1=1, 2=2, 3=3} print(lru_cache.get(1)) # 返回 1, 缓存 = {2=2, 3=3, 1=1} lru_cache.put(4, 4) # 该操作会删除key 2, 缓存 = {3=3, 1=1, 4=4} print(lru_cache.get(2)) # 返回 -1 (未找到) print(lru_cache.get(3)) # 返回 3 lru_cache.put(5, 5) # 该操作会删除key 1, 缓存 = {3=3, 4=4, 5=5} print(lru_cache.get(1)) # 返回 -1 (未找到) print(lru_cache.get(4)) # 返回 4

代码解析

1. 构造函数__init__：

   • 初始化LRU缓存时，我们指定缓存的最大容量capacity，并使用OrderedDict来存储缓存项。OrderedDict能保持插入的顺序，方便我们访问最旧的元素。

2. get方法：

   • 如果缓存中存在key，我们将它移到链表的尾部，表示最近访问，并返回其对应的值。如果缓存中没有key，返回-1。

3. put方法：

   • 如果缓存已满，首先删除最久未使用的缓存项（即OrderedDict中的第一个元素）。
   • 如果key已存在于缓存中，则更新其对应的值，并将其移到尾部（表示最近访问）。
   • 如果key不在缓存中，直接插入新的键值对。

复杂度分析

• get(key)操作：

  • 时间复杂度是 O(1)，因为我们使用了OrderedDict，并且访问是基于哈希表的查找。

• put(key, value)操作：

  • 时间复杂度是 O(1)，在最坏情况下，删除最久未使用的元素也是 O(1)，而更新或者插入操作也是 O(1)。

最后总结下吧

LRU缓存是一种非常高效的缓存淘汰策略，适用于大多数需要缓存的场景。通过结合使用双向链表和哈希表，可以实现高效的缓存管理。Python提供的OrderedDict使得LRU缓存的实现变得非常简单且高效。如果需要更复杂的缓存策略，可以进一步扩展此基础实现。