python - Python-比嵌套循环更好的迭代复杂列表的方法

我正在用这种格式在python中迭代一个复杂的列表：

[
  {
    <parent id>: [
      <child id>,
      <child id>
    ],
    <parent id>: [
      <child id>
    ]
  },
  {
    <parent id>: [
      <child id>,
      <child id>,
      <child id>
    ],
    <parent id>: [
      <child id>
    ]
  }
]

该列表将把dict作为元素。这些字典具有<parent id>的键和<child id>列表的值

不同的字典中可以有相同的<parent id>，但是<child id>只能属于一个<parent id>。一个例子是这样的：

[
  {
    2: [1, 5],
    3: [3, 7],
    4: [6]
  },
  {
    1: [2, 4, 8],
    4: [6]
  }
]

父id 4在两个dict元素中，但是所有子ID对父ID都是唯一的。

现在，我要迭代此数据结构作为输入，因为我想确保满足所有子代对父代ID唯一的条件。这是我的代码：

def check_format(self, mapping):
    # mapping is the data structure
    unique_parent_list = []
    child_list = []

    for x in range(0, 2):
        for parent in mapping[x].keys():
            if parent not in unique_parent_list:
                unique_parent_list.append(parent)
                for child in mapping[x][parent]:
                    child_list.append(child)
    if len(child_list) > len(set(child_list)):
        return 'Condition not met'
    else:
        return 'Condition met'

这可行，但是我不喜欢O ^ 4复杂性之类的。有没有一种方法可以简化或编码以获得更好的性能？

最佳答案

您显然具有从孩子到父母的映射关系。我能想到的最简单的事情就是以孩子为键来做出命令。如果遇到已经在里面的孩子，请检查其父值。

查找和插入发生在恒定的时间（字典键实际上是哈希集）。您也可以更有效地使用短路功能，因为这样一来，您就可以停止寻找有多个父母的孩子：

def check_format(map_list):
    check = {}
    for parent, children in (i  for d in map_list for i in d.items()):
        for child in children:
            if check.setdefault(child, parent) != parent:
                return False
    return True

这将为每个孩子精确地迭代一次，并使用dict.setdefault对每个孩子执行恒定时间（理想情况下）的操作。