我希望你能幫助我，我被我的任務困住了。
對于它，我有 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 開始，他們拆分為“點頭”，其中每個都有更多的組件。
那看起來像
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。
任何輸出真的很感激！
uj5u.com熱心網友回復：
如果您仍在尋找解決方案：
我假設您實際上正在處理一棵樹（或森林），并且您的資料按以下形式組織：
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}}
我確信這可以優化，但我在這里的重點是透明度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/325468.html
上一篇：這個演算法的復雜度是多少？
下一篇：從塊引數動態創建方法