模拟交易对账：支持5分钟时间容差的两组交易记录一对一匹配方案

现有代码问题 #

• 语法错误：len(self.setA) != self.setB 未对setB取长度，存在未定义变量e_product、found_reconciliation/reconciliation变量拼写混乱等问题
• 逻辑缺陷：两层循环暴力匹配会出现「优先匹配非最优时间差记录」的问题，匹配顺序会直接影响最终结果，可能导致本来可以匹配的记录因顺序问题被判定为不匹配
• 性能问题：时间复杂度为O(n²)，数据集超过千级就会出现明显性能瓶颈

最优实现思路 #

整体时间复杂度为O(n log n)，逻辑如下：

• 预处理：将两组交易记录按【产品标识+交易数量】作为key分组，每组内存储转换完成的时间格式，避免重复转换
• 快速剪枝：如果任意key在两组的分组中长度不一致，直接返回False
• 双指针匹配：对每个分组的两组时间戳分别排序，用双指针逐一检查时间差是否≤5分钟，匹配成功则两个指针同时后移，否则移动时间更早的那一侧指针

实现代码 #

from datetime import datetime, timedelta
from collections import defaultdict

def check_reconciliation(setA, setB) -> bool:
    # 总长度不同直接不匹配
    if len(setA) != len(setB):
        return False
    
    # 按(产品,数量)分组，存储转换后的datetime对象
    def group_records(records):
        groups = defaultdict(list)
        for prod, qty, ts_str in records:
            ts = datetime.strptime(ts_str, '%H:%M:%S')
            groups[(prod, qty)].append(ts)
        return groups
    
    groupA = group_records(setA)
    groupB = group_records(setB)
    
    # 分组key集合不一致直接不匹配
    if groupA.keys() != groupB.keys():
        return False
    
    # 逐个分组校验匹配
    for key in groupA:
        timesA = sorted(groupA[key])
        timesB = sorted(groupB[key])
        # 同分组长度不同直接不匹配
        if len(timesA) != len(timesB):
            return False
        
        i = j = matched = 0
        n = len(timesA)
        while i < n and j < n:
            time_diff = abs(timesA[i] - timesB[j])
            if time_diff <= timedelta(minutes=5):
                matched += 1
                i += 1
                j += 1
            elif timesA[i] < timesB[j]:
                # A侧时间更早，与当前B侧时间差已超阈值，无匹配可能
                i += 1
            else:
                # B侧时间更早，与当前A侧时间差已超阈值，无匹配可能
                j += 1
        if matched != n:
            return False
    return True

# 测试示例数据集
setA = {('H', '-50', '16:19:02'), ('A', '10', '11:53:00'), 
('A', '10', '11:59:00'), ('A', '10', '12:00:00'), ('B', '12', '15:01:02')} 
setB = {('A', '10', '12:01:00'), ('H', '-50', '16:14:02'), 
('A', '10', '11:59:00'), ('A', '10', '12:00:00'), ('B', '12', '15:01:03')}
print(check_reconciliation(setA, setB)) # 输出False，符合预期

示例数据集匹配说明 #

针对示例中(A,10)的分组：

• setA时间排序后：11:53:00、11:59:00、12:00:00
• setB时间排序后：11:59:00、12:00:00、12:01:00
  setA中11:53:00的记录与B侧最早的11:59:00差值为6分钟，超过5分钟阈值，无法匹配，因此整体返回False。

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