如何在Cross Join时应用条件筛选合规中转航班优化性能？

我有两组航班数据：到达航班表df_arrivals（测试数据10行，真实场景25万行）、出发航班表df_departures（测试数据10行，真实场景25万行），需要找出所有满足中转时长0≤时间差<4小时的可中转航班组合。

最初的方法是先做笛卡尔积（Cross Join）生成100行测试数据，再筛选得到19行结果，但面对25万行的真实数据时，笛卡尔积会产生625亿条记录，直接触发numpy.core._exceptions._ArrayMemoryError，计算和内存成本完全不可行。

请问有没有办法避免全笛卡尔积，直接在匹配过程中应用筛选条件？

测试输入数据 #

到达航班表 #

出发航班表 #

高效解决方案 #

方法1：利用Pandas的区间连接（Interval Join） #

核心思路是给每个到达航班生成一个允许中转的时间区间（到达时间 ~ 到达时间+4小时），然后将出发航班的时间与这个区间做连接，直接匹配符合条件的组合，无需生成全笛卡尔积。

import datetime
import pandas as pd

# 读取数据并解析时间列
df_arrivals = pd.read_csv(r"C:\Users\df_arrivals.csv", parse_dates=["Arriving time"])
df_departures = pd.read_csv(r"C:\Users\df_departures.csv", parse_dates=["Departing time"])

# 为到达航班生成中转允许的时间区间
df_arrivals["interval_start"] = df_arrivals["Arriving time"]
df_arrivals["interval_end"] = df_arrivals["Arriving time"] + datetime.timedelta(hours=4)
# 转换为Interval类型
df_arrivals["transfer_interval"] = pd.IntervalIndex.from_arrays(
    df_arrivals["interval_start"], df_arrivals["interval_end"], closed="left"
)

# 用区间连接匹配出发航班时间
result = pd.merge_asof(
    df_departures.sort_values("Departing time"),
    df_arrivals.sort_values("interval_start"),
    left_on="Departing time",
    right_on="interval_start",
    direction="backward",
)

# 筛选出发时间在区间内的记录
result = result[result["Departing time"].isin(result["transfer_interval"])]

# 整理输出列
result = result[["到达航班", "到达时间", "出发航班", "出发时间"]]

方法2：排序后用二分查找匹配 #

先对两张表按时间排序，然后对每个到达航班，用二分查找找到出发时间在[到达时间, 到达时间+4小时)范围内的所有出发航班，避免全量匹配。

import datetime
import pandas as pd
import numpy as np

df_arrivals = pd.read_csv(r"C:\Users\df_arrivals.csv", parse_dates=["Arriving time"])
df_departures = pd.read_csv(r"C:\Users\df_departures.csv", parse_dates=["Departing time"])

# 按时间排序
df_arrivals_sorted = df_arrivals.sort_values("Arriving time").reset_index(drop=True)
df_departures_sorted = df_departures.sort_values("Departing time").reset_index(drop=True)

# 提取出发时间的numpy数组用于二分查找
dep_times = df_departures_sorted["Departing time"].values

matches = []
for idx, row in df_arrivals_sorted.iterrows():
    arr_time = row["Arriving time"]
    # 计算时间区间的上下限
    lower = arr_time
    upper = arr_time + datetime.timedelta(hours=4)
    # 找到出发时间在区间内的索引范围
    left = np.searchsorted(dep_times, lower, side="left")
    right_idx = np.searchsorted(dep_times, upper, side="left")
    # 提取符合条件的出发航班
    matching_deps = df_departures_sorted.iloc[left:right_idx].copy()
    matching_deps["到达航班"] = row["到达航班"]
    matching_deps["到达时间"] = arr_time
    matches.append(matching_deps)

# 合并所有匹配结果
result = pd.concat(matches, ignore_index=True)
# 调整列顺序
result = result[["到达航班", "到达时间", "出发航班", "出发时间"]]

测试输出结果 #

内容的提问来源于stack exchange，提问作者Howard