Python 中的记忆化

1. 在 Python 中使用简单的字典实现 Memoization
2. 在 Python 中使用 Memoization 类实现 Memoization
3. 在 Python 中使用装饰器实现记忆
4. 在 Python 中使用 functools.lru_cache 装饰器实现 Memoization
5. 在 Python 中使用 functools.cache 装饰器实现 Memoization

记忆化是一种通过记住过去完成的计算来加速计算的技术。

它存储一定数量的过去计算，以便于将来的计算。

Memoization 用于计算阶乘和斐波那契数列问题。

在 Python 中使用简单的字典实现 Memoization

字典是 Python 存储数据的四种基本数据类型之一。它在处理函数调用以及检索和存储数据时起作用。

memo1 = {}


def fact1(x):
    if x < 2:
        return 1
    if x not in memo1:
        memo1[x] = x * fact1(x - 1)
    return memo1[x]


for i in range(1, 10):
    print(fact1(i))

输出：

1
2
6
24
120
720
5040
40320
362880

代码说明：

• 首先，字典 memo1 被初始化，它存储 memoization 过程中的值。
• 其次，我们创建并混合了阶乘函数和存储值的字典。
• 然后可以调用该函数以显示所需的结果。

随着字典存储的术语越来越多，这种方法的速度会受到影响并大幅下降。

在需要借助 Memoization 存储大量数据的情况下使其过时。

在 Python 中使用 Memoization 类实现 Memoization

该方法将整个 memoization 过程封装到一个类中，并将其与主要的 factorial 函数分开。

class Memoize:
    def __init__(self, x):
        self.x = x
        self.memo = {}

    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.x(*args)
        return self.memo[args]


def fact1(a):
    if a < 2:
        return 1
    return a * fact1(a - 1)


fact1 = Memoize(fact1)
for i in range(1, 10):
    print(fact1(i))

输出：

1
2
6
24
120
720
5040
40320
362880

代码说明：

• 首先，定义一个 Memoize 类，并在其下定义 __init__ 函数和 __call__ 函数。
• 然后，定义用户定义的 fact1 函数以在递归的帮助下计算阶乘。
• 然后在 print 命令的帮助下显示输出。

这种方法的唯一缺点是它增加了代码的长度并使其更加复杂。

在 Python 中使用装饰器实现记忆

装饰器可以定义为一个函数，它可以将另一个函数作为其唯一参数。可以使用两个装饰器在 Python 中实现 Memoization。

在 Python 中使用 functools.lru_cache 装饰器实现 Memoization

functools.lru_cache 可用于 Python 3.2+ 版本，用于缓存函数调用。它能够存储最多 128 个最近使用的呼叫。

一个简单的调整可以将缓存设置为在代码运行时不过期。需要将 functools 库导入到 python 代码中才能实现此方法而不会出现任何错误。

import functools


@functools.lru_cache(maxsize=None)
def fact1(x):
    if x < 2:
        return 1
    return x * fact1(x - 1)


for i in range(1, 10):
    print(fact1(i))

输出：

1
2
6
24
120
720
5040
40320
362880

在 Python 中使用 functools.cache 装饰器实现 Memoization

functools.cache 装饰器在 Python 3.9 中可用，并且仅适用于迄今为止相对较新的 Python 版本。

该函数存储或缓存使用指定参数集调用函数时返回的值。

需要将 functools 库导入到 python 代码中才能实现此方法而不会出现任何错误。

import functools


@functools.cache
def fact1(x):
    if x < 2:
        return 1
    return x * fact1(x - 1)


for i in range(1, 10):
    print(fact1(i))

输出：

1
2
6
24
120
720
5040
40320
362880