在遞歸代碼中斷功能中實現記憶

-1

我寫，需要一個金字塔一個代碼：

[[1], 
[2,3], 
[4,5,6], 
[7,8,9,10]]

從頭部開始（金字塔[0] [0]）計算最大總和可能通過移動到或者低於項，或要實現下方和右邊的項遞歸

在這個例子中，輸出應爲20

這是一個沒有記憶化的代碼，其中正常工作：

def max_trail(pyramid,row=0,col=0): 
    if row == (len(pyramid)-1): 
     return pyramid[row][col] 
    else: 
     return pyramid[row][col] + max(max_trail(pyramid ,row+1 ,col), 
             max_trail(pyramid ,row+1, col+1))

但是，當我嘗試應用memoization，沿途的事情打破。我錯過了什麼？

這是斷碼：

def max_trail_mem(pyramid,row=0,col=0,mem=None): 
    if mem==None: 
     mem={} 
    key = ((row),(col)) 
    if row == (len(pyramid)-1): 
     if key not in mem: 
      value = pyramid[row][col] 
      mem[key]=value 
      return mem[key] 
     return mem[key] 
    else: 
     key = (row+1),(col) 
     if key not in mem: 
      mem[(row+1),(col)] = max_trail_mem(pyramid ,row+1 ,col,mem) 
     key = (row+1),(col+1) 
     if key not in mem: 
      mem[(row+1),(col+1)]=max_trail_mem(pyramid ,row+1, col+1,mem) 
    return max(mem[(row+1),(col)],mem[(row+1),(col+1)])

這已小時的休息我可憐studential生活。任何幫助將不勝感激！

來源

2016-12-17 Guy Seltenreich

歡迎的StackOverflow！請花時間參加[旅遊]（http://stackoverflow.com/tour），並參閱[我可以在這裏問什麼？]（http://stackoverflow.com/help/on-topic）。正如它寫的，你的問題是要求調試幫助「爲什麼這個代碼不工作？」這在[我可以在這裏問什麼？]（http://stackoverflow.com/help/on-topic）作爲stackoverflow的offtopic特別列出。 –

您是否嘗試過測試失敗的地方？您可以添加打印語句以進行快速測試或使用[pdb]（https://docs.python.org/3.6/library/pdb.html）。 – Nister

您忘記了pyramid[row][col] +之前max(...在您最後的回報。添加它給20您的例子（見的代碼最後一行）：

def max_trail_mem(pyramid,row=0,col=0,mem=None): 
    if mem==None: 
     mem={} 
    key = ((row),(col)) 
    if row == (len(pyramid)-1): 
     if key not in mem: 
      value = pyramid[row][col] 
      mem[key]=value 
      return mem[key] 
     return mem[key] 
    else: 
     key = (row+1),(col) 
     if key not in mem: 
      mem[(row+1),(col)] = max_trail_mem(pyramid ,row+1 ,col,mem) 
     key = (row+1),(col+1) 
     if key not in mem: 
      mem[(row+1),(col+1)] = max_trail_mem(pyramid ,row+1, col+1,mem) 
    return pyramid[row][col] + max(mem[(row+1),(col)],mem[(row+1),(col+1)])

來源

2016-12-17 19:13:44

謝謝！這樣可行！但是......似乎這裏的記憶實際上並沒有改善運行時間......它有什麼貢獻嗎？我嘗試了一個大小爲10的金字塔，並且它在沒有記憶的情況下在我的版本中返回了相同的運行時間，並且在這裏有任何建議？ –

我得到41.2微秒的備忘錄和201微秒的純遞歸版本。因此，對於10號金字塔，速度大約快5倍。對於15號金字塔，差值爲101微秒和6.15毫秒，即超過60倍。對於20號，這個因子超過1000. –

謝謝麥克，我嘗試了一個更大的金字塔，它確實有效！ –

from timeit import timeit 
import math 

from repoze.lru import CacheMaker 
cache_maker=CacheMaker() 


def max_trail(pyramid,row=0,col=0): 
    if row == (len(pyramid)-1): 
     return pyramid[row][col] 
    else: 

     mt1 = max_trail(pyramid ,row+1 ,col) 
     mt2 = max_trail(pyramid ,row+1, col+1) 
     return pyramid[row][col] + max(mt1, mt2) 

@cache_maker.lrucache(maxsize='1000', name='pyramid') 
def max_trail_with_memoization(pyramid,row=0,col=0): 
    if row == (len(pyramid)-1): 
     return pyramid[row][col] 
    else: 

     mt1 = max_trail(pyramid ,row+1 ,col) 
     mt2 = max_trail(pyramid ,row+1, col+1) 
     return pyramid[row][col] + max(mt1, mt2) 

# Build pyramid 
pyramid =() 
c = 0 
for i in range(20): 
    row =() 
    for j in range(i): 
     c += 1 
     row += (c,) 
    if row: 
     pyramid += (tuple(row),) 

# Repetitions to time 
number = 20 

# Time it 
print('without memoization: ', timeit('f(t)', 'from __main__ import max_trail as f, pyramid as t', number=number)) 
print('with memoization  ', timeit('f(t)', 'from __main__ import max_trail_with_memoization as f, pyramid as t', number=number)) 




print max_trail(pyramid)

without memoization: 3.9645819664001465 
with memoization:  0.18628692626953125

來源

2016-12-17 19:59:14

謝謝伊凡=） –

在遞歸代碼中斷功能中實現記憶

回答

相關問題