Как оптимизировать рекурсивные вызовы функций и внутренние циклы в пандах?

Question

Я хочу найти всех родителей конкретного ребенка из данных.Мой текущий код занимает более 20 секунд, чтобы скомпилировать для набора данных 3000 точек данных.Я подумал, что это из-за рекурсивных вызовов функций и циклов, которые я использовал.Можете ли вы помочь мне оптимизировать программу?

Я пытался найти родительский элемент дочернего узла, распечатать его и предположить, что он является дочерним.Затем рекурсивно найдите его родитель и т. Д., Пока все родители не будут найдены исчерпывающе.

df = pd.DataFrame(
    {
        'parent_name': 
    ["Car","Tyre","Tyre","Rubber","Nylon","Nylon","Trees","Trees"],
    'child_name': ["Tyre","Rubber","Nylon","Trees","Chemicals","Man-made","Leaves","Stems"]
    }
)

Определите функцию, используя все это, чтобы найти все родительские узлы

def get_parent_list(node_id):

    list_of_parents = []  

#define a function to find parent_names for all child_names   
    def find_parent(node_id):

       parent_names = df.loc[df["child_name"].isin([node_id]),"parent_name"]

       for parent_name in parent_names:
          list_of_parents.append(parent_name)
          find_parent(parent_name)

       find_parent(node_id)
       return list_of_parents

  df["list_of_parents"] = df["child_name"].apply(get_parent_list)

Я буду хранить полученный результатв виде отдельного столбца на фрейме данных

После этого я просто выполнил бы поиск в фрейме данных для пользовательского ввода и отобразил бы соответствующий столбец списка родителей в качестве вывода

Ожидается OutPut:

если пользователь вводит: "Деревья" в качестве входных данных

вывод: Деревья: резина, шина, автомобиль

Answer 1

Наиболее естественным здесь является использование древовидной структуры данных, которая будет иметь линейное время запроса.Хотя я удивлен, что ваш подход был таким медленным, так как 3000 точек данных невелики.

import pandas as pd
from treelib import Tree

df = pd.DataFrame(
    {
        "parent_name":
            ["Car", "Tyre", "Tyre", "Rubber", "Nylon", "Nylon", "Trees", "Trees"],
        "child_name": ["Tyre", "Rubber", "Nylon", "Trees", "Chemicals", "Man-made", "Leaves", "Stems"]
    }
)

tree = Tree()
tree.create_node(df["parent_name"][0], df["parent_name"][0])  # root
for i, row in df.iterrows():
    tree.create_node(row["child_name"], row["child_name"], parent=row["parent_name"])
tree.show()

def find_parents(child_name):
    child = tree[child_name]
    parent_names = []
    while child.bpointer is not None:
        parent = tree[child.bpointer]
        parent_names.append(parent.identifier)
        child = parent

    return parent_names


print(find_parents("Trees"))
df["list_of_parents"] = df["child_name"].apply(find_parents)

Примечание: если вы измените фрейм данных, вам придется воссоздать дерево перед повторным вызовом функции "find_parents",Если вы регулярно изменяете фрейм данных, вы можете восстановить дерево внутри функции find_parents.

РЕДАКТИРОВАТЬ: Привет @AkshayKannan, извините за поздний ответ.Поскольку некоторые узлы могут иметь несколько родителей, правильная структура, которую следует здесь использовать, - это не дерево, а ориентированный ациклический граф (DAG).Следующее должно работать (я добавил строку («Нейлон», «Листья»), чтобы проверить случай с несколькими родителями)

import pandas as pd
import networkx as nx

df = pd.DataFrame(
    {
        "parent_name":
            ["Car", "Tyre", "Tyre", "Rubber", "Nylon", "Nylon", "Trees", "Trees", "Nylon"],
        "child_name": ["Tyre", "Rubber", "Nylon", "Trees", "Chemicals", "Man-made", "Leaves", "Stems", "Leaves"]
    }
)

G = nx.DiGraph()
for i, row in df.iterrows():
    G.add_edge(row["child_name"], row["parent_name"])

nx.draw(G, with_labels=True)


def find_parents(child_name):
    return list(nx.descendants(G, child_name))


print(find_parents("Car"))
print(find_parents("Chemicals"))
print(find_parents("Leaves"))