Python

Question

我正在使用以下格式迭代 python 中的复杂列表：

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

列表将以字典作为元素。这些字典具有 <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 在两个字典元素中，但所有子 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 复杂度或类似的东西。有没有办法对此进行简化或编码以获得更好的性能？

Answer 1

你确定这是 O(3) 复杂度吗？关于什么？

这段代码对你来说太慢了吗？如果你想浏览所有 childs，除了像这样遍历它们之外真的没有别的了。

不过。考虑设置 unique_parent_list 和 child_list 而不是列表。这可能会使 in 检查速度更快（O(log(n) 与 O(1) 相比）。但如果你关心的话，你应该分析一下，看看情况是否如此。

如果在 [=11] 中输入 children 时检查条件，您也可以在发现重复 child 时尽早退出（如果格式不正确） =].

Answer 2

你明明有child到parent的映射关系。我能想到的最简单的事情就是用 children 作为键来制作一个字典。如果您遇到已经存在的 child，请检查 parent 值。

查找和插入在恒定时间内发生（dict 键实际上是一个哈希集）。您还可以更有效地使用短路，因为您可以在找到具有多个 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

这将每个 child 迭代一次，并使用 dict.setdefault.

对每个执行 constant-time（理想情况下）操作

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

Python - Better way to iterate complex list than nested for loops

for-loop

nested-loops