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

标签 python for-loop nested-loops

我正在使用以下格式迭代 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 复杂度或类似的东西。有没有办法简化或编码以获得更好的性能?

最佳答案

您显然具有从子级到父级的映射关系。我能想到的最简单的事情就是用 child 作为 key 来制定一个字典。如果您遇到已存在的子项,请检查父项值。

查找和插入在恒定时间内发生(字典键实际上是一个哈希集)。您还可以更有效地使用短路,因为您可以在发现有多个 parent 的 child 时立即停止:

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 对每个子元素执行恒定时间(理想情况下)操作。

关于Python - 比嵌套 for 循环更好的迭代复杂列表的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51739253/

相关文章:

python - 将列表从一个 Dataframe 行映射到另一个 Dataframe 行的矢量化方法

python - 如何让PyQT4窗口跳到最前面?

结合三个二维数组的 JavaScript,保持第一个值唯一

arrays - 在 Swift 中更新数组中的字符串数量

c - c中的While循环递增

java - 为什么嵌套 Java 循环执行得非常快

python - 导入错误: No module named authentication

python - Matplotlib 堆叠条形图,具有类似于 pgfplots 的单独边缘颜色

java - 如何在表中编写行索引和列索引(java) - 嵌套for循环

c++ - 为什么这个 C++ for 循环的执行时间有显着差异?