有多个点头的树（Python）

Question

我希望你能帮助我，我的作业很卡。

为此，我有 JSON 格式的数据，其中包含下一个需要哪些组件的多个条目。它们以以下格式显示：

{‘id’ : 123, ‘ needed’ 1, ‘need_id’: None},
{‘id’ : 100, ‘ needed’ 2, ‘need_id’: 123},
{‘id’ : 101, ‘ needed’ 3, ‘need_id’: 123},
{‘id’ : 105, ‘ needed’ 3, ‘need_id’: 123},
{‘id’ : 210, ‘needed’ 5, ‘need_id’: 101},
{‘id’ : 999, ‘needed’ 2, ‘need_id’: 210},

因此，从不需要任何其他 ID 的 ID 开始，它们拆分为 'nods'，其中每个组件都有更多的组件。

看起来像

ID:123   (1 component)
|             |      |
|             |      |
ID:100     ID:101   ID:105
(2 com)    (3 com)  (3 com)
             |
             |
           ID:210
           (15 components total)
             |
             |
           ID:999
           (30 components total)

因此 ID 210 将有 15 个组件，因为每个 ID 101 需要 5 个组件。相应地，ID 999 将需要 30 个组件。

实际上，这棵树会更宽，需要很多组件才能从上层分支创建组件。

我不确定哪种算法可以最快地遍历整个列表（100 JSON 行）然后计算每个组件的需求。

我正在考虑将每个对象作为一个对象存储在具有所需组件值的子节点列表中，但这可能需要太多迭代。任何语言都可以提供帮助，python 就足够了，但不限于 python.

非常感谢任何输出！

Answer 1

如果您仍在寻找解决方案：

我假设您实际上是在处理一棵树（或一片森林）并且您的数据按以下形式组织：

data = [
    {'id': 123, 'needed': 1, 'need_id': None},
    {'id': 100, 'needed': 2, 'need_id': 123},
    {'id': 101, 'needed': 3, 'need_id': 123},
    {'id': 105, 'needed': 3, 'need_id': 123},
    {'id': 210, 'needed': 5, 'need_id': 101},
    {'id': 999, 'needed': 2, 'need_id': 210},
]

第一步是预处理：在字典中组织树 tree，从而向节点添加子视图（输入只有父视图），并将根收集到一个集合中roots:

tree = {}
for node in data:
    i, needed, parent = node.values()
    tree[i] = {"needed": needed, "parent": parent, "childs": []}
roots = set()
for i, d in tree.items():
    parent = d["parent"]
    if parent is not None:
        tree[parent]["childs"].append(i)
    else:
        roots.add(i)

现在您可以遍历树（此处以深度优先的方式）并相应地更新所需的组件：

for root in roots:
    stack = [root]
    while stack:
        node = stack.pop()
        needed = tree[node]["needed"]
        for child in tree[node]["childs"]:
            tree[child]["needed"] *= needed
            if tree[child]["childs"]:
                stack.append(child)

示例数据的结果：

{100: {'childs': [], 'needed': 2, 'parent': 123},
 101: {'childs': [210], 'needed': 3, 'parent': 123},
 105: {'childs': [], 'needed': 3, 'parent': 123},
 123: {'childs': [100, 101, 105], 'needed': 1, 'parent': None},
 210: {'childs': [999], 'needed': 15, 'parent': 101},
 999: {'childs': [], 'needed': 30, 'parent': 210}}

我确定这可以优化，但我的重点是透明度。

有多个点头的树（Python）

Tree with multiple nods for counting (Python)

python

algorithm

tree

data-structures