Я пытаюсь выполнить задачу как часть более крупного проекта на своем рабочем месте, и у меня есть рабочее решение проблемы, но из-за временной сложности решения для выполнения задачи требуется неоправданно много времени ( длина фрейма данных составляет несколько миллионов). Это не одноразовая задача, и ее нужно запускать ежедневно.
Цель: дана таблица с двумя столбцами: 'a' и 'b', где 'a' имеет одиночные строки в качестве значений и 'b' имеет список строк в качестве значений, объедините строки, где элемент в строке 'b' совпадает с элементом в 'b' других строк, так что 'a' и 'b' в объединенной таблице будут списком элементов.
Пример 1:
Таблица ввода:
a b
0 1 [a, b, e]
1 2 [a, g]
2 3 [c, f]
3 4 [d]
4 5 [b]
Требуемый вывод:
a b
0 [1, 2, 5] [a, b, e, g]
1 [3] [c, f]
2 [4] [d]
Пример 2:
Таблица ввода:
a b
0 1 [a, b, e]
1 3 [a, g, f]
2 4 [c, f]
3 6 [d, h]
4 9 [b, g, h]
Требуемый вывод:
a b
0 [1, 3, 4, 6, 9] [a, b, c, d, e, f, g, h]
У меня есть рабочее решение:
import pandas as pd
def merge_rows(df):
df_merged = pd.DataFrame(columns=df.columns)
matched = False
while len(df) > 0:
if not matched:
x = len(df_merged)
df_merged.loc[x, 'a'] = list(df.iloc[0, 0])
df_merged.loc[x, 'b'] = df.iloc[0, 1]
df = df.iloc[1:, :]
for rm in range(len(df_merged)):
matched = False
right_b_lists_of_lists = df.b.tolist()
df.reset_index(drop=True, inplace=True)
match_index_list = [i for b_part in df_merged.loc[rm, 'b'] for (i, b_list) in enumerate(right_b_lists_of_lists) if b_part in b_list]
df_matches = df.loc[match_index_list]
if len(df_matches) > 0:
df_merged.loc[rm, 'a'] = list(set(df_merged.loc[rm, 'a'] + df_matches.a.tolist()))
df_merged.loc[rm, 'b'] = list(set(df_merged.loc[rm, 'b'] + [item for sublist in df_matches.b.tolist() for item in sublist]))
df = df.drop(df_matches.index)
matched = True
break
return df_merged
df1 = pd.DataFrame({'a': ['1', '2', '3', '4', '5'], 'b': [['a', 'b', 'e'], ['a', 'g'], ['c', 'f'], ['d'], ['b']]})
df1_merged = merge_rows(df1)
print('Original DF:')
print(df1.to_string())
print('Merged DF:')
print(df1_merged.to_string())
df2 = pd.DataFrame({'a': ['1', '3', '4', '6', '9'], 'b': [['a', 'b', 'e'], ['a', 'g', 'f'], ['c', 'f'], ['d', 'h'], ['b', 'g', 'h']]})
df2_merged = merge_rows(df2)
print('Original DF:')
print(df2.to_string())
print('Merged DF:')
print(df2_merged.to_string())
Приведенный выше код печатает следующее:
Original DF:
a b
0 1 [a, b, e]
1 2 [a, g]
2 3 [c, f]
3 4 [d]
4 5 [b]
Merged DF:
a b
0 [1, 2, 5] [e, b, a, g]
1 [3] [c, f]
2 [4] [d]
Original DF:
a b
0 1 [a, b, e]
1 3 [a, g, f]
2 4 [c, f]
3 6 [d, h]
4 9 [b, g, h]
Merged DF:
a b
0 [4, 3, 6, 9, 1] [e, h, c, g, f, d, b, a]
Обратите внимание, что списки в 'a' и 'b' в выводе из приведенного выше кода не отсортированы, но это приемлемо.
Это решение практически неосуществимо с учетом асимптотики c временная сложность O (n ^ 2) как средний случай для решения, наряду с невозможностью придумать способ распараллеливания этого полиномиального решения, большой размер n, что мне нужно запускать его ежедневно, и машина, на которой я должен его запускать.
Любая помощь с решением linearithmi c или a распараллеливаемое полиномиальное решение (или лучше!) было бы очень признательно!
Решение Python является предпочтительным, но я приветствовал бы решение в R / C / C ++ / Java / стр.