在Python中的記憶化

我真的很喜歡你的幫助，瞭解這個使用Python中的Memoization。我是Python的新手，我不確定如何理解這種語法。在Python中的記憶化

def fib_mem(n): 
    return fib_mem_helper(n,[0,1]+[-1]*(n-1)) 

def fib_mem_helper(i,mem): 
    if mem[i] == -1: 
     mem[i]=fib_mem_helper(i-1,mem) + fib_mem_helper(i-2,mem) 
     return mem[i]

這是我看到了使用記憶化avaluating Fibonacci數代碼，這是什麼意思[0,1]+[-1]*(n-1)？你能向我解釋一下這種類型的文字代表什麼？

來源

2013-02-17 Joni

代碼縮進在python中非常重要，所以請複製合適的縮進代碼和「;」字符不在行尾使用。 – eLRuLL 2013-02-17 12:44:49

提供代碼時請注意，它是正確的。如果不是，那麼幫助就更難了。（對於這種情況，這意味着縮進正確，其他語法如'：'而不是';'用於'def'和'if'語句。） – 2013-02-17 12:46:54

[0, 1] + [-1] * (n - 1)表示「連接兩個列表，一個是[0, 1]，另一個是-1重複n-1次」。

來源

2013-02-17 12:45:20

奇怪的編碼，但。看起來像語法錯誤。但根據你的問題：

[0,1]是具有兩個元素的列表，第一個是整數0和第二個是一個整數1

明智執行與記憶化這樣的功能的在Python將是：

def fib(i): 
    try: 
     return fib._memory[i] 
    except KeyError: 
     pass 
    if i == 1 or i == 2: 
     return 1 
    else: 
     f = fib(i-1) + fib(i-2) 
     fib._memory[i] = f 
     return f 
fib._memory = {}

來源

2013-02-17 12:45:28

[-1] * 5將創建一個新的列表具有五個元件是-1，即[-1 -1 -1 -1 -1]

[0 1 ] + [ - 1] * 5會將兩個列表追加爲[0 1 -1 -1 -1 -1 -1]

來源

2013-02-17 12:47:27 Anil

首先，我不得不說，即使在編輯之後，你的代碼仍然有一個錯誤的縮進：return mem[i]應該是縮進。

在列表操作中，「+」表示串聯，「*」表示重複，所以[0,1]+[-1]*(n-1)意味着列表：[0,1，-1，...，-1]（總共（n-1）個負1 ）。

更多說明：

列表[0, 1, -1, ..., -1]存儲計算斐波納契序列（記憶化）。最初它只包含兩個有效值：0和1，所有「-1」元素意味着該索引處的序列還沒有被計算。此備忘錄作爲第二個參數傳遞至功能fib_mem_helper。如果沒有計算出指定的索引（即i）的斐波那契數字（測試是否爲mem[i] == -1），則fib_mem_helper將遞歸計算並將其存儲到mem[i]。如果已經計算出來，只需從備忘錄中返回而無需重新計算。

這就是整個故事。

一錘定音：

這個代碼是沒有足夠有效的，但它需要使用記憶化的。實際上，每次調用fib_mem時，它會創建一個新的列表。例如，如果您撥打fib_mem(8)兩次，第二個電話仍然需要重新創建列表並重新計算所有內容。原因是您將備註存儲在的範圍內fib_mem。要修復它，您可以將備忘錄保存爲fib_mem以外的字典。

來源

2013-02-17 13:04:55

記憶是一種避免重新計算相同問題的技術。我會回到你的問題，但這是一個更容易理解的解決方案。

mem = {0:0, 1:1} 

def fib(n): 
    global mem 
    if mem.get(n,-1) == -1: 
     mem[n] = fib(n-1) + fib(n-2) 
    return mem[n]

通過使mem一個全局變量，你可以利用記憶化的跨越調用fib()。行mem.get(n,-1) == -1檢查mem是否已包含n的計算。如果是，則返回結果mem[n]。否則，它將遞歸調用fib()來計算fib(n)並將其存儲在mem[n]中。

讓我們來看看你的代碼。第二個參數fib_mem_helper(n,[0,1]+[-1]*(n-1))傳遞格式爲[0,1，-1，-1，...]的列表，長度爲(n+1)。在fib_mem_helper函數中，該列表由變量mem引用。如果mem[i]結果爲-1，則計算m[i];否則使用mem[i]的已計算結果。由於您不會在fib_mem()的呼叫範圍內堅持mem，因此它的運行速度要慢一個數量級。

來源

2013-02-17 13:23:36 sidi

在某些功能上使用記憶時，python的加速可能會達到百萬倍或更多。這是斐波那契系列的一個例子。傳統的遞歸方式就是這樣，需要永遠。

def recursive_fibonacci(number): 
    if number==0 or number==1: 
     return 1 
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2) 

print recursive_fibonacci(50),

與memoization相同的算法需要幾毫秒。自己試試！

def memoize(f): 
    memo={} 
    def helper(x): 
     if x not in memo: 
      memo[x]=f(x) 
     return memo[x] 
    return helper 

@memoize 
def recursive_fibonacci(number): 
    if number==0 or number==1: 
     return 1 
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2) 

print recursive_fibonacci(50),

來源

2014-11-08 23:30:33

在Python中的記憶化

回答

相關問題