Python 中的记忆化

Vaibhhav Khetarpal 2023年1月30日 2022年5月17日
  1. 在 Python 中使用简单的字典实现 Memoization
  2. 在 Python 中使用 Memoization 类实现 Memoization
  3. 在 Python 中使用装饰器实现记忆
  4. 在 Python 中使用 functools.lru_cache 装饰器实现 Memoization
  5. 在 Python 中使用 functools.cache 装饰器实现 Memoization
Python 中的记忆化

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

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

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
Vaibhhav Khetarpal avatar Vaibhhav Khetarpal avatar

Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.

LinkedIn