python - 对具有复杂关系的数据集进行重复数据删除

Question

对于以下问题，我正在寻找一种在大量数据上快速且有效的解决方案。我可以访问 databricks 基础设施，并且可以交替使用 SQL 和 Python (pyspark) 编写代码。问题如下——给定一个大约 1m 行的数据集，格式如下。

duplicate  parent
2          1
3          1
4          1
5          2
3          2
2          6
2          7
3          7
8          9
10         12
11         8
15         14
13         15
14         10

我从火花表中获取这些数据。我现在试图得到两个结果：

1 - 找到每个家庭成员的根父母

member    parent
1         []
2         [1,7]
3         [1,7]
4         [1]
5         [1,7]
6         [1,7]
7         []
8         [9]
9         []
10        [12]
11        [9]
12        []
13        [12]
14        [12]
15        [12]

2 - 将所有亲子关系汇集到“家庭”中

family
[1,2,3,4,5,6,7]
[8,9,11]
[10,12,13,14,15]

这是一个代表关系的 Python dict，我尝试解决结果 1 的工作但速度非常慢，可能是由于递归函数。我的问题是这种方法在处理大量数据时非常缓慢，我不确定我拥有的哪些工具最适合解决这个问题。熊猫？斯卡拉？纯Python？

test = {
  'duplicate':[2,3,4,5,3,2,6,3,8,10,11,14,15,14],
  'parent':[1,1,1,2,2,6,7,7,9,12,8,15,13,10]
}

result = {
  'root_parent': [],
  'duplicate': []
}

parents = test['parent']
duplicates = test['duplicate']

def find_parents(root_duplicate, duplicate, result):
  parents_of_duplicate = [parents[i] for i, x in enumerate(duplicates) if x == duplicate]
  if not parents_of_duplicate:
    result['root_parent'].append(duplicate)
    result['duplicate'].append(root_duplicate)
  else:
    for parent_of_duplicate in parents_of_duplicate:
      find_parents(root_duplicate, parent_of_duplicate, result)

for duplicate in set(duplicates):
  find_parents(duplicate, duplicate, result)

标签： pythonpandaspysparkapache-spark-sqldatabricks

Answer 1

我在这个 Stackoverflow 响应中找到了我的答案。似乎是一个常见的图形问题：

合并共享共同元素的列表

import networkx as nx
test = {
  'duplicate':[2,3,4,5,3,2,6,3,8,10,11,14,15,14],
  'parent':[1,1,1,2,2,6,7,7,9,12,8,15,13,10]
}
relations = zip(test['duplicate'], test['parent'])
G = nx.Graph()
G.add_edges_from(relations)
list(nx.connected_components(G))

出去：

[{1, 2, 3, 4, 5, 6, 7}, {8, 9, 11}, {10, 12, 13, 14, 15}]