在递归代码中断功能中实现记忆
Implementing memoization in recursive code break functionality
我似乎无法弄清楚是什么破坏了我的代码。
我写了一个取金字塔的代码:
[[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))
但是当我尝试应用记忆时,过程中出现了问题。
我错过了什么?
这是损坏的代码:
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)])
这让我的学生生活少了几个小时。
任何帮助将不胜感激!
您上次 return 在 max(...
之前忘记了 pyramid[row][col] +
。添加它会为您的示例提供 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)])
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)
Returns:
without memoization: 3.9645819664001465
with memoization: 0.18628692626953125
我似乎无法弄清楚是什么破坏了我的代码。
我写了一个取金字塔的代码:
[[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))
但是当我尝试应用记忆时,过程中出现了问题。 我错过了什么?
这是损坏的代码:
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)])
这让我的学生生活少了几个小时。 任何帮助将不胜感激!
您上次 return 在 max(...
之前忘记了 pyramid[row][col] +
。添加它会为您的示例提供 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)])
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)
Returns:
without memoization: 3.9645819664001465
with memoization: 0.18628692626953125