Дедупликация набора данных со сложными отношениями - PullRequest
Новая
       8

Дедупликация набора данных со сложными отношениями

0 голосов
/ 13 апреля 2020

Для решения следующей проблемы я ищу решение, которое быстро работает с очень большим набором данных и работает. У меня есть доступ к инфраструктуре блоков данных, и я могу писать в SQL и Python (pyspark) взаимозаменяемо. Проблема заключается в следующем: в наборе данных примерно 1 м строк в следующем формате. 

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 - Найти root родителей для каждого члена семьи 

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, который представляет отношения и попытку, которую я предпринял, чтобы найти результат 1, работает, но невероятно медленно, возможно, из-за рекурсивной функции. Моя проблема в том, что этот подход очень медленный для большого количества данных, и я не уверен, какие инструменты, которые у меня есть, лучше всего подходят для решения этой проблемы. Pandas? Scala? Чистый 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)

1 Ответ

0 голосов
/ 13 апреля 2020

Я нашел свой ответ в этом ответе 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))

Out: 

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