7
\$\begingroup\$

I am trying to find a vectorized (or more efficient) solution to an iteration problem, where the only solution I found requires row by row iteration of a DataFrame with multiple loops. The actual data file is huge, so my current solution is practically unfeasible. I included line profiler outputs at the very end, if you'd like to have a look.

The main issue seems to be the increased overhead due to frequent Pandas access for filtering operations, especially when creating the temporary DataFrame dfTemp. Any ideas on modifying the algorithm and minimizing Pandas usage are welcome. I am also open to Numpy/Cython/Numba implementations.

Problem Statement

An airport has two landing strips side by side. Each plane lands (arrival time), taxis on one of the landing strips for a while, then takes off (departure time). Looking for solutions to two cases:

  1. Build a list of events where there are more than one plane present on a single strip at a time. Do not include subsets of events (e.g. do not show [3,4] if there is a valid [3,4,5] case). The list should store the indices of the actual DataFrame rows. See function findSingleEvents() for a solution for this case (runs around 5 ms).

  2. Build a list of events where there is at least one plane on each strip at a time. Do not count subsets of an event, only record the event with maximum number of planes. (e.g. do not show [3,4] if there is a [3,4,5] case). Do not count events that fully occur on a single strip. The list should store the indices of the actual DataFrame rows. See function findMultiEvents() for a solution for this case (runs around 15 ms).

Code with sample input

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)

Output

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

Line Profiler Logs

%lprun -f findSingleEvents findSingleEvents(df[df.STRIP==1])

Timer unit: 2.85099e-07 s

Total time: 0.0172055 s
File: <ipython-input-33-220dd9d5b99b>
Function: findSingleEvents at line 1

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     1                                           def findSingleEvents(df):
     2         1          9.0      9.0      0.0      events = []
     3         4       8702.0   2175.5     14.4      for row in df.itertuples():
     4         3      31604.0  10534.7     52.4          dfTemp = df[(row.DEPARTURE>df.ARRIVAL) & (row.ARRIVAL<df.DEPARTURE)]
     5         3         65.0     21.7      0.1          if len(dfTemp)>1:
     6         6        334.0     55.7      0.6              current_event = [int(v) for v in dfTemp.index.tolist()]
     7         6         50.0      8.3      0.1              for i in reversed(current_event):
     8         4      19537.0   4884.2     32.4                  if (dfTemp.loc[i].ARRIVAL > dfTemp.DEPARTURE).any():
     9                                                               current_event.remove(i)
    10         2         12.0      6.0      0.0              events.append(current_event)
    11         1         33.0     33.0      0.1      events = map(list, set(map(tuple, events)))
    12         1          3.0      3.0      0.0      return events

%lprun -f findMultiEvents findMultiEvents(df)

Timer unit: 2.85099e-07 s

Total time: 0.0532152 s
File: <ipython-input-28-97265d757453>
Function: findMultiEvents at line 1

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     1                                           def findMultiEvents(df):
     2         1         18.0     18.0      0.0      events = []
     3         9      21661.0   2406.8     11.6      for row in df.itertuples():
     4         8      60694.0   7586.8     32.5          dfTemp = df[(row.DEPARTURE>df.ARRIVAL) & (row.ARRIVAL<df.DEPARTURE)]
     5         8        145.0     18.1      0.1          if len(dfTemp)>1:
     6        32       1208.0     37.8      0.6              current_event = [int(v) for v in dfTemp.index.tolist()]
     7        32        152.0      4.8      0.1              for i in reversed(current_event):
     8        26      87007.0   3346.4     46.6                  if (dfTemp.loc[i].ARRIVAL > dfTemp.DEPARTURE).any():
     9         6         67.0     11.2      0.0                      current_event.remove(i)
    10         6      15636.0   2606.0      8.4              if len(df.iloc[current_event].STRIP.unique()) > 1:
    11         6         38.0      6.3      0.0                  events.append(current_event)
    12         1         27.0     27.0      0.0      events = map(list, set(map(tuple, events)))
    13         1          2.0      2.0      0.0      return events
