Python: 为什么这个递归不改变输入列表？
Python: Why doesn't this recursion mutate the input list?
这是理解Python列表变异的问题。我解决了这个深度优先搜索问题并且得到了正确的结果。然后我得到了一些反馈，在我看来不应该起作用，但它起作用了。
基本上，如果我使用 path[0] 而不是 current_path（通过切换成对的注释行和非注释行），结果是相同的。我试图理解为什么会这样。我知道列表路径中的列表，意思是路径 [0]，没有发生变化。但是，当我将不同的列表分配给路径的第 0 个索引时，列表路径应该发生变化。然而，它工作得很好。
下面是代码，我留下了文档字符串以供进一步说明。最后，我粘贴了我玩过的代码以更好地理解列表突变，但这对我没有帮助。有人可以解释一下吗？
# Problem 3b: Implement get_best_path
def get_best_path(digraph, start, end, path, max_dist_outdoors, best_dist,
best_path):
"""
Finds the shortest path between buildings subject to constraints.
digraph: Digraph instance
The graph on which to carry out the search
start: string, Building number at which to start
end: string, Building number at which to end
path: list composed of [[list of strings], int, int]
Represents the current path of nodes being traversed. Contains
a list of node names, total distance traveled, and total
distance outdoors.
max_dist_outdoors: int
Maximum distance spent outdoors on a path
best_dist: int
The smallest distance between the original start and end node
for the initial problem that you are trying to solve
best_path: list of strings
The shortest path found so far between the original start
and end node.
Returns:
A tuple with the shortest-path from start to end, represented by
a list of building numbers (in strings), [n_1, n_2, ..., n_k],
where there exists an edge from n_i to n_(i+1) in digraph,
for all 1 <= i < k and the distance of that path.
If there exists no path that satisfies max_total_dist and
max_dist_outdoors constraints, then return None.
"""
if not digraph.has_node(Node(start)) or not digraph.has_node(Node(end)):
raise ValueError('Start or end node, or both not in graph')
current_path = path[0] + [start]
path[0]="This line doesn't change a thing, if I use 'current_path', but why?!"
# path[0] = path[0] + [start]
if start == end:
return [current_path, path[1], path[2]]
# return path
edges = digraph.get_edges_for_node(Node(start))
for edge in edges:
next_node = str(edge.get_destination())
if next_node not in current_path: #avoiding cycles
# if next_node not in path[0]: #avoiding cycles
new_tot = path[1] + edge.get_total_distance()
new_out = path[2] + edge.get_outdoor_distance()
if (best_dist==None or best_dist>=new_tot) and new_out<=max_dist_outdoors:
new_path=get_best_path(digraph, next_node, end, [current_path,new_tot,new_out], \
# new_path=get_best_path(digraph, next_node, end, [path[0],new_tot,new_out], \
max_dist_outdoors, best_dist, best_path)
if new_path != None:
best_path = new_path[0]
best_dist = new_path[1]
if best_path == None:
return None
return [best_path, best_dist]
我在这里尝试了这个想法，但正如我所料，输入列表发生了变化。那么，为什么大写的列表'path'没有发生变异呢？
def foo_mutating(bar):
bar[0] = bar[0] + [1]
print('bar inside foo:', bar)
if len(bar[0]) == 5:
return bar
return foo_mutating(bar)
def foo_nonmut(bar):
temp_bar0 = bar[0]+[1]
print('bar inside foo:', bar)
if len(temp_bar0) == 5:
return [temp_bar0, bar[1], bar[2]]
return foo_nonmut([temp_bar0, bar[1], bar[2]])
def test():
print('-----TESTING NON-MUTATING----')
bar_init = [[], 22, 33]
print('bar_init:', bar_init)
new_bar = foo_nonmut(bar_init)
print('new_bar:', new_bar)
print('bar_init:', bar_init)
print('\n')
print('-----TESTING MUTATING----')
bar_init = [[], 22, 33]
print('bar_init:', bar_init)
new_bar = foo_mutating(bar_init)
print('new_bar:', new_bar)
print('bar_init:', bar_init)
test()
打印：
-----TESTING NON-MUTATING----
bar_init: [[], 22, 33]
bar inside foo: [[], 22, 33]
bar inside foo: [[1], 22, 33]
bar inside foo: [[1, 1], 22, 33]
bar inside foo: [[1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1], 22, 33]
new_bar: [[1, 1, 1, 1, 1], 22, 33]
bar_init: [[], 22, 33]
-----TESTING MUTATING----
bar_init: [[], 22, 33]
bar inside foo: [[1], 22, 33]
bar inside foo: [[1, 1], 22, 33]
bar inside foo: [[1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1, 1], 22, 33]
new_bar: [[1, 1, 1, 1, 1], 22, 33]
bar_init: [[1, 1, 1, 1, 1], 22, 33]
Why doesn't this recursion mutate the input list?
因为它不是用输入列表调用的，因此没有它可用于变异。
当你进行递归调用时（我重新格式化了一下）：
# "non-mutating" approach, as in the original code
new_path = get_best_path(
digraph, next_node, end, [current_path,new_tot,new_out],
max_dist_outdoors, best_dist, best_path
)
# "mutating" approach, using the commented-out line
new_path=get_best_path(
digraph, next_node, end, [path[0],new_tot,new_out],
max_dist_outdoors, best_dist, best_path
)
尝试改变路径的算法会创建一个传递给递归调用的新列表，因此它不会改变。与玩具示例对比：
# "non-mutating" recursive call
return foo_nonmut([temp_bar0, bar[1], bar[2]])
# "mutating" recursive call
return foo_mutating(bar)
# Notice, it does not make a new list.
一般来说，当您不依赖变异时，递归算法更容易推理。您可能还会发现，通过使用某种 class 来表示路径，您可以获得更清晰、更易于理解的代码。然后你可以为 "create a new path with the specified node appended to the node name list" 和 "create a new path with modified distance data" 提供 class 非变异方法。 （或者更好的是 - 同时，给它一个 Edge 实例，它从中获取所有必要的数据）。
类似于：
class Path:
def __init__(self, names, distance, outdoor):
self._names, self._distance, self._outdoor = names, distance, outdoor
def __contains__(self, node):
return node in self._names
def with_edge(self, edge):
return Path(
# incidentally, you should be using `property`s instead of methods
# for this Edge data.
self._names + [edge.get_destination()],
self._distance + edge.get_total_distance(),
self._outdoor + edge.get_outdoor_distance()
)
def better_than(self, other, outdoor_limit):
if self._outdoor <= outdoor_limit:
return False
best_distance = other._distance
return best_distance is None or best_distance >= self._distance
def end(self): # where we start recursing from during pathfinding.
return self._names[-1]
现在我们可以做更多类似的事情：
# instead of remembering best_path and best_dist separately, we'll just
# use a Path object for best_path, and we can ignore the outdoor distance
# when interpreting the results outside the recursion.
edges = digraph.get_edges_for_node(Node(start))
for edge in edges:
if edge.get_destination() in path:
continue
candidate = path.with_edge(edge)
if candidate.better_than(best_path, max_dist_outdoors):
# We can remove some parameters from the recursive call,
# because we can infer them from the passed-in `path`.
new_path = get_best_path(digraph, end, path, max_dist_outdoors, best_path)
if new_path is not None:
best_path = new_path
这是理解Python列表变异的问题。我解决了这个深度优先搜索问题并且得到了正确的结果。然后我得到了一些反馈，在我看来不应该起作用，但它起作用了。
基本上，如果我使用 path[0] 而不是 current_path（通过切换成对的注释行和非注释行），结果是相同的。我试图理解为什么会这样。我知道列表路径中的列表，意思是路径 [0]，没有发生变化。但是，当我将不同的列表分配给路径的第 0 个索引时，列表路径应该发生变化。然而，它工作得很好。
下面是代码，我留下了文档字符串以供进一步说明。最后，我粘贴了我玩过的代码以更好地理解列表突变，但这对我没有帮助。有人可以解释一下吗？
# Problem 3b: Implement get_best_path
def get_best_path(digraph, start, end, path, max_dist_outdoors, best_dist,
best_path):
"""
Finds the shortest path between buildings subject to constraints.
digraph: Digraph instance
The graph on which to carry out the search
start: string, Building number at which to start
end: string, Building number at which to end
path: list composed of [[list of strings], int, int]
Represents the current path of nodes being traversed. Contains
a list of node names, total distance traveled, and total
distance outdoors.
max_dist_outdoors: int
Maximum distance spent outdoors on a path
best_dist: int
The smallest distance between the original start and end node
for the initial problem that you are trying to solve
best_path: list of strings
The shortest path found so far between the original start
and end node.
Returns:
A tuple with the shortest-path from start to end, represented by
a list of building numbers (in strings), [n_1, n_2, ..., n_k],
where there exists an edge from n_i to n_(i+1) in digraph,
for all 1 <= i < k and the distance of that path.
If there exists no path that satisfies max_total_dist and
max_dist_outdoors constraints, then return None.
"""
if not digraph.has_node(Node(start)) or not digraph.has_node(Node(end)):
raise ValueError('Start or end node, or both not in graph')
current_path = path[0] + [start]
path[0]="This line doesn't change a thing, if I use 'current_path', but why?!"
# path[0] = path[0] + [start]
if start == end:
return [current_path, path[1], path[2]]
# return path
edges = digraph.get_edges_for_node(Node(start))
for edge in edges:
next_node = str(edge.get_destination())
if next_node not in current_path: #avoiding cycles
# if next_node not in path[0]: #avoiding cycles
new_tot = path[1] + edge.get_total_distance()
new_out = path[2] + edge.get_outdoor_distance()
if (best_dist==None or best_dist>=new_tot) and new_out<=max_dist_outdoors:
new_path=get_best_path(digraph, next_node, end, [current_path,new_tot,new_out], \
# new_path=get_best_path(digraph, next_node, end, [path[0],new_tot,new_out], \
max_dist_outdoors, best_dist, best_path)
if new_path != None:
best_path = new_path[0]
best_dist = new_path[1]
if best_path == None:
return None
return [best_path, best_dist]
我在这里尝试了这个想法，但正如我所料，输入列表发生了变化。那么，为什么大写的列表'path'没有发生变异呢？
def foo_mutating(bar):
bar[0] = bar[0] + [1]
print('bar inside foo:', bar)
if len(bar[0]) == 5:
return bar
return foo_mutating(bar)
def foo_nonmut(bar):
temp_bar0 = bar[0]+[1]
print('bar inside foo:', bar)
if len(temp_bar0) == 5:
return [temp_bar0, bar[1], bar[2]]
return foo_nonmut([temp_bar0, bar[1], bar[2]])
def test():
print('-----TESTING NON-MUTATING----')
bar_init = [[], 22, 33]
print('bar_init:', bar_init)
new_bar = foo_nonmut(bar_init)
print('new_bar:', new_bar)
print('bar_init:', bar_init)
print('\n')
print('-----TESTING MUTATING----')
bar_init = [[], 22, 33]
print('bar_init:', bar_init)
new_bar = foo_mutating(bar_init)
print('new_bar:', new_bar)
print('bar_init:', bar_init)
test()
打印：
-----TESTING NON-MUTATING----
bar_init: [[], 22, 33]
bar inside foo: [[], 22, 33]
bar inside foo: [[1], 22, 33]
bar inside foo: [[1, 1], 22, 33]
bar inside foo: [[1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1], 22, 33]
new_bar: [[1, 1, 1, 1, 1], 22, 33]
bar_init: [[], 22, 33]
-----TESTING MUTATING----
bar_init: [[], 22, 33]
bar inside foo: [[1], 22, 33]
bar inside foo: [[1, 1], 22, 33]
bar inside foo: [[1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1, 1], 22, 33]
new_bar: [[1, 1, 1, 1, 1], 22, 33]
bar_init: [[1, 1, 1, 1, 1], 22, 33]
Why doesn't this recursion mutate the input list?
因为它不是用输入列表调用的，因此没有它可用于变异。
当你进行递归调用时（我重新格式化了一下）：
# "non-mutating" approach, as in the original code
new_path = get_best_path(
digraph, next_node, end, [current_path,new_tot,new_out],
max_dist_outdoors, best_dist, best_path
)
# "mutating" approach, using the commented-out line
new_path=get_best_path(
digraph, next_node, end, [path[0],new_tot,new_out],
max_dist_outdoors, best_dist, best_path
)
尝试改变路径的算法会创建一个传递给递归调用的新列表，因此它不会改变。与玩具示例对比：
# "non-mutating" recursive call
return foo_nonmut([temp_bar0, bar[1], bar[2]])
# "mutating" recursive call
return foo_mutating(bar)
# Notice, it does not make a new list.
一般来说，当您不依赖变异时，递归算法更容易推理。您可能还会发现，通过使用某种 class 来表示路径，您可以获得更清晰、更易于理解的代码。然后你可以为 "create a new path with the specified node appended to the node name list" 和 "create a new path with modified distance data" 提供 class 非变异方法。 （或者更好的是 - 同时，给它一个 Edge 实例，它从中获取所有必要的数据）。
类似于：
class Path:
def __init__(self, names, distance, outdoor):
self._names, self._distance, self._outdoor = names, distance, outdoor
def __contains__(self, node):
return node in self._names
def with_edge(self, edge):
return Path(
# incidentally, you should be using `property`s instead of methods
# for this Edge data.
self._names + [edge.get_destination()],
self._distance + edge.get_total_distance(),
self._outdoor + edge.get_outdoor_distance()
)
def better_than(self, other, outdoor_limit):
if self._outdoor <= outdoor_limit:
return False
best_distance = other._distance
return best_distance is None or best_distance >= self._distance
def end(self): # where we start recursing from during pathfinding.
return self._names[-1]
现在我们可以做更多类似的事情：
# instead of remembering best_path and best_dist separately, we'll just
# use a Path object for best_path, and we can ignore the outdoor distance
# when interpreting the results outside the recursion.
edges = digraph.get_edges_for_node(Node(start))
for edge in edges:
if edge.get_destination() in path:
continue
candidate = path.with_edge(edge)
if candidate.better_than(best_path, max_dist_outdoors):
# We can remove some parameters from the recursive call,
# because we can infer them from the passed-in `path`.
new_path = get_best_path(digraph, end, path, max_dist_outdoors, best_path)
if new_path is not None:
best_path = new_path