Python 中的 LRU 缓存

在本教程中，我们将学习 Python 中的 LRU 缓存。我们将学习缓存策略以及如何使用 Python 装饰器、LRU 策略及其工作原理来实现它们。我们还将讨论如何通过使用 @lru_cache 装饰器进行缓存来提高性能。本教程将深入了解缓存的工作原理以及如何在 Python 中从中获益。首先，让我们了解什么是缓存及其用途。

缓存及其用途

缓存是内存管理的一种最佳技术，它将最近或最常使用的数据存储在内存中，以便我们可以比从实际源访问更快或计算成本更低地访问它们。

LRU 缓存遵循先进先出格式。让我们以一个真实生活中的例子来更好地理解它。

假设我们正在创建一个网站，该网站会从不同的网站获取文章。当用户点击特定列表时，应用程序会下载文章并显示在屏幕上。

当用户决定返回到已访问的文章时会发生什么？如果我们的应用程序不支持缓存技术，它将一遍又一遍地下载相同的内容。这将使应用程序系统非常缓慢，并给托管文章的服务器带来额外压力。

在这种情况下，应用程序将在获取每篇文章后将内容本地存储。下次用户决定打开文章时，应用程序将从本地存储的副本中获取内容，而不是返回到资源。这项技术被称为缓存。

什么是 LRU 缓存？

LRU 缓存称为 Least Recently Used（最近最少使用），这是一种常见的缓存策略，用于定义逐出元素并为新元素腾出空间的策略。当缓存已满时，它会首先丢弃最近最少使用的项目。在 LRU 中，有两种引用使用 -

• 页面命中 (Page hit) - 如果引用页在主内存中找到，则为页面命中。
• 页面错误 (Page Fault) - 这与页面命中正好相反。如果引用页在内存中找不到，则会发生页面错误。

使用 Python 字典实现缓存

我们可以使用 Python 字典实现缓存解决方案。让我们以文章引用为例，而不是直接访问服务器，我们可以检查缓存并将其返回给服务器。让我们理解下面的例子。

示例 -

输出

Getting article...
Fetching article from server...
Getting article...
Fetching article from server...

解释 -

在上面的代码中，我们可以看到我们得到了字符串“正在从服务器获取文章”，因为在第一次访问文章后，我们将它的 URL 和内容放入了缓存字典。当我们第二次运行代码时，我们不需要再次从服务器获取项目。

各种缓存策略

我们需要有适当的策略来决定使应用程序更高效。在我们的应用程序中，当用户下载更多文章时，它会继续将它们存储在内存中，这可能导致应用程序崩溃。

合适的策略可以使用专注于管理缓存信息以及移除哪个项目以腾出新项目空间的算法来解决此类问题。有各种策略可以用来驱逐缓存并为新缓存腾出空间。让我们看看下面的流行缓存策略。

我们将在接下来的部分中使用 Python 的 functools 模块的 @lru_cache 装饰器。

LRU（最近最少使用）缓存策略

LRU 策略以组织其项目的使用方式而闻名。当我们尝试访问 LRU 算法中的条目时，它会将该条目移到缓存的顶部。算法通过检查列表的底部来识别未使用的条目。

当新条目进来时，它会将第一个条目向下推。该算法假定如果一个对象已被使用，它在未来被需要的可能性更大。

在 Python 中创建 LRU 缓存

在本节中，我们将使用 Python 的功能创建一个简单的 LRU 缓存实现。Python 带有称为 OrderedDict 的哈希表，它保留了键的插入顺序。我们使用以下策略来实现这一点。

• 我们创建 get() 函数，该函数会移除字典并将项添加到有序键的末尾。
• 我们创建 put() 函数，该函数会检查空间；如果空间已满，则用最新条目替换有序键中的第一个条目。它之所以有效，是因为每次 get() 调用都会将一个项目移到有序键的末尾；因此，第一个项目就是最近最少使用的。

示例 -

输出

OrderedDict([('1', '1'), ('3', '3'), ('4', '4')])
OrderedDict([('3', '3'), ('4', '4'), ('5', '5')])

说明

让我们分解代码 -

• 我们创建了一个可以容纳三个项目的缓存。
• cache.put('1', '1') 函数将 1 存储在 OrderedDict 的最后，cache.put('2', '2') 和 cache.put('3', '3') 也是如此。现在元素存储为 [1, 2, 3]。
• 当调用 cache.get('1') 时，1 会从前面移除并添加到最后。现在元素存储为 [2, 3, 1]。
• 当调用 cache.get('1') 时，1 会从前面移除并添加到最后。现在元素存储为 [2, 1, 3]。
• 当我们调用 cache.put('4', '4') 时，它会从前面移除并添加到后面，现在元素存储为 [1, 3, 4]。
• 当我们调用 cache.put('5', '5') 时，它会从前面移除并添加到后面，最后，元素存储为 [3, 4, 5]。

使用 functools 在 Python 中创建 LRU 缓存

在这里，我们将使用 functools 模块的 @lru_cache 装饰器。然而，@lru_cache 在后台使用它。我们可以将此装饰器应用于任何接受潜在键作为输入并返回相应数据对象的函数。优点是，当再次调用该函数时，如果相应的数据已存在于缓存中，装饰器将不会执行函数语句。

让我们理解下面的例子。

示例 -

输出

Cache miss with 1
1: value
Cache miss with 2
2: value
Cache miss with 3
3: value
Cache miss with 4
4: value
4: value
3: value
1: value
Cache miss with 7
7: value
Cache miss with 6
6: value
3: value
1: value

基于时间和空间逐出缓存条目

@lru_cache 装饰器仅在没有空间存储更多条目时才会逐出现有条目。如果条目足够，它们将一直存在，永远不会刷新。因此，我们可以实现此功能来更新缓存系统，使其在特定时间后过期。

我们可以使用 @lru_cache 来实现这一点，如前所述。如果调用者尝试访问已过期的项目，缓存将不会返回其内容，而是强制调用者直接从网络获取结果。

让我们理解以下示例 -

示例 -

让我们分解代码 -

• @timed_lru_decorator 用于支持缓存中条目的生存期以及缓存的最大大小。
• 在 wrap_cache 函数中，lru_cache 实现相同的功能，而其余两行使用两个属性为装饰器函数添加了仪器，这些属性表示缓存的生存期以及数据实际过期的时间。
• 在 wrapped_func 函数中，装饰器检查当前时间是否已过过期日期。如果发生这种情况，它会从缓存中删除所有条目并重新计算生存期和过期日期。

我们可以通过根据各个条目的生存期来逐出条目，从而更复杂地实现此策略。

结论

缓存是提高任何软件系统性能的重要策略。我们已经解释了一些与 LRU 相关的重要概念以及如何使用多种技术（如 @lru_cache 和 OrderDict）来实现它。它还包括使用 timeit 模块测量代码运行时间。