python - 从大型 JSON 文件创建树状结构的最有效方法

Question

我有一个如下所示的大型 JSON 文件:

[(3, (2, 'Child')), (2, (1, 'Parent')), (1, (None, 'Root'))]

其中每个元素的键是该元素的唯一索引，值对中的第一个元素表示其父元素的索引。

现在，最终目标是将这个 JSON 文件转换为以下内容:

[(3, (2, 'Child Parent Root')), (2, (1, 'Parent Root')), (1, (None, 'Root'))]

其中每个项目的值对中的第二个元素将被修改，以便它具有直到其根祖先的所有值的串联。

没有。级别不固定，最多可达 256。我知道我可以通过创建树 DS 并遍历它来解决这个问题，但问题是 JSON 文件很大(列表中几乎有 180M 项)。

关于如何有效地实现这一目标有什么想法吗？涉及 Apache Spark 的建议也很好。

Answer 1

您可以使用广度优先搜索来查找所有祖先元素链:

from collections import deque, defaultdict
d, d1 = [(3, (2, 'Child')), (2, (1, 'Parent')), (1, (None, 'Root'))], defaultdict(list)
for a, (b, c) in d:
   d1[b].append((a, c))

q, r = deque([(1, d1[None][0][1])]), {}
while q:
   r[n[0]] = (n:=q.popleft())[1]
   q.extend([(a, b+' '+n[1]) for a, b in d1[n[0]]])

现在，r 存储每个元素的祖先值:

{1: 'Root', 2: 'Parent Root', 3: 'Child Parent Root'}

然后，使用列表理解来更新d:

result = [(a, (b, r[a])) for a, (b, _) in d]

输出:

[(3, (2, 'Child Parent Root')), (2, (1, 'Parent Root')), (1, (None, 'Root'))]

诸如 BFS 之类的迭代方法将消除在非常大的图上运行 DFS 时可能发生的RecursionError 的可能性。