python - 加法和 += 给出列表的不同结果(深度优先搜索)

Question

我一直试图理解深度优先搜索，并使用各种在线资源获得了以下代码:

graph = {'A': ['B', 'D'], 'B': ['E'], 'C': [], 'D': ['C', 'E'], 
         'E': ['H', 'I', 'J'], 'F': [], 'G': [], 'H': ['F'], 
         'I': [], 'J': ['G']}

def dfs(graph, start, end, path=None):
    if path == None:
        path = []
    path = path + [start]
    paths = []
    if start == end:
        return [path]
    for neighbour in graph[start]:
        if neighbour not in path:
            paths.extend(dfs(graph, neighbour, end, path))
    return paths

print(dfs(graph, 'A', 'G'))

这将输出所需的结果:

[['A', 'B', 'E', 'J', 'G'], ['A', 'D', 'E', 'J', 'G']]

但是当我用 path += [start] (或 path.extend([start]) 替换 path = path + [start] 行时，据我所知做同样的事情)我得到以下输出:[['A', 'B', 'E', 'H', 'F', 'I', 'J ', 'G', 'D', 'C']]

我知道这与操作的不同有关，但我真的不明白它在这里如何应用。请问有人可以解释一下吗？

Answer 1

这个

path = path + [start]

与

略有不同

path += [start]  # or path.extend([start])

for lists (和其他可变类型)因为它重新创建了一个新的 path 引用(隐含你想要的，你不想写入以前的引用)

path += [start]  # or path.extend([start])

重复使用相同的引用，因为您在循环中多次传递 path(没有制作副本):

for neighbour in graph[start]:
    if neighbour not in path:
       paths.extend(dfs(graph, neighbour, end, path))

因此，如果其他某个对象将其存储在存储中，您将更改两个列表:行为不同，而不是您想要的行为。

当然你可以做 paths.extend(dfs(graph, neighbor, end, path.copy())) 但这将违反对调用者的最小惩罚原则(这不'期望修改最后一个参数)

我的建议:

• 如果您想要性能并且不关心是否重用引用，请始终对列表使用 +=，因为它只是扩展了列表。 + 运算符创建一个新的列表和副本，这真的很慢。
• 在 list 类型中使用 path = path + something 时，请始终为 future 的维护者(包括您自己!)添加注释不要优化 使用 +=。

也许一些更明确和等效的代码:

path = path.copy() # or path[:], or list(path)...: force creation of a new reference to break dependency with passed parameter
path += [start]

另请注意:它不适用于 str 或 tuple 类型，因为即使 += 也会创建一个新引用，因为字符串不变性。没有与字符串共享引用的风险，因此在这里使用 tuple 而不是 list 也可以修复它:

if path == None:
    path = tuple()
path += (start,)  # += creates a new path reference, cos path is a tuple, immutable

(但不要指望使用 += 会获得更多性能，在这种情况下，会生成副本)