时间戳

首页 > 解决方案 > 迭代期间字典大小更改（运行时错误）

python - 迭代期间字典大小更改（运行时错误）

问题描述

我得到 RuntimeError: dictionary changed size during iteration，我浏览了一些堆栈溢出帖子，发现当您在字典循环（插入/删除）时修改字典的大小时会发生这种情况。

但是，就我而言，我只是在遍历字典，所以我不确定为什么会出现错误。

我发现在使用非集合字典时我没有遇到任何问题，但这使得添加新顶点比使用集合复杂得多。

我知道我可能可以制作字典的深层副本并对其进行迭代，但我想首先了解为什么我首先会收到此错误。

我在下面的示例中删除了大部分非必要的代码。

from collections import defaultdict 


class Graph: 

    def __init__(self,vertices): 

        self.graph = defaultdict(list)  

    def addEdge(self,u,v): 
        self.graph[u].append(v) 

    def fillOrder(self,v,visited, stack): 

        visited.add(v)
        for neighbour in self.graph[v]:
          if neighbour not in visited:
            self.fillOrder(neighbour, visited, stack)
        stack.append(v)


    def printSCCs(self): 

        stack = [] 

        visited = set()

        for key in self.graph:
          print(key)
          self.fillOrder(key, visited, stack)

g = Graph(5) 
g.addEdge(1, 0) 
g.addEdge(0, 2) 
g.addEdge(2, 1) 
g.addEdge(0, 3) 
g.addEdge(3, 4) 
g.printSCCs()

我希望不会抛出任何错误，并且堆栈将被图中的顶点填充。

标签： pythonpython-3.xdictionaryrecursion

解决方案

defaultdict如果您尝试访问不存在的条目，则您在隐式插入中使用so 。

尤其是：

def fillOrder(self,v,visited, stack): 
    # ...
    for neighbour in self.graph[v]:
        # ...

不能保证您的密钥v存在，因此访问self.graph[v]会导致将新条目添加到字典中。如果您将 替换defaultdict为普通字典并按需创建新列表，addEdge那么失败的原因就更明显了：

1
Traceback (most recent call last):
  File "test.py", line 38, in <module>
    g.printSCCs()
  File "test.py", line 30, in printSCCs
    self.fillOrder(key, visited, stack)
  File "test.py", line 21, in fillOrder
    self.fillOrder(neighbour, visited, stack)
  File "test.py", line 21, in fillOrder
    self.fillOrder(neighbour, visited, stack)
  File "test.py", line 21, in fillOrder
    self.fillOrder(neighbour, visited, stack)
  File "test.py", line 19, in fillOrder
    for neighbour in self.graph[v]:
KeyError: 4

如果您想保证两个边缘端点都在字典中，您可能需要修改addEdge以执行此操作：

self.graph[u].append(v) 
self.graph[v].append(u)

推荐阅读