加速！缓存Python函数的运行结果：Memoization

使用称为“memoization”的强大而方便的缓存技术来加速您的Python程序。

在这篇文章中，我将向您介绍一种方便的方法来加速你的Python代码，该技术称为memoization (有时拼写为memoisation）：

Memoization是用作软件优化技术的特定类型的缓存。

缓存存储操作的结果以供以后使用。例如，如果将来再次访问，您的Web浏览器很可能会使用缓存来加载此教程网页。

所以，当我谈论memoization和Python时，我正在讨论的是如何根据输入记忆或缓存函数的输出。Memoization的词根来自于单词memorandum，这个词语的意思是“被记住”。

Memoization允许您根据提供给函数的参数缓存输出来优化Python函数。一旦你“记忆”一个函数，它将只为你调用的每一组参数计算一次输出。第一次之后的每次调用结果都将快速从缓存中检索出来。

在本教程中，您将看到如何以及何时用Python来运用这个简单而强大的概念，所以您可以使用它来优化自己的程序，并在某些情况下使其运行速度更快。

为什么以及何时应该在Python程序中使用Memoization？

答案是昂贵的代码：

当我分析代码时，我会根据运行需要多长时间以及它使用多少内存来考虑它。如果需要很长时间才能运行或使用大量内存的代码，那么我认为代码是昂贵的。

昂贵的代码耗费大量的资源，空间和时间来运行。当你运行昂贵的代码时，它会占用你机器上其他程序的资源。

如果你想加快你的Python应用程序中昂贵的部分，memoization可以是一个很好的技巧。让我们先深入研究一下memoization，然后我们就来亲手实现它们！

我在本教程中使用的所有代码示例都是用Python 3编写的，但是当然这里演示的一般技术和模式同样适用于Python 2。

Memoization算法的解释

基本的memoization算法如下所示：

为函数结果设置一个缓存数据结构

每次调用该函数时，请执行以下操作之一：

如果有的话，返回缓存的结果; 要么

调用函数来计算缺少的结果，然后在将结果返回给调用者之前更新缓存

给定足够的缓存存储，这实际上保证了一个特定的函数参数集的函数结果只能计算一次。

只要我们有一个缓存的结果，我们将不必为同一组输入重新运行memoized函数。相反，我们可以获取缓存的结果并立即返回。

我们从零开始写一个Memoization装饰器

接下来，我将用一个Python装饰器来实现上面的memoization算法，这是一个在Python中实现泛型函数包装的方便方法：

装饰器是一个函数，它将另一个函数作为输入，并构建一个函数作为其输出。

这使我们能够以通用和可重用的方式实现我们的memoization算法。听起来有点困惑？不用担心，我们会一步一步地看到一些真实的代码。

这里memoize()是实现上述缓存算法的装饰器：

这个装饰器接受一个函数并返回实现缓存逻辑（memoized_func）的相同函数的包装版本。

我在这里使用Python字典作为缓存。在Python中，使用键可以快速查找字典中的值。这使dict成为函数结果缓存的数据结构的一个很好的选择。

每当装饰函数被调用，我们检查参数是否已经在缓存中。如果是，则返回缓存的结果。所以，我们不是重新计算结果，而是从缓存中快速返回。

如果结果不在缓存中，我们必须更新缓存，以便将来可以节省一些时间。因此，我们首先计算缺失的结果，将其存储在缓存中，然后将其返回给调用者。

让我们用一个递归的斐波那契序列函数测试我们的memoization装饰器。首先，我将定义一个Python函数计算第n个斐波那契数：

这个fibonacci函数将作为一个“昂贵”的计算的例子。用这种方法计算第n个斐波纳契数的时间复杂度为O（2 ^ n），需要花费指数级的时间来完成。

这确实使它成为一个相当昂贵的函数。

接下来，我将做一些基准测试，以便了解这个函数在计算上是多么的昂贵。Python的内置timeit模块让我可以以秒为单位测量任意Python语句的执行时间。

以下是我使用Python内置timeit模块测量fibonacci的函数的执行时间：

正如你所看到的，在我的机器上，计算Fibonacci序列中的第35个数字大约需要五秒钟的时间。这是一个非常缓慢和昂贵的操作。

边栏：timeit.timeit参数

Python的内置timeit模块让我可以测量任意Python语句的执行时间（以秒为单位）。以下是关于上例中我给timeit.timeit传递的参数的简要说明：

因为我在一个Python解释器（REPL）会话中运行这个基准测试，所以我需要为这个基准测试运行设置环境，方法是使用内置的globals()设置globals为当前全局变量集合。

默认情况下timeit()会多次重复基准测试，以使测量的执行时间更加准确。但是，因为一个单独的fibonacci(35)调用已经需要几秒钟的时间来执行，所以我将执行次数number限制为一次。对于这个实验，我对大概的时间数据感兴趣，毫秒精度是不需要的。

让我们看看我们是否可以通过利用memoization装饰器提供的函数结果缓存来加速它：

memoized功能仍然需要大约五秒钟返回第一次运行。到目前为止，如此不堪设想...

我们会得到类似的执行时间，因为第一次运行memoized函数时，没有缓存结果——我们从空的缓存开始，这意味着没有预先计算的结果可以帮助加速这个函数的调用。

让我们再次运行我们的基准测试：

注意到了e-06那个浮点数的末尾的后缀吗？第二次运行memoized_fibonacci只需要约2微秒即可完成。0.0000019930012058466673秒——这确实是一个不错的加速！

我们的memoize装饰器不是递归地计算第35个斐波纳契数，而是简单地取出缓存的结果并立即返回，而这又导致了第二次基准测试中令人难以置信的加速。

检查函数结果缓存

为了真正推动memoization在幕后工作的方式，我想向你展示前面例子中使用的函数结果缓存的内容：

我使用memoized_fibonacci函数的__closure__属性进入“内部”来检查缓存。该cache字典是第一个局部变量，并存储在cell0中。我不建议你在生产代码中使用这种技术—— 但这里它是一个很好的调试技巧。

正如你所看到的，缓存字典将memoized_fibonacci函数调用的参数元组映射到函数结果（第n个斐波那契数）。

所以，例如，(35,)是memoized_fibonacci(35)函数调用的参数元组，它与第35个斐波纳契数9227465相关联：

让我们做一个小小的实验来演示函数结果缓存如何工作。我将再次调用几次memoized_fibonacci来填充缓存，然后我们再次检查它的内容：

正如你所看到的，cache字典现在还包含了对memoized_fibonacci函数的其他几个输入的缓存结果。这使我们能够从缓存中快速检索这些结果，而不是从头开始慢慢重新计算它们。

对我们的memoize装饰器实现的一个简单的缓存提出一个警告：在这个例子中，缓存的大小是无限的，这意味着缓存可以随意增长。这通常不是一个好主意，因为它会导致程序中的内存耗尽错误。

在程序中使用的任何类型的缓存，最好可以同时限制缓存中保存的数据量。这通常是通过对高速缓存大小进行硬性限制或通过定义在某个时刻从高速缓存中逐出旧项目的到期策略来实现的。

请记住，我们之前编写的memoize函数是用于演示目的的简化实现。在本教程的下一节中，您将看到如何在Python程序中使用memoization算法的“生产就绪”实现。

未完，请看第二篇推文

英文原文：https://dbader.org/blog/python-memoization

译者：立方体的太阳