如何在Pandas中保留无替代最优行程？百万级DataFrame优化求助

Awesome question—your initial solution works for small datasets, but it's totally understandable that it slows down with 1M rows. The problem with your current approach is that the apply(lambda x: sum(...)) runs in O(n²) time: every single row has to compare itself against every other row in the DataFrame. Let's fix this with a far more efficient group-based strategy that leverages sorting and cumulative operations, which scales beautifully to large datasets.

Step 1: Frame the Problem in Groups #

We only need to evaluate trips that share the same origin, destination, and date. Within each group, we want to remove any trip where there exists another trip that departs later but arrives earlier. This is equivalent to keeping only the "Pareto-efficient" trips—no other trip in the group dominates it in both departure time (later) and arrival time (earlier).

Step 2: Optimized Group-Based Filtering #

This approach runs in O(n log n) time (due to sorting) instead of O(n²), making it feasible for 1M+ rows:

1. Sort strategically: For each group, sort trips in descending order of departure_hour. This lets us process the latest departures first.
2. Track cumulative minimum arrival time: As we iterate through the sorted group, we use cummin() to keep track of the earliest arrival time we've seen so far. If a trip's arrival time matches this cumulative minimum, it means no later-departing trip arrives earlier—so we keep it. If not, there's a better (later depart, earlier arrive) trip, so we discard it.

Full Code Implementation #

import pandas as pd

# Your original DataFrame
df = pd.DataFrame({
    'origin': ['town a', 'town a', 'town a','town a', 'town c', 'town c'],
    'destination': ['town b', 'town b', 'town b','town b','town b','town b'], 
    'departure_hour': ['09:30', '09:45','10:00', '10:30','14:30', '15:30'],
    'arrival_hour': ['11:30', '10:50','12:00', '11:45','16:30', '19:30'],
    'date': ['29-09-2020']*6
})

# Optional (but safer): Convert time columns to datetime.time for consistent comparison
df['departure_hour'] = pd.to_datetime(df['departure_hour'], format='%H:%M').dt.time
df['arrival_hour'] = pd.to_datetime(df['arrival_hour'], format='%H:%M').dt.time

# Sort by group keys + descending departure time
df_sorted = df.sort_values(
    by=['origin', 'destination', 'date', 'departure_hour'],
    ascending=[True, True, True, False]
)

# Compute cumulative minimum arrival time per group
df_sorted['min_arrival_so_far'] = df_sorted.groupby(
    ['origin', 'destination', 'date']
)['arrival_hour'].cummin()

# Filter to keep only non-dominated trips
result = df_sorted[df_sorted['arrival_hour'] == df_sorted['min_arrival_so_far']]

# Optional: Restore original row order (or sort as needed)
result = result.sort_index().reset_index(drop=True)

print(result)

Output (Matches Your Expected Result) #

origin destination departure_hour arrival_hour        date
0  town a       town b        09:45:00    10:50:00  29-09-2020
1  town a       town b        10:30:00    11:45:00  29-09-2020
2  town c       town b        14:30:00    16:30:00  29-09-2020
3  town c       town b        15:30:00    19:30:00  29-09-2020

Why This Is Faster #

• No row-by-row comparisons: We use vectorized operations (sorting + cummin()) which are optimized in pandas (built on NumPy), avoiding the O(n²) overhead of your original method.
• Isolated group processing: We only evaluate trips within their relevant origin/destination/date groups, cutting down on unnecessary computations.

This method will handle 1M rows with ease—you'll see a massive speedup compared to your initial approach.

内容的提问来源于stack exchange，提问作者Mathieu P.