Вложенная (двойная) строка за строкой итерации Pandas DataFrame

Привет, Я пытаюсь найти векторизованное (или более эффективное) решение проблемы итерации, где единственное найденное мной решение требует строковой итерации DataFrame с несколькими циклами. Фактический файл данных огромен, поэтому мое текущее решение практически невозможно. Я включил вывод профилировщика линии в самом конце, если вы хотите посмотреть. Реальная проблема довольно сложная, поэтому я попытаюсь объяснить это простым примером (мне понадобилось довольно много времени, чтобы упростить ее :)):

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

PLANE   STRIP   ARRIVAL   DEPARTURE
0       1       85.00     86.00
1       1       87.87     92.76
2       2       88.34     89.72
3       1       88.92     90.88
4       2       90.03     92.77
5       2       90.27     91.95
6       2       92.42     93.58
7       2       94.42     95.58

Ищете решения для двух случаев:

1. Создайте список событий, в которых на одной полосе имеется более одной плоскости. Не включайте подмножества событий (например, не показывайте [3,4], если существует действительный случай [3,4,5]). В списке должны храниться индексы фактических строк DataFrame. См. Функцию findSingleEvents() для решения для этого случая (пробегает около 5 мс).

2. Составьте список событий, где по крайней мере одна плоскость на каждой полосе за раз. Не учитывайте подмножества события, регистрируйте событие только с максимальным количеством самолетов. (например, не показывать [3,4], если есть случай [3,4,5]). Не учитывайте события, которые полностью происходят на одной полосе. В списке должны храниться индексы фактических строк DataFrame. См. Функцию findMultiEvents() для решения для этого случая (пробегает около 15 мс).

Рабочий код:

import numpy as np
import pandas as pd
import itertools
from __future__ import division

data =  [{'PLANE':0, 'STRIP':1, 'ARRIVAL':85.00, 'DEPARTURE':86.00},
         {'PLANE':1, 'STRIP':1, 'ARRIVAL':87.87, 'DEPARTURE':92.76},
         {'PLANE':2, 'STRIP':2, 'ARRIVAL':88.34, 'DEPARTURE':89.72},
         {'PLANE':3, 'STRIP':1, 'ARRIVAL':88.92, 'DEPARTURE':90.88},
         {'PLANE':4, 'STRIP':2, 'ARRIVAL':90.03, 'DEPARTURE':92.77},
         {'PLANE':5, 'STRIP':2, 'ARRIVAL':90.27, 'DEPARTURE':91.95},
         {'PLANE':6, 'STRIP':2, 'ARRIVAL':92.42, 'DEPARTURE':93.58},
         {'PLANE':7, 'STRIP':2, 'ARRIVAL':94.42, 'DEPARTURE':95.58}]

df = pd.DataFrame(data, columns = ['PLANE','STRIP','ARRIVAL','DEPARTURE'])

def findSingleEvents(df):
    events = []
    for row in df.itertuples():
        #Create temporary dataframe for each main iteration
        dfTemp = df[(row.DEPARTURE>df.ARRIVAL) & (row.ARRIVAL<df.DEPARTURE)]
        if len(dfTemp)>1:
            #convert index values to integers from long
            current_event = [int(v) for v in dfTemp.index.tolist()]
            #loop backwards to remove elements that do not comply
            for i in reversed(current_event):
                if (dfTemp.loc[i].ARRIVAL > dfTemp.DEPARTURE).any():
                    current_event.remove(i)
            events.append(current_event)
    #remove duplicate events
    events = map(list, set(map(tuple, events)))
    return events

def findMultiEvents(df):
    events = []
    for row in df.itertuples():
        #Create temporary dataframe for each main iteration
        dfTemp = df[(row.DEPARTURE>df.ARRIVAL) & (row.ARRIVAL<df.DEPARTURE)]
        if len(dfTemp)>1:
            #convert index values to integers from long
            current_event = [int(v) for v in dfTemp.index.tolist()]
            #loop backwards to remove elements that do not comply
            for i in reversed(current_event):
                if (dfTemp.loc[i].ARRIVAL > dfTemp.DEPARTURE).any():
                    current_event.remove(i)
            #remove elements only on 1 strip
            if len(df.iloc[current_event].STRIP.unique()) > 1:
                events.append(current_event)
    #remove duplicate events
    events = map(list, set(map(tuple, events)))
    return events

print findSingleEvents(df[df.STRIP==1])
print findSingleEvents(df[df.STRIP==2])
print findMultiEvents(df)

Проверенный выход:

[[1, 3]]
[[4, 5], [4, 6]]
[[1, 3, 4, 5], [1, 4, 6], [1, 2, 3]]

Очевидно, что это неэффективные и элегантные решения. С огромным DataFrame, который у меня есть, запуск этого, вероятно, займет несколько часов. Я долго думал о векторизованном подходе, но не мог придумать ничего твердого. Любые указатели/помощь будут приветствоваться! Я также открыт для одобрения Numpy/Cython/Numba.

