我有一个从webapi检索到的dict数组。每个dict都有一个name
、description
、“parent”和children
键。children
键的值是dict数组。为了清楚起见,下面是一个虚拟示例:
[
{'name': 'top_parent', 'description': None, 'parent': None,
'children': [{'name': 'child_one'},
{'name': 'child_two'}]},
{'name': 'child_one', 'description': None, 'parent': 'top_parent',
'children': []},
{'name': 'child_two', 'description': None, 'parent': 'top_parent',
'children': [{'name': 'grand_child'}]},
{'name': 'grand_child', 'description': None, 'parent': 'child_two',
'children': []}
]
数组中的每一项。项可以是最顶层的父项,因此不存在于children
数组中。一个项既可以是子项,也可以是父项。或者一个项目只能是子项目(没有自己的子项目)。在
所以,在树状结构中,你会得到这样的结果:
^{pr2}$在这个精心设计和简化的示例中,top_parent
是父项而不是子项;child_one
是子项而不是父项;child_two
是父项和子项;grand_child
是子项而不是父项。这涵盖了所有可能的状态。在
我想要的是能够在dicts数组上迭代1次,并生成一个恰当地表示树结构的嵌套dict(但是,一次迭代是不可能的,这是最有效的方法)。因此,在这个例子中,我会得到一个如下所示的dict:
{
'top_parent': {
'child_one': {},
'child_two': {
'grand_child': {}
}
}
}
严格地说,没有必要让没有孩子的项目不成为钥匙,但这是最好的。在
您可以保留从名称到节点的延迟映射,然后通过只处理
parent
链接来重建层次结构(我假设数据是正确的,因此如果A
被标记为B
iffB
将列在A
的子级中)来重建层次结构。在输入的
children
属性仅用于知道元素是否应作为None
存储在其父元素中(因为没有子元素),还是因为在重建过程结束时它将有子元素而应该是字典。将没有子节点的节点存储为空字典可以避免这种特殊情况,从而简化代码。在使用
^{pr2}$collections.defaultdict
还可以简化代码以创建新节点此算法是
O(N)
假设时间不变的字典访问,只对输入进行一次传递,并且需要O(N)
空间作为name->;节点映射(对于原始的nochildren->None
版本,空间需求是O(Nc)
,其中Nc
是具有子节点的节点数)。在第四次编辑,显示了三个版本,清理了一点。第一个版本自上而下工作,并按您的要求返回None,但实际上在顶级数组中循环3次。下一个版本只循环一次,但返回空dicts而不是None。在
最终版本是自下而上的,非常干净。它可以通过单个循环返回空dict,也可以通过附加循环返回空dict:
结果:
^{pr2}$我的刺:
结果:
^{pr2}$它还提取任何父对象尚未添加的子对象,然后在最后进行协调。在
相关问题 更多 >
编程相关推荐