\$\endgroup\$
  • \$\begingroup\$ your data seems sort by ARRIVAL, if it's the case, at least you can use a break in thefor i in reversed... as once you find an ARRIVAL smaller than all DEPARTURE of dfTemp, all the one after in this loop will be smaller, so you can add else: break after the if (dfTemp.loc[i].ARRIVAL .... Should save some times \$\endgroup\$ – Ben.T Aug 8 '18 at 14:02
  • \$\begingroup\$ what do you mean by your data is huge? \$\endgroup\$ – Ben.T Aug 10 '18 at 16:00
2
\$\begingroup\$

I suggest using a simpler approach here: just keep track of which planes are where, as you go chronologically through time. This way, you only go through the data once, and you don't have to create dfTemp.

def findEvents(df):

    # An event: a list of indices of the df rows representing planes involved 
    # in the event.

    # Planes present on the strips. 
    strips = {
        1: [],
        2: []
    }

    single_events = {
        1: [],
        2: []
    }
    multi_events = []

    for row in df.sort_values(by=['ARRIVAL']).itertuples():

        # Check for departed planes first
        for planes in strips.values():
             remove_departed_planes(row.ARRIVAL, planes)

        strips[row.STRIP].append(row)

        # Single Event: 
        # Build a list of events where there are more than one plane present on 
        # a single strip at a time. Do not include subsets of events.
        for strip_name in (1, 2):
            if len(strips[strip_name]) > 1:
                indexes = frozenset(int(row.Index) for row in strips[strip_name])
                add_event(single_events[strip_name], indexes)

        # Multi Event
        # Build a list of events where there is at least one plane on each strip 
        # at a time. Do not count subsets of an event. 
        # Do not count events that fully occur on a single strip. (???) 
        if strips[1] and strips[2]:
            indexes = frozenset(int(row.Index) for row in strips[1]) | \
                      frozenset(int(row.Index) for row in strips[2])
            add_event(multi_events, indexes)

    # Sort the sets, for consistent output 
    return (
        {
            1: [sorted(event) for event in single_events[1] ],
            2: [sorted(event) for event in single_events[2] ],
        },
        [sorted(event) for event in multi_events]
    )

def remove_departed_planes(time, planes):
    i = 0
    while i < len(planes):
        if planes[i].DEPARTURE < time:
            del planes[i]
        else:
            i += 1

def add_event(events, event):
    """ Adds an event (list of indexes) to the events list.

        If the event is a subset of the previous or vice versa,
        the biggest set is kept.
    """
    if events and events[-1] < event:
        # Replace
        events[-1] = event
    elif events and events[-1] >= event:
        # Previous event already covers this event
        pass
    else:
        # Neither is a subset of each other
        events.append(event)


print "findSingleEvents and findMultiEvents"
t1 = time.time()
print findSingleEvents(df[df.STRIP==1])
print findSingleEvents(df[df.STRIP==2])
print findMultiEvents(df)
t2 = time.time()
print t2 - t1

print

print "findEvents"
t1 = time.time()
single, multiple = findEvents(df)
print single[1]
print single[2]
print multiple
t2 = time.time()
print t2 - t1

Output:

findSingleEvents and findMultiEvents
[[1, 3]]
[[4, 5], [4, 6]]
[[1, 3, 4, 5], [1, 4, 6], [1, 2, 3]]
0.0490000247955

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

In my opinion, this is also easier to read, test and debug than the more pandas-oriented approach.

You can make this even faster by accessing row.Index and row.Arrival as row[0] and row[2]: tuple-like access is faster than dictionary-like access, but less readable.

If I understand you correctly I have "Do not count events that fully occur on a single strip." covered. If not, you will have to adjust the code for this yourself. Good luck!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.