我是Python的新手。我坚持在合理的时间内在Project-Euler中进行问题15。记忆功能中的问题。没有备忘录，一切工作正常，但仅适用于小型网格。我尝试使用“记忆化”，但对于所有网格，此类代码的结果均为“ 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)))
问题不在于我以前想的那样。问题出在“搜索”功能上。Whithout Globals希望它能正确执行。感谢您的意见，他们真的很有用。
至少对于这个问题，您的记忆功能很好。对于更一般的情况，我将使用以下代码：
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在评论中指出的那样）是，只有在该功能无法通过副作用起作用的情况下，记忆才有效。当函数执行return结果时，您无需在递归计算中使用此结果，而仅依赖于递增全局计数器变量。当您通过记忆获得较早的结果时，该计数器将不会进一步增加，也不会使用返回的值。
更改您的函数以总结递归调用的结果，然后它将起作用。
您还可以稍微简化代码。特别是，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)))
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句