dict[new_key] = [dict[key], new_value] 和 x = dict[key] + [new_value] 有什么区别？

Question

我正在阅读关于图形实现的 Python 模式论文，并看到了讨论寻找最短路径的最佳实现的部分。文章是here.

我无法理解 dist[next] 的两个作业之间的区别；后者在运行时是二次的，而前者是线性的？

线性运行时间：

# Code by Eryk Kopczyński 
def find_shortest_path(graph, start, end):
    dist = {start: [start]}
    q = deque(start)
    while len(q):
        at = q.popleft()
        for next in graph[at]:
            if next not in dist:
                dist[next] = [dist[at], next]  # this line
                q.append(next)
    return dist.get(end)

二次运行时间：

# Code by Eryk Kopczyński 
def find_shortest_path(graph, start, end):
    dist = {start: [start]}
    q = deque(start)
    while len(q):
        at = q.popleft()
        for next in graph[at]:
            if next not in dist:
                dist[next] = dist[at] + [next]  # this line
                q.append(next)
    return dist.get(end)

有人可以解释一下这两个作业之间的区别吗？

Answer 1

[ ] 括号符号用于两者下标 de-reference 以及构建列表。

您问的是这些表达式：

            dist[next] = [dist[at], next]

            dist[next] = dist[at] + [next]

让我们忽略赋值的左手边，因为它只是存储一个字典映射。而不是 dist[next] = ... 它本来可以很容易地 x = ... 其次是 dist[next] = x.

同样，在 RHS 中，让我们忽略 dist[at]。我们可以很容易地预先设置一个临时变量：y = dist[at]，然后在表达式中使用 y。

好吧，除了方括号符号，让我们关注构造 [y, next] 和 y + [next] 表达式的算法复杂性，其中 y 是一个列表。

我们可以在 O(1) 常数时间内计算第一个表达式。我们简单地分配一个短列表并填写它前两个元素指向 y 和 next 对象。

第二个列表表达式y + [next]需要扫描y的每个元素并将其复制到新的临时结果中，然后最后将 next 指针附加到该结果。这具有 O(n) 线性成本，如果 y 的长度为 n.

说明

为什么需要额外的工作？好吧，假设 y 的一个元素随后发生变异，更改为一个新值。第一个表达式很好，它将反映新值，由于程序员要求在列表中存储一个指针，因此引用了 y 指向的内容。

OTOH 第二个表达式不会保留该关系，它只查看 + 加号两侧的 values。想象一下，我们存储那个“大列表”结果，然后变异 y。大榜单不会有影响，这是理所应当的。

dict[new_key] = [dict[key], new_value] 和 x = dict[key] + [new_value] 有什么区别？

What is the difference between dict[new_key] = [dict[key], new_value] and x = dict[key] + [new_value]?

python

list