python - 不明白这个字典在迭代错误期间改变了大小

Question

这个问题已经有答案了:

How to solve dictionary changed size during iteration error? (9 个回答)

已关闭 3 年前。

我正在尝试执行下面的代码，但它给了我 RuntimeError: dictionary changed size during iteration即使我没有删除 key 。

有人可以帮我理解我哪里做错了吗？

这是针对 Python 3 的。

from collections import defaultdict
class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        def create_graph():
            for course in prerequisites:
                child, pare = course[0], course[1]
                graph[child].append(pare)

        graph = defaultdict(list)
        create_graph()

        def topological_order(node):

            visited.add(node)
            visiting.add(node)

            for nei in graph[node]:
                if nei in visiting:
                    return False
                if nei not in visited:
                    rs = topological_order(nei)
                    if not rs:
                        return False

            visiting.remove(node)
            result.append(node)
            return True


        result = []
        visited = set()
        visiting = set()

        for nd in graph.keys():
            if nd not in visited:
                rs = topological_order(nd)
                if not rs:
                    return []

        return result

obj = Solution()
print( obj.findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) )

Answer 1

您正在使用默认字典。

如果您使用尚不存在的 key 访问它，它将创建该 key 并添加 [] 作为默认值。

调试代码时，当使用键 1 的 0 值递归到 rs = topological_order(0) 中，然后将其作为键进行迭代时，会发生这种情况在 for nei in graph[0]: 中创建 {0:[]}。

    def topological_order(node):

        visited.add(node)
        visiting.add(node)

        for nei in graph[node]:      # this line adds unknown keys with default value []
            if nei not in visited:
                rs = topological_order(nei)
                if not rs:
                    return False

这发生在迭代时

for nd in graph.keys(): # first key is 1
    if nd not in visited:
        rs = topological_order(nd) # calls it with 1 then inside recurses on 0 which 
                                   # modifies the dictionary.
        if not rs:
            return []

return result

您可以通过先检查 if 来防止它，如果不存在则不访问 key 。不确定这对于您尝试做的事情是否有意义。

您可以对字典键的副本进行操作:

    for nd in list(graph.keys()):
        if nd not in visited:
            rs = topological_order(nd)
            if not rs:
                return []

    return result

这将忽略添加的键 - 不确定这是否有帮助。