Привет! Я пытаюсь найти векторизованное (или более эффективное) решение итерационной задачи, где единственное найденное мной решение требует построчную итерацию объекта 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
РЕДАКТИРОВАТЬ: Исправлен код и набор тестовых данных.
РЕДАКТИРОВАТЬ2: Используйте приведенный ниже код для создания 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)