Поиск дочерних строк в одном DataFrame без использования циклов - PullRequest
Новая
       0

Поиск дочерних строк в одном DataFrame без использования циклов

1 голос
/ 22 февраля 2020

В настоящее время я пытаюсь извлечь значимые данные из системы заявок (Redmine). Одна из моих задач - найти все дочерние билеты из списка билетов, которые меня интересуют. Поскольку дети имеют ту же форму, что и их родители, живут в одном и том же DataFrame - поэтому я не могу использовать pd.merge, и, кроме того, у ребенка могут быть дети сами, я сначала попытался найти их рекурсивно, но довольно быстро наткнулся на

ошибка превышения максимальной глубины рекурсии

Поэтому мой следующий подход заключался в том, чтобы вместо этого сериализовать процедуру. К сожалению, это заставляет меня искать такие билеты несколько раз во вложенных циклах, что на самом деле слишком медленно для моих нужд. Чтобы не переутомлять ваше воображение, вот возможный пример данных, над которыми я работаю: 

            id  project.id  status.id  priority.id  author.id  assigned_to.id  parent.id  category.id
    0    18543          18          5            2         85            85.0    18203.0          NaN
    1    18542          18          5            2         85            85.0    18538.0          NaN
    2    18541          71          5            2         67            67.0    17788.0          NaN
    3    18540          18          5            3        105            85.0        NaN        150.0
    4    18539          17          5            2         81            81.0    18537.0          NaN
    ..     ...         ...        ...          ...        ...             ...        ...          ...
    806  18257           4          1            2          3             NaN    16423.0          NaN
    807  17738          11          1            2          3             NaN    17737.0          NaN
    808  16017          65          2            2         81             NaN        NaN          NaN
    809   2473          65         15            2          4             4.0        NaN          NaN
    810  16423          65         18            2          3            18.0        NaN          NaN

    [811 rows x 8 columns]

Думайте об этом как об иерархической древовидной структуре. Как вы можете видеть, было бы очень легко работать снизу вверх через поле parent.id, которое совпадает с полем id его родителя, но обходить объект сверху вниз не так просто.

Я пришел к следующему решению: 

def findChildren(issueId, issueFrame):
    # clean data
    safeElements = issueFrame.fillna(0)
    children = safeElements[safeElements['parent.id'] == issueId]
    childList = np.array(children['id'])
    listLength = 0
    # seek until list of children does not grow anymore
    while listLength != len(childList):
        listLength = len(childList)
        for identifier in childList:
            children = safeElements[safeElements['parent.id'] == identifier]
            addToList = np.array(children['id'])
            childList = np.append(childList, addToList)
        childList = np.unique(childList)
    return childList

Это работает! Но так как мне не нужно просто искать одну проблему, буквально за несколько минут я создаю для себя все те списки детей, которые мне нужны. Какой будет более быстрый подход? Результат не обязательно должен быть в списке детей. Я также был бы счастлив с отфильтрованным DataFrame, в котором строки его потомков хранятся до последнего из их пра-пра-пра-внуков.

1 Ответ

1 голос
/ 24 февраля 2020

Самое большое узкое место в производительности вашего кода - это сопоставление массивов. Поиск в массиве - это операция O(n). Повторите это для каждого элемента в другом массиве делает операцию O(n*m). Для более быстрого результата ищите словарь, время поиска которого всегда равно O(1).

И есть способ сделать это без рекурсии. Попробуйте это: 

def findChildren(issueId, issueFrame, cache=None):
    # Create a dictionary which lists all children an `id` has
    # The result is something like this:
    # {
    #   1: [2,3,4], # 1 has children 2, 3, 4
    #   2: [5]      # 2 has child 5
    # }
    _cache = cache or issueFrame[['parent.id', 'id']].groupby('parent.id')['id'].apply(list).to_dict()

    # We start with the supplied `issueId`
    check_list = [issueId]

    # The final list of children
    ids = []

    while len(check_list) > 0:
        parent_id = check_list.pop()

        # Get all children of the current `parent_id`...
        children = _cache.get(parent_id, [])

        # ... then check if they have an children too
        check_list += children

        # and add them to the list of children for the current ticket
        ids += children

    # Finally, extract those children from the DataFrame
    return issueFrame[issueFrame['id'].isin(ids)]
...