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