GL账户零和交易匹配脚本性能优化求助

你的问题本质是子集和问题的变种——寻找和为0的交易子集，暴力枚举的时间复杂度是O(2^n)，n=77时完全不可能跑完。以下是针对小数据集（几十到几百行）的高效优化方案：

一、预处理剪枝，减少计算量 #

• 先筛掉无效项：单个金额为0的直接归入匹配列表；如果所有正数总和的绝对值≠所有负数总和的绝对值，差额部分直接归入未分配列表。
• 按金额绝对值从大到小排序，优先处理大额交易，快速排除不可能的组合，减少后续遍历次数。
• 拆分正负组：把正数和负数（取绝对值）分开，问题转化为找两组中和相等的子集，避免全量遍历所有项。

二、用动态规划替代暴力枚举 #

动态规划的时间复杂度是O(n*S)（S是所有金额的最大绝对值和），对于小数据完全可行：

• 初始化集合dp记录可达的和，初始值为0，同时用字典记录每个和对应的交易索引。
• 遍历每个交易金额：
  • 正数：遍历当前dp中的所有和，计算新的和并加入集合，同时记录对应的索引。
  • 负数（取绝对值）：同理，计算新的和并加入集合。
  • 每次更新后检查是否存在和为0的情况，若存在则回溯找到对应的交易项，标记为已匹配。

三、回溯算法加剪枝（需找所有匹配组合时用） #

如果需要找出所有可能的匹配组合，用回溯+剪枝大幅减少计算：

• 排序后跳过重复金额，避免重复计算相同组合。
• 若当前累计和加上剩余所有项的最小/最大可能和仍无法凑成0，直接终止这条分支（剪枝）。
• 记录已使用的交易索引，避免重复匹配。

四、优化分阶段匹配策略 #

之前的“先精确匹配再全量”思路没问题，但要优化全量匹配环节：

• 精确匹配（正负金额完全相等的交易对）完成后，对剩余项用动态规划或剪枝回溯处理，而非暴力枚举。
• 把期初余额作为一个特殊交易项加入列表，统一参与匹配，简化逻辑。

五、代码层面的细节优化 #

• 去掉冗余的打印语句，只在关键节点（比如每处理10个项）打印状态，避免IO拖慢速度。
• 使用高效数据结构：用set存储可达和，用dict记录和对应的交易索引，方便快速查找和回溯。
• 避免递归，改用迭代实现动态规划或回溯，减少栈开销和函数调用成本。

示例动态规划代码片段 #

def match_zero_sum_transactions(transactions):
    # 预处理：拆分正负、0金额项，记录索引
    pos = []
    neg = []
    zero_matched = []
    for idx, amt in enumerate(transactions):
        if amt == 0:
            zero_matched.append(idx)
        elif amt > 0:
            pos.append((idx, amt))
        else:
            neg.append((idx, abs(amt)))
    
    # 动态规划找正负匹配子集
    dp = {0: []}
    matched_indices = set(zero_matched)
    
    # 先处理正数，构建可达和集合
    for idx, num in pos:
        new_dp = dp.copy()
        for current_sum, indices in dp.items():
            new_sum = current_sum + num
            if new_sum not in new_dp:
                new_dp[new_sum] = indices + [idx]
        dp = new_dp
    
    # 检查负数能否抵消已有的和，找到匹配项
    for idx, num in neg:
        if num in dp:
            matched_indices.update(dp[num])
            matched_indices.add(idx)
            # 移除已匹配项，重新初始化dp处理剩余数据
            pos = [p for p in pos if p[0] not in matched_indices]
            neg = [n for n in neg if n[0] not in matched_indices]
            dp = {0: []}
            for p_idx, p_num in pos:
                new_dp = dp.copy()
                for s, ids in dp.items():
                    new_s = s + p_num
                    if new_s not in new_dp:
                        new_dp[new_s] = ids + [p_idx]
                dp = new_dp
    
    # 整理最终结果
    matched = [transactions[i] for i in matched_indices]
    unmatched = [transactions[i] for i in range(len(transactions)) if i not in matched_indices]
    return matched, unmatched

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