Memoization python

Question

什麼是memoization，它是如何在python中使用的？還有它與遞歸的不同之處。 某處我遇到了一個聲明，爲了減少遞歸程序或函數的執行時間，我們應該使用memoization而不是遞歸。例如：

def factorial(n): 
    if n <1: # base case 
     return 1 
    else: 
     return n * factorial(n - 1) # recursive call 

如果這是一個遞歸函數來計算factorial，使用memoization時會發生什麼變化？

Answer 1

記憶是未來使用結果的存儲。 Python的functools模塊包含一個簡單的裝飾器，它可以爲你處理這個問題。因此，例如：

@lru_cache(maxsize=None) 
def factorial(n): 
    ... 

將存儲階乘的每個結果，包括其遞歸調用。這意味着下次您調用階乘時，您將不會執行完整的計算，而是在您遇到之前被調用的呼叫時立即停止。此時，結果將從先前存儲的結果中提取。

這些答案也可能對你有用： What is memoization and how can I use it in Python?

Answer 2

如果一個函數是純的，那麼它總會給出相同的輸入。我們可以通過記住執行一個函數的結果來利用這個優點，從而節省昂貴函數的工作量，如階乘函數。結果看起來像這樣：

factorialAns = {} 
def factorial(n): 
    global factorialAns 
    if n in factorialAns: 
     return factorialAns[n] 
    if n <1: # base case 
     return 1 
    else: 
     factorialAns[n] = n * factorial(n - 1) # recursive call 
     return factorialAns[n]