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