Спасибо!

PS: Если вы задаетесь вопросом, что я буду делать со списками: я назначу EVENT номер каждому EVENT и создаю отдельную базу данных с объединением данных выше, а номера EVENT в виде отдельного столбца будут использоваться для чего-то другого. Для случая 1 он будет выглядеть примерно так:

EVENT    PLANE   STRIP   ARRIVAL   DEPARTURE
0        4       2       90.03     92.77
0        5       2       90.27     91.95
1        5       2       90.27     91.95
1        6       2       92.42     95.58

EDIT: пересмотрен код и набор тестовых данных.

EDIT2: используйте приведенный ниже код для создания DataFrame длиной 1000 строк (или более) для тестирования. (за рекомендацию @ImportanceOfBeingErnest)

import random
import pandas as pd
import numpy as np

data =  []
for i in range(1000):
    arrival = random.uniform(0,1000)
    departure = arrival + random.uniform(2.0, 10.0)
    data.append({'PLANE':i, 'STRIP':random.randint(1, 2),'ARRIVAL':arrival,'DEPARTURE':departure})

df = pd.DataFrame(data, columns = ['PLANE','STRIP','ARRIVAL','DEPARTURE'])
df = df.sort_values(by=['ARRIVAL'])
df = df.reset_index(drop=True)
df.PLANE  = df.index

EDIT3:

Измененная версия принятого ответа. Принятый ответ не смог удалить подмножества событий. Модифицированная версия удовлетворяет правилу "(например, не показывать [3,4], если существует действительный случай [3,4,5])"

def maximal_subsets_modified(sets):
    sets.sort()
    maximal_sets = []
    s0 = frozenset()
    for s in sets:
        if not (s > s0) and len(s0) > 1:
            not_in_list = True
            for x in maximal_sets:
                if set(x).issubset(set(s0)):
                    maximal_sets.remove(x)
                if set(s0).issubset(set(x)):
                    not_in_list = False
            if not_in_list:
                maximal_sets.append(list(s0))
        s0 = s
    if len(s0) > 1:
        not_in_list = True
        for x in maximal_sets:
            if set(x).issubset(set(s0)):
                maximal_sets.remove(x)
            if set(s0).issubset(set(x)):
                not_in_list = False
        if not_in_list:
            maximal_sets.append(list(s0))
    return maximal_sets

def maximal_subsets_2_modified(sets, d):
    sets.sort()
    maximal_sets = []
    s0 = frozenset()
    for s in sets:
        if not (s > s0) and len(s0) > 1 and d.loc[list(s0), 'STRIP'].nunique() == 2:
            not_in_list = True
            for x in maximal_sets:
                if set(x).issubset(set(s0)):
                    maximal_sets.remove(x)
                if set(s0).issubset(set(x)):
                    not_in_list = False
            if not_in_list:
                maximal_sets.append(list(s0))
        s0 = s
    if len(s0) > 1 and d.loc[list(s), 'STRIP'].nunique() == 2:
        not_in_list = True
        for x in maximal_sets:
            if set(x).issubset(set(s0)):
                maximal_sets.remove(x)
            if set(s0).issubset(set(x)):
                not_in_list = False
        if not_in_list:
            maximal_sets.append(list(s0))
    return maximal_sets

# single

def hal_3_modified(d):
    sets = np.apply_along_axis(
        lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]), 
        1, d.values
    )
    return maximal_subsets_modified(sets)

# multi

def hal_5_modified(d):
    sets = np.apply_along_axis(
        lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]), 
        1, d.values
    )
    return maximal_subsets_2_modified(sets, d)

Ответ 1

Я переписал решение, используя DataFrame.apply вместо DataFrame.apply, и в качестве оптимизации использовались массивы numpy, где это возможно. Я использовал frozenset потому что они неизменяемы и хешируются, и поэтому Series.unique работает правильно. Series.unique не работает на элементах set типов.

Кроме того, я нашел d.loc[list(x), 'STRIP'].nunique() будет немного быстрее, чем d.loc[list(x)].STRIP.nunique(). Я не уверен, почему, но я использовал более быстрое утверждение в приведенном ниже решении.

Алгоритм простого английского языка:

Для каждой строки создайте набор индексов ниже (или равно) индекса текущего индекса, чье Отклонение больше текущего Прибытия. В результате получается список наборов.

Возвращайте уникальные наборы, которые не являются подмножествами других множеств (и для второго алгоритма дополнительно фильтруют, что оба STRIP называются наборами)

(Обновление) 2-е улучшение:

1 небольшое улучшение выполняется путем опускания до уровня numpy и использования np.apply_along_axis вместо использования df.apply. Это возможно, поскольку PLANE всегда равна индексу df.values и мы можем получить доступ к базовой матрице с df.values

Я нашел значительное улучшение в понимании списка, которое возвращает максимальные подмножества

[list(x) for x in sets if ~np.any(sets > x)]

