如何基于±10动态条件分组嵌套列表并优化内存

问题需求 #

给定嵌套列表nested_list，需按照元素数值的±10范围进行分组，结果中不能存在子列表（即若分组A是分组B的子集且A≠B，则需移除A）。原实现代码处理大型嵌套列表时会出现内存错误，需要更高效的解决方案。

输入数据 #

nested_list = [[[0, 59.87271881103516]],
 [[1, 56.33743667602539], [2, 12.141159057617188]],
 [[3, 116.6510009765625]],
 [[4, 98.58261108398438], [5, 98.01058959960938]],
 [[5, 98.01058959960938], [6, -2.2177391052246094]],
 [[7, -7.6250953674316415], [8, 89.80469512939453]],
 [[8, 89.80469512939453],
  [9, 14.612628936767578],
  [10, 10.861335754394531],
  [11, 33.497543334960945],
  [12, 114.00135040283205],
  [13, 29.74617004394531],
  [14, 45.50025939941406],
  [15, 12.267791748046877],
  [16, 107.34764862060548],
  [17, 25.24243927001953]],
 [[18, 1.3098258972167969],
  [19, -6.511528015136719],
  [20, -8.737972259521483]],
 [[20, -8.737972259521483],
  [21, -1.0142173767089844],
  [22, 109.0613784790039]],
 [[21, -1.0142173767089844],
  [22, 109.0613784790039],
  [23, -7.488857269287108],
  [24, -11.845829010009766],
  [25, 108.14006042480467],
  [26, -0.218780517578125],
  [27, -15.114391326904297]],
 [[23, -7.488857269287108],
  [24, -11.845829010009766],
  [25, 108.14006042480467],
  [26, -0.218780517578125],
  [27, -15.114391326904297],
  [28, -11.57907485961914],
  [29, 46.48944091796875],
  [30, -11.690120697021484]]
]

预期输出 #

expected_output = [
[[0],
 [1],
 [2],
 [3],
 [4, 5],
 [6],
 [7],
 [8],
 [9, 10, 15],
 [11, 13, 17],
 [12, 16],
 [14],
 [18, 19],
 [19, 20],
 [20, 21],
 [21, 23, 26],
 [22, 25],
 [23, 24, 26, 27, 28, 30],
[29]]
]

分组规则 #

• 分组依据：同一子列表内，元素的数值需严格落在另一元素的(数值-10, 数值+10)区间内
• 结果限制：不能存在子列表（例如允许[[5,6],[6,7]]，但不允许[[5,6],[5],[6,7]]，因为[5]是[5,6]的子集）

原代码问题 #

原实现使用numpy处理，生成大量重复分组，后续去重和子集检查步骤内存开销极大，处理大型数据时会触发内存错误。

优化解决方案 #

def optimized_grouping(nested_list: list) -> list:
    # 生成初始组，子列表内先去重
    all_groups = []
    for sublist in nested_list:
        if not sublist:
            continue
        indices = [item[0] for item in sublist]
        values = [item[1] for item in sublist]
        seen_in_sublist = set()
        n = len(sublist)
        for i in range(n):
            vi = values[i]
            lower = vi - 10
            upper = vi + 10
            current_group = []
            for j in range(i, n):
                if lower < values[j] < upper:
                    current_group.append(indices[j])
            fs = frozenset(current_group)
            if fs not in seen_in_sublist:
                seen_in_sublist.add(fs)
                all_groups.append(current_group)
    
    # 全局去重
    global_seen = set()
    unique_groups = []
    for g in all_groups:
        fs = frozenset(g)
        if fs not in global_seen:
            global_seen.add(fs)
            unique_groups.append(g)
    
    # 过滤子集：按组长度降序处理，避免子集保留
    unique_groups_sorted = sorted(unique_groups, key=lambda x: (-len(x), x[0]))
    result = []
    kept_fsets = set()
    for g in unique_groups_sorted:
        fs = frozenset(g)
        is_subset = False
        for kept_fs in kept_fsets:
            if fs.issubset(kept_fs):
                is_subset = True
                break
        if not is_subset:
            sorted_g = sorted(g)
            result.append(sorted_g)
            kept_fsets.add(fs)
    
    # 按组首元素升序排序
    result.sort(key=lambda x: x[0])
    return [result]

# 测试调用
output = optimized_grouping(nested_list)
print(output)

优化点说明 #

1. 移除numpy依赖：纯Python处理减少内存占用，避免numpy数组的额外内存开销
2. 子列表内去重：生成组时先在当前子列表内去重，减少后续处理的组数量
3. 高效全局去重：使用frozenset作为键快速去重，时间复杂度O(1)
4. 子集过滤优化：按组长度降序处理，仅与已保留的大组比较，减少无效比较，提升效率同时降低内存消耗

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