回溯有效地指基于方法輸入的方法調(diào)用的結(jié)果(“回憶錄”→“備忘錄”被記住的→“)結(jié)果，然后返回記住的結(jié)果，而不是再次計(jì)算結(jié)果。您可以將其視為方法結(jié)果的緩存。有關(guān)更多詳細(xì)信息，請參見第387頁中的定義算法簡介(3E)，Cormen等人。

使用Python中的回憶錄計(jì)算階乘的一個(gè)簡單示例如下所示：

factorial_memo = {}def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]

您可以變得更復(fù)雜，并將回憶錄過程封裝到一個(gè)類中：

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        #Warning: You may wish to do a deepcopy here if returning objects
        return self.memo[args]

然后：

def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)factorial = Memoize(factorial)

一種被稱為“裝飾師“是在Python2.4中添加的，它允許您現(xiàn)在只需編寫以下代碼就可以完成相同的任務(wù)：

@Memoizedef factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

這個(gè)PythonDecorator庫有一個(gè)類似的裝飾師memoized這比Memoize這里所示的班級(jí)。

Python 3.2的新版本是functools.lru_cache..默認(rèn)情況下，它只緩存最近使用的128個(gè)調(diào)用，但是可以將maxsize到None若要指示緩存不應(yīng)過期，請執(zhí)行以下操作：

import functools@functools.lru_cache(maxsize=None)def fib(num):
    if num < 2:
        return num    else:
        return fib(num-1) + fib(num-2)

這個(gè)函數(shù)本身是非常慢的，請嘗試fib(36)你得等十秒鐘。

加法lru_cache注釋確保如果函數(shù)是最近為特定值調(diào)用的，它不會(huì)重新計(jì)算該值，而是使用緩存的前一個(gè)結(jié)果。在這種情況下，它帶來了巨大的速度改進(jìn)，而代碼并沒有被緩存的細(xì)節(jié)弄得亂七八糟。

其他的答案涵蓋了它是相當(dāng)好的。我不重復(fù)了。只是一些對(duì)你有用的觀點(diǎn)。

通常，回憶錄是一種運(yùn)算，你可以應(yīng)用于任何計(jì)算某物(昂貴)并返回一個(gè)值的函數(shù)。正因?yàn)槿绱?，它通常被?shí)現(xiàn)為裝飾師..這個(gè)實(shí)現(xiàn)很簡單，它應(yīng)該是這樣的

memoised_function = memoise(actual_function)

或表示為裝潢師

@memoisedef actual_function(arg1, arg2):
   #body