如何高效实现Cross Join、值对比并筛选最匹配项？

问题概述 #

你有两个数据表：

• t1：5万行，含ID列+30+数值列
• t2：200万行，含ID列+30+数值列
  需求是为每个t1的ID找到误差最小的t2 ID（误差定义为对应数值列的绝对值之和），可选要求是每个t2 ID最多被匹配一次。

当前用交叉连接的方案完全不可行——5万×200万的笛卡尔积会生成1000亿行数据，内存和计算资源根本扛不住，必须用更高效的近邻搜索或优化分配方案。

方案1：不限制t2 ID复用（优先高效） #

利用KD-Tree/Ball-Tree做高维近邻搜索，scikit-learn的NearestNeighbors可以快速为每个t1样本找到距离最近的t2样本，时间复杂度远低于全量交叉连接。

代码实现 #

import pandas as pd
from sklearn.neighbors import NearestNeighbors

# 模拟数据（实际替换为你的真实数据）
t1 = {'id': ['a1', 'a2', 'a3'], 'val1': [0.11, 0.22, 0.33], 'val2': [0.44, 0.55, 0.66]}
t2 = {'id': ['b1', 'b2', 'b3'], 'val1': [0.99, 0.77, 0.55], 'val2': [0.22, 0.44, 0.66]}
df1 = pd.DataFrame(t1)
df2 = pd.DataFrame(t2)

# 提取数值列（假设所有非ID列都是数值列）
num_cols = [col for col in df1.columns if col != 'id']
X1 = df1[num_cols].values
X2 = df2[num_cols].values

# 初始化近邻模型，使用曼哈顿距离（和你的误差计算逻辑一致）
nn = NearestNeighbors(n_neighbors=1, metric='l1')
nn.fit(X2)

# 为每个t1样本找最近的t2样本
distances, indices = nn.kneighbors(X1)

# 整理结果
result = pd.DataFrame({
    'id_x': df1['id'],
    'id_y': df2.iloc[indices.flatten()]['id'].values,
    'err': distances.flatten()
})

print(result)

优势 #

• 时间复杂度约为O(N log M)（N是t1行数，M是t2行数），处理5万+200万的数据量只需几分钟
• 内存占用极低，无需生成笛卡尔积

方案2：限制t2 ID最多用一次（最优分配） #

如果需要每个t2 ID只能被匹配一次，这属于二分图最优分配问题，可以用匈牙利算法（scipy的linear_sum_assignment）。但直接计算全量距离矩阵仍不可行，需先为每个t1样本筛选候选t2样本，再在候选集内做分配。

代码实现 #

import pandas as pd
from sklearn.neighbors import NearestNeighbors
from scipy.optimize import linear_sum_assignment

# 模拟数据
t1 = {'id': ['a1', 'a2', 'a3'], 'val1': [0.11, 0.22, 0.33], 'val2': [0.44, 0.55, 0.66]}
t2 = {'id': ['b1', 'b2', 'b3'], 'val1': [0.99, 0.77, 0.55], 'val2': [0.22, 0.44, 0.66]}
df1 = pd.DataFrame(t1)
df2 = pd.DataFrame(t2)

num_cols = [col for col in df1.columns if col != 'id']
X1 = df1[num_cols].values
X2 = df2[num_cols].values

# 步骤1：为每个t1样本筛选top K个候选t2样本（K建议设为5~20，平衡精度和内存）
K = 5
nn = NearestNeighbors(n_neighbors=K, metric='l1')
nn.fit(X2)
distances, indices = nn.kneighbors(X1)

# 构建候选映射：t1索引 -> 候选t2索引+距离
candidates = []
for i in range(len(df1)):
    for j in range(K):
        candidates.append({
            't1_idx': i,
            't2_idx': indices[i][j],
            'err': distances[i][j]
        })
candidate_df = pd.DataFrame(candidates)

# 步骤2：构建候选距离矩阵
unique_t1 = candidate_df['t1_idx'].unique()
unique_t2 = candidate_df['t2_idx'].unique()

# 创建索引映射
t1_to_idx = {v: idx for idx, v in enumerate(unique_t1)}
t2_to_idx = {v: idx for idx, v in enumerate(unique_t2)}

# 初始化距离矩阵（未配对的设为极大值）
cost_matrix = pd.DataFrame(
    float('inf'),
    index=unique_t1,
    columns=unique_t2
)
for _, row in candidate_df.iterrows():
    cost_matrix.loc[row['t1_idx'], row['t2_idx']] = row['err']

# 步骤3：用匈牙利算法找最优分配
row_ind, col_ind = linear_sum_assignment(cost_matrix.values)

# 整理结果
result = pd.DataFrame({
    'id_x': df1.iloc[unique_t1[row_ind]]['id'].values,
    'id_y': df2.iloc[unique_t2[col_ind]]['id'].values,
    'err': cost_matrix.values[row_ind, col_ind]
})

print(result)

注意事项 #

• K值不宜过大，否则候选距离矩阵仍会占用过多内存
• 若t1行数远小于t2（如5万 vs 200万），该方案可以在可接受时间内完成分配
• 若t1和t2行数接近，直接使用linear_sum_assignment处理全量矩阵（但需确保内存足够）

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