我是 Python 新手。我坚持在合理的时间内完成 Project-Euler 中的第 15 题。 memoize 函数中的问题。没有内存所有工作都很好,但只适用于小网格。我已尝试使用记忆化,但此类代码的结果对于所有网格都是“1”。
def memoize(f): #memoization
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
@memoize
def search(node):
global route
if node[0] >= k and node[1] >= k:
route += 1
return route
else:
if node[0] < k + 1 and node[1] < k + 1:
search((node[0] + 1, node[1]))
search((node[0], node[1] + 1))
return route
k = 2 #grid size
route = 0
print(search((0, 0)))
如果注释掉禁用内存功能的代码:
#@memoize
一切正常,但对于大网格来说会变慢。我究竟做错了什么?帮忙调试。非常感谢!
更新1:
谢谢你的帮助,我也找到了答案:
def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
@memoize
def search(node):
n = 0
if node[0] == k and node[1] == k:
return 1
if node[0] < k+1 and node[1] < k+1:
n += search((node[0] + 1, node[1]))
n += search((node[0], node[1] + 1))
return n
k = 20
print(search((0, 0)))
问题并不像我之前想的那样出在 memoize func 中。问题出在“搜索”功能中。没有全局变量,我希望它能正常工作。感谢评论,它们真的很有用。
最佳答案
你的内存功能很好,至少对于这个问题。对于更一般的情况,我会使用这个:
def memoize(f):
f.cache = {} # - one cache for each function
def _f(*args, **kwargs): # - works with arbitrary arguments
if args not in f.cache: # as long as those are hashable
f.cache[args] = f(*args, **kwargs)
return f.cache[args]
return _f
实际的问题——正如 Kevin 在评论中指出的那样——是只有当函数不能通过副作用起作用时内存才起作用。虽然您的函数确实返回
结果,但您不会在递归计算中使用它,而只是依赖递增全局计数器变量。当您通过内存获得较早的结果时,该计数器不会再增加,您也不会使用返回的值。
改变你的函数来总结递归调用的结果,然后它就可以工作了。
您还可以稍微简化您的代码。特别是,递归调用之前的 if
检查不是必需的,因为无论如何您都会检查 >= k
,但是您应该检查 x
组件 或 y
组件是 >= k
,而不是两者;一旦其中一个命中k
,就只有一条通往目标的路线。此外,您可以尝试倒数到 0
而不是倒数到 k
,这样代码就不再需要 k
了。
@memoize
def search(node):
x, y = node
if x <= 0 or y <= 0:
return 1
return search((x - 1, y)) + search((x, y - 1))
print(search((20, 20)))
关于python - Python 中的欧拉计划 #15,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24932779/