“備忘”的定義

“memoization”（備忘）這個詞是由Donald Michie在1968年提出的，它基于拉丁語單詞“memorandum”（備忘錄），意思是“被記住”。雖然它和單詞“memorization”在某種程度上有些相似，但它并不是該單詞的錯誤拼寫。實際上，Memoisation是一種用于通過計算來加速程序的技術，它通過記住輸入量的計算結果，例如函數(shù)調用結果，來實現(xiàn)其加速目的。如果遇到相同的輸入或者具有相同參數(shù)的函數(shù)調用，那么之前存儲的結果就可以被再次使用，從而避免一些不必要的計算。在很多情況下，可以使用一個簡單的數(shù)組來存儲結果，但也可以使用許多其他的數(shù)據結構，例如關聯(lián)數(shù)組，它在Perl語言中叫做哈希，在Python語言中稱為字典。

備忘功能可以由程序員顯式地編程實現(xiàn)，但是一些編程語言如Python，都提供了自動備忘函數(shù)的機制。
利用函數(shù)裝飾器實現(xiàn)備忘功能

在前面關于遞歸函數(shù)的那章中，我們分別使用迭代和遞歸實現(xiàn)了斐波納契數(shù)列的求解。我們已經證明，如果直接利用斐波納契數(shù)列的數(shù)學定義，在一個遞歸函數(shù)中實現(xiàn)數(shù)列的求解，正如下面的函數(shù)一樣，那么它將具有指數(shù)級的時間復雜度：
 

def fib(n):  if n == 0:    return 0  elif n == 1:    return 1  else:    return fib(n-1) + fib(n-2)

此外，我們還提出了一種提高遞歸實現(xiàn)的時間復雜度的方法，即通過添加一個字典來記住之前函數(shù)的計算結果。這是一個顯式地使用備忘技術的例子，只是當時我們并沒有這么稱呼它。這種方法的缺點是，原始遞歸實現(xiàn)的明晰性和優(yōu)雅性丟失了。

造成以上缺點的原因是，我們改變了遞歸函數(shù)fib的代碼。不過下面的代碼不會改變我們的fib函數(shù)，所以它的明晰性和易讀性并沒有丟失。為了實現(xiàn)該目的，我們使用自定義的函數(shù)memoize()。函數(shù)memoize()以函數(shù)作為參數(shù)，并使用一個字典“memo”來存儲函數(shù)的結果。雖然變量“memo”和函數(shù)“f”僅僅具有局部備忘功能，但是它們通過函數(shù)“helper”被一個閉包捕獲，而memoize()將函數(shù)“helper”作為引用返回。所以，對memoize(fib)的調用將會返回一個helper()的引用，而在helper()中實現(xiàn)了fib()函數(shù)的功能以及一個用于保存還未存儲的結果到字典“memo”中的包裝器，并防止重新計算“memo”中已有的結果。
 

def memoize(f):  memo = {}  def helper(x):    if x not in memo:            memo[x] = f(x)    return memo[x]  return helper def fib(n):  if n == 0:    return 0  elif n == 1:    return 1  else:    return fib(n-1) + fib(n-2) fib = memoize(fib) print(fib(40))

現(xiàn)在讓我們了解下所謂的裝飾器，首先看一下上面代碼中將備忘功能指派到fib函數(shù)的這一行：