python - Python 中的欧拉计划 #15

Question

我是 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 中。问题出在“搜索”功能中。没有全局变量，我希望它能正常工作。感谢评论，它们真的很有用。

Answer 1

你的内存功能很好，至少对于这个问题。对于更一般的情况，我会使用这个:

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)))