Вышеприведенная операция О (п ^ 2). На небольших наборах данных это очень быстро. Однако на больших наборах данных это утверждение становится шеей бутылки. Чтобы оптимизировать это, сначала отсортируйте sets и снова проведите по элементу, чтобы найти максимальные подмножества. После сортировки достаточно проверить, что elem [n] не является подмножеством elem [n + 1], чтобы определить, является ли elem [n] максимальным подмножеством. Процедура сортировки сравнивает два элемента с < операцией

Тайминги:

Хотя моя первоначальная реализация значительно улучшила производительность по сравнению с попыткой OP, алгоритм был экспоненциально упорядочен, как показано на следующей диаграмме.

Я представляю только тайминги для findMultiEvents, hal_2 & hal_5. Относительная производительность findSinglEvents, hal_1 & hal_3 аналогично сопоставима.

прокрутите ниже, чтобы увидеть код бенчмаркинга.

обратите внимание, что я прекратил бенчмаркинг findMumtiEvents & hal_2 раньше, когда стало очевидно, что они менее эффективны по экспоненциальному коэффициенту

Реализация

Улучшенная реализация:

def maximal_subsets(sets):
    sets.sort()
    maximal_sets = []
    s0 = frozenset()
    for s in sets[::-1]:
        if s0 > s or len(s) < 2:
            continue
        maximal_sets.append(list(s))
        s0 = s
    return maximal_sets

def maximal_subsets_2(sets, d):
    sets.sort()
    maximal_sets = []
    s0 = frozenset()
    for s in sets[::-1]:
        if s0 > s or len(s) < 2 or d.loc[list(s), 'STRIP'].nunique() < 2:
            continue
        maximal_sets.append(list(s))
        s0 = s
    return maximal_sets

# single
def hal_3(d):
    sets = np.apply_along_axis(
        lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]), 
        1, d.values
    )
    return maximal_subsets(sets)
# multi
def hal_5(d):
    sets = np.apply_along_axis(
        lambda x: frozenset(d.PLANE.values[(d.PLANE.values <= x[0]) & (d.DEPARTURE.values > x[2])]), 
        1, d.values
    )
    return maximal_subsets_2(sets, d)

Исходная реализация:

# findSingleEvents
def hal_1(d):
    sets = d.apply(
       lambda x: frozenset(
           d.index.values[(d.index.values <= x.name) & (d.DEPARTURE.values > x.ARRIVAL)]
       ),
       axis=1
    ).unique()
    return [list(x) for x in sets if ~np.any(sets > x) and len(x) > 1]

# findMultiEvents
def hal_2(d):
    sets = d.apply(
        lambda x: frozenset(
            d.index.values[(d.index.values <= x.name) & (d.DEPARTURE.values > x.ARRIVAL)]
        ),
        axis=1
    ).unique()
    return [list(x) for x in sets 
            if ~np.any(sets > x) and
               len(x) > 1 and 
               d.loc[list(x), 'STRIP'].nunique() == 2]

Выходы:

Выходы идентичны реализации OP.

hal_1(df[df.STRIP==1])
[[1, 3]]
hal_1(df[df.STRIP==2])
[[4, 5], [4, 6]]
hal_2(df)
[[1, 2, 3], [1, 3, 4, 5], [1, 4, 6]]
hal_3(df[df.STRIP==1])
[[1, 3]]
hal_3(df[df.STRIP==2])
[[4, 5], [4, 6]]
hal_5(df)
[[1, 2, 3], [1, 3, 4, 5], [1, 4, 6]]

Детали тестовой системы:

os: windows 10
python: 3.6 (Anaconda)
pandas: 0.22.0
numpy: 1.14.3

Код бенчмаркинга:

import random

def mk_random_df(n):
    data =  []
    for i in range(n):
        arrival = random.uniform(0,1000)
        departure = arrival + random.uniform(2.0, 10.0)
        data.append({'PLANE':i, 'STRIP':random.randint(1, 2),'ARRIVAL':arrival,'DEPARTURE':departure})

    df = pd.DataFrame(data, columns = ['PLANE','STRIP','ARRIVAL','DEPARTURE'])
    df = df.sort_values(by=['ARRIVAL'])
    df = df.reset_index(drop=True)
    df.PLANE = df.index
    return df

dfs = {i: mk_random_df(100*(2**i)) for i in range(0, 10)}
times, times_2, times_5 = [], [], []

for i, v in dfs.items():
    if i < 5:
        t = %timeit -o -n 3 -r 3 findMultiEvents(v)
        times.append({'size(pow. of 2)': i, 'timings': t})

for i, v in dfs.items():
    t = %timeit -o -n 3 -r 3 hal_5(v)
    times_5.append({'size(pow. of 2)': i, 'timings': t})

for i, v in dfs.items():
    if i < 9:
        t = %timeit -o -n 3 -r 3 hal_2(v)
        times_2.append({'size(pow. of 2)': i, 'timings': t})