Excel中累计求和达标后重置并按目标值分组的可扩展实现方法

你给出的场景分组规则为：按条目原有顺序累加数值，累加和首次大于等于目标值时结束当前分组，后续条目进入下一分组；若单个条目数值大于等于目标值，直接单独分为一组。目标值为10时的分组效果如下：

小数据量（单机能承载）快速实现 #

直接遍历一次数据即可完成分组，时间复杂度O(n)，空间复杂度O(1)（不计结果存储），Python实现代码如下：

def group_by_sum(target: int, items: list[tuple[str, int]]) -> list[dict]:
    groups = []
    current_group = []
    current_sum = 0
    group_id = 1
    for item_name, value in items:
        # 累加当前值会超过目标且当前组已有数据，先结算当前组
        if current_sum + value > target and current_group:
            groups.append({
                "group_id": group_id,
                "items": current_group,
                "total": current_sum
            })
            group_id += 1
            current_group = []
            current_sum = 0
        current_group.append((item_name, value))
        current_sum += value
        # 累加后达标直接结算
        if current_sum >= target:
            groups.append({
                "group_id": group_id,
                "items": current_group,
                "total": current_sum
            })
            group_id += 1
            current_group = []
            current_sum = 0
    # 剩余不足目标值的条目单独成组
    if current_group:
        groups.append({
            "group_id": group_id,
            "items": current_group,
            "total": current_sum
        })
    return groups

# 示例测试
items = [("A",4),("B",3),("C",4),("D",3),("E",2),("F",7),("G",10),("H",12)]
print(group_by_sum(10, items))

大数据量（分布式/千万级以上）可扩展方案 #

针对数据量级过大、单节点无法全量加载处理的场景，可采用无锁并行计算方案，计算能力可线性扩展：

• 第一步：将全量数据集按固定大小切分为多个独立分片，分发到不同计算节点
• 第二步：各节点并行计算分片内的局部累加值：记录分片内每一条数据对应的局部累加和、以及整个分片的总累加值
• 第三步：汇总所有分片的总累加值，按分片顺序计算每个分片的全局累加偏移量，定位每个分片内的分组切割位置以及对应的全局分组编号
• 第四步：各节点并行给分片内的条目打上分组编号，最后合并所有分片的结果即可

若业务不要求严格保留数据原顺序，可采用背包算法优化分组，让分组总和尽可能接近目标值，减少溢出的总差值，但计算复杂度会有所提升。

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