如何用Pandas为同组DataFrame元素匹配另一DataFrame的最小差值

问题背景 #

现有两个DataFrame定义如下：

import pandas as pd

df1 = pd.DataFrame()
df1['group'] = ['a', 'a', 'b', 'b']
df1['value'] = [1, 0, 1, 4]

df2 = pd.DataFrame()
df2['group'] = ['a', 'a', 'b']
df2['value'] = [2, 4, 3]

需求：为df1中的每一行，找到同group分组下df2中value与当前行value的最小差值，最终期望得到df1['smallest_diff'] = [1, 2, 2, 1]。

此前采用全量merge的方式实现，但数据量大时效率低下，需要更高效的方案。

高效解决方案 #

核心思路是通过分组排序+二分查找避免全量笛卡尔积匹配，大幅提升效率：

实现步骤 #

1. 预处理df2：按group分组，将每个group的value排序后存入字典，方便快速索引
2. 利用二分查找定位df1中value在对应group排序数组中的插入位置，比较前后元素的差值，取最小值
3. 批量计算df1所有行的最小差值

代码实现 #

import bisect

# 预处理df2：按group分组并排序value，转成字典
group_sorted_vals = df2.groupby('group')['value'].apply(sorted).to_dict()

def calculate_min_diff(row):
    sorted_vals = group_sorted_vals[row['group']]
    # 二分查找找到插入位置
    insert_idx = bisect.bisect_left(sorted_vals, row['value'])
    # 收集候选差值（插入点前后的元素）
    diff_candidates = []
    if insert_idx > 0:
        diff_candidates.append(abs(row['value'] - sorted_vals[insert_idx - 1]))
    if insert_idx < len(sorted_vals):
        diff_candidates.append(abs(row['value'] - sorted_vals[insert_idx]))
    return min(diff_candidates)

# 生成结果列
df1['smallest_diff'] = df1.apply(calculate_min_diff, axis=1)

运行结果 #

处理后的df1如下：

效率说明 #

• 预处理阶段：对每个group的value排序，时间复杂度为O(n log n)（n为df2总行数）
• 查找阶段：每行采用二分查找，时间复杂度为O(log m)（m为对应group的df2行数）
• 整体时间复杂度远低于全量merge的O(n*m)，数据量越大，效率优势越显著

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