时间戳

首页 > 解决方案 > 如何从基于另一个键值对的列表中的字典中访问值？

python - 如何从基于另一个键值对的列表中的字典中访问值？

问题描述

鉴于下面的列表，

graph = [{'Node':'A', 'children':['T','Z','S'], 'gWt':[118,75,140], 'h':366},
         {'Node':'Z', 'children':['O','A'], 'gWt':[71,75], 'h':374},
         {'Node':'T', 'children':['A'], 'gWt':[118], 'h':329},
         {'Node':'S', 'children':['A','O','R','F'], 'gWt':[140,151,80,99], 'h':253}]

对于给定的节点值，我将如何获得它的所有“孩子”？例如，

graph.index('Node'=='S')['children'] -> ['A','O','R','F']

标签： pythonlistdictionary

解决方案

index()使用or的评论next()：

创建节点名称列表，然后使用 查找节点的索引是可行index()的方法，但请注意，这可能会导致性能大幅下降以及逻辑错误。

  • 性能问题：使用list.index(target)is O(n)在列表中查找，这意味着它遍历列表中的每个元素，直到找到与不理想的目标匹配的第一个元素。
  • 逻辑错误：如果你有一个格式错误的图，一个包含两次或更多相同节点名称的列表，例如： ，由于函数graph = [{"node": "A", ...props1}, {"node": "A", ... props2}]的性质，你只会遇到第一个节点。index()如果要查找每个节点"A"，则需要index()遍历所有列表，直到确定已找到所有节点"A"，然后考虑节点属性的合并策略。

 解决方案（推荐）：

使用字典存储图的节点。字典具有恒定的时间查找 ( O(1) )，因为它们是哈希表。您希望实现的表示是：

graph = {
    "A": {'children':['T','Z','S'], 'gWt':[118,75,140], 'h':366},
    "B": {'children':['O','A'], 'gWt':[71,75], 'h':374},
    ...
}

这也将使您的图表的遍历变得超级容易。这样，每当您在寻找节点时，"X"您只需要graph["X"]获取它，并graph["X"]["children"]获取它的子节点。

 如何将给定的输入转换为最优的数据结构？

如果您无法构建上述数据结构，那么如果您计划不断查询图形的节点属性，那么您肯定希望将其转换为最佳结构。您可以通过以下方式实现：

def transform_graph(graph):
    new_graph = {}
    for node in graph:
        node_name = node['Node']
        new_graph[node_name] = new_graph.get(
            node_name,
            {'children': set(), 'gWt': set(), 'h': 0}
        )
        new_graph[node_name]["children"] |= set(node['children'])
        new_graph[node_name]["gWt"] |= set(node["gWt"])
        new_graph[node_name]["h"] = node["h"]
    return new_graph

调用函数的输出transform_graph(old_graph)是

old_graph = [
    {'Node':'A', 'children':['T','Z','S'], 'gWt':[118,75,140], 'h':366},
    {'Node':'Z', 'children':['O','A'], 'gWt':[71,75], 'h':374},
    {'Node':'T', 'children':['A'], 'gWt':[118], 'h':329},
    {'Node':'S', 'children':['A','O','R','F'], 'gWt':[140,151,80,99], 'h':253}
]
new_graph = transform_graph(old_graph)
print(new_graph)

> {
    'A': {'children': {'S', 'T', 'Z'}, 'gWt': {75, 118, 140}, 'h': 366},
    'Z': {'children': {'A', 'O'}, 'gWt': {71, 75}, 'h': 374},
    'T': {'children': {'A'}, 'gWt': {118}, 'h': 329},
    'S': {'children': {'A', 'F', 'O', 'R'}, 'gWt': {80, 99, 140, 151}, 'h': 253}
}

推荐阅读