Python 函数 returns 与记忆不同的结果
Python function returns different result with memoization
我的 Python 寻路函数 returns 如果我使用记忆装饰器会产生不同的结果。它 returns 本身是一个正确的值,但在被记忆后,它 returns 是一个不正确的值。
我说的函数是这样的:
@functools.lru_cache(maxsize=None)
def recursiveTraversal(originIndex, target, steps):
startingVertex = data[originIndex]
if startingVertex["ID"] == target:
if steps == 0:
return Path(0, [])
else:
return None
else:
if steps == 0:
return None
else:
potentialPaths = []
for i in startingVertex["Edges"]:
nextVertex = data[i]
nextPath = recursiveTraversal(i, target, steps - 1)
if nextPath == None:
continue
nextPath.weight += int(nextVertex["Weight"])
nextPath.vertices.append(i)
potentialPaths.append(nextPath)
if len(potentialPaths) > 0:
minPath = min(potentialPaths, key=lambda x: x.weight)
return minPath
else:
return None
一个完整的可运行示例can be found here。文件的上半部分都是数据,代码在下半部分。要重现这一点,只需注释掉第 15 行,然后观察输出是否不同。
如何让记忆版输出与普通版相同的内容?
问题是您正在修改 recursiveTraversal
的 return 值的属性。此函数 returns Path
个对象,您修改它们的属性 weight
和 vertices
。因此,对于非缓存版本,每次使用 (x, y, z)
参数调用函数时,都会创建一个新的 Path(0, [])
对象,并且稍后在 for
循环中修改其属性。但是对于每个 (x, y, z)
调用,您都可以放心地从一个新对象开始。现在对于缓存版本,缓存包装器不是通过递归树一直向下提供新对象,而是为您提供先前创建的 Path
对象的实例(它已经修改了 weight
和 vertices
属性)并且这些被进一步修改(即这修改了缓存)。这可以从下面的例子看出:
# Augment `Path` class with `__repr__`.
class Path:
# Other methods go here.
def __repr__(self):
return '{}({}, {})'.format(self.__class__.__name__, repr(self.weight), repr(self.vertices))
data = [
{'ID': '2', 'Weight': 1, 'Edges': [1]},
{'ID': '1', 'Weight': 1, 'Edges': []}
]
print(recursiveTraversal(0, '1', 1)) # Prints "Path(1, [1])".
print(recursiveTraversal(1, '1', 0)) # Prints "Path(1, [1])".
检查函数 recursiveTraversal
似乎对于 steps=0
它应该 return Path(0, [])
以防目标匹配。尽管如此,它 returns Path(1, [1])
。发生这种情况是因为先前对 recursiveTraversal
的调用已经调用了 recursiveTraversal(1, '1', 0)
并修改了结果的 weight
和 vertices
属性。当执行对 recursiveTraversal(1, '1', 0)
的第二次显式调用时,您将取回对该对象的缓存引用。
可能的解决方案
一个可能的解决方案是在进一步修改之前创建缓存对象的副本。这可以防止缓存被修改。
from copy import deepcopy
# Within `recursiveTraversal`:
# ...
nextPath = deepcopy(recursiveTraversal(i, target, steps - 1))
# ...
我的 Python 寻路函数 returns 如果我使用记忆装饰器会产生不同的结果。它 returns 本身是一个正确的值,但在被记忆后,它 returns 是一个不正确的值。
我说的函数是这样的:
@functools.lru_cache(maxsize=None)
def recursiveTraversal(originIndex, target, steps):
startingVertex = data[originIndex]
if startingVertex["ID"] == target:
if steps == 0:
return Path(0, [])
else:
return None
else:
if steps == 0:
return None
else:
potentialPaths = []
for i in startingVertex["Edges"]:
nextVertex = data[i]
nextPath = recursiveTraversal(i, target, steps - 1)
if nextPath == None:
continue
nextPath.weight += int(nextVertex["Weight"])
nextPath.vertices.append(i)
potentialPaths.append(nextPath)
if len(potentialPaths) > 0:
minPath = min(potentialPaths, key=lambda x: x.weight)
return minPath
else:
return None
一个完整的可运行示例can be found here。文件的上半部分都是数据,代码在下半部分。要重现这一点,只需注释掉第 15 行,然后观察输出是否不同。
如何让记忆版输出与普通版相同的内容?
问题是您正在修改 recursiveTraversal
的 return 值的属性。此函数 returns Path
个对象,您修改它们的属性 weight
和 vertices
。因此,对于非缓存版本,每次使用 (x, y, z)
参数调用函数时,都会创建一个新的 Path(0, [])
对象,并且稍后在 for
循环中修改其属性。但是对于每个 (x, y, z)
调用,您都可以放心地从一个新对象开始。现在对于缓存版本,缓存包装器不是通过递归树一直向下提供新对象,而是为您提供先前创建的 Path
对象的实例(它已经修改了 weight
和 vertices
属性)并且这些被进一步修改(即这修改了缓存)。这可以从下面的例子看出:
# Augment `Path` class with `__repr__`.
class Path:
# Other methods go here.
def __repr__(self):
return '{}({}, {})'.format(self.__class__.__name__, repr(self.weight), repr(self.vertices))
data = [
{'ID': '2', 'Weight': 1, 'Edges': [1]},
{'ID': '1', 'Weight': 1, 'Edges': []}
]
print(recursiveTraversal(0, '1', 1)) # Prints "Path(1, [1])".
print(recursiveTraversal(1, '1', 0)) # Prints "Path(1, [1])".
检查函数 recursiveTraversal
似乎对于 steps=0
它应该 return Path(0, [])
以防目标匹配。尽管如此,它 returns Path(1, [1])
。发生这种情况是因为先前对 recursiveTraversal
的调用已经调用了 recursiveTraversal(1, '1', 0)
并修改了结果的 weight
和 vertices
属性。当执行对 recursiveTraversal(1, '1', 0)
的第二次显式调用时,您将取回对该对象的缓存引用。
可能的解决方案
一个可能的解决方案是在进一步修改之前创建缓存对象的副本。这可以防止缓存被修改。
from copy import deepcopy
# Within `recursiveTraversal`:
# ...
nextPath = deepcopy(recursiveTraversal(i, target, steps - 1))
# ...