如何基于数值与阈值高效创建集合序列？

需求明确 #

给定升序排列的短阈值序列和大量无序数值，需生成一组集合序列：

• 第一个集合：所有低于最低阈值的不同数值
• 中间集合：依次包含「不低于前一阈值但低于下一阈值」的不同数值
• 最后一个集合：所有不低于最高阈值的不同数值

现有问题：基于itertools.pairwise的实现需要遍历values共len(thresholds)+1次，当values数据量极大时，效率瓶颈明显。尝试过SciPy/NumPy未找到适配方案，使用numpy.digitize()结合数组add()的效果与partition_Kelly3b()相近，寻求更优解。

高效实现方案 #

核心思路：仅遍历一次values，通过快速区间定位将数值直接分配到对应集合，避免多次遍历的冗余开销。

方案1：bisect二分查找（纯Python，短阈值最优）

利用Python内置的bisect模块，基于升序阈值快速定位数值所属区间，单次遍历完成分配：

import bisect

def partition_values(values, thresholds):
    # 处理空阈值边界情况
    if not thresholds:
        return [set(values)]
    
    # 初始化对应数量的空集合
    result_sets = [set() for _ in range(len(thresholds) + 1)]
    
    for val in values:
        # 用bisect_left找到第一个大于val的阈值索引，即所属集合的下标
        idx = bisect.bisect_left(thresholds, val)
        result_sets[idx].add(val)
    
    return result_sets

• 时间复杂度：O(N logM)，其中N是values数量，M是阈值长度（因阈值短，logM可忽略）
• 优势：纯Python实现，无需额外依赖，代码简洁，比pairwise方案减少M次遍历，效率提升显著

方案2：NumPy向量化处理（超大量数据最优）

当values数据量极大时，利用NumPy的向量化运算加速分组：

import numpy as np

def partition_values_numpy(values, thresholds):
    if not thresholds:
        return [set(values)]
    
    # 转换为NumPy数组（若输入已是数组可跳过此步）
    val_array = np.array(values)
    # digitize返回每个值对应的区间索引（right=False对应左闭右开，与bisect逻辑一致）
    indices = np.digitize(val_array, thresholds, right=False)
    
    # 按索引分组并转换为set
    result_sets = []
    for idx in range(len(thresholds) + 1):
        group = val_array[indices == idx]
        result_sets.append(set(group))
    
    return result_sets

• 优势：向量化运算规避Python循环开销，超大量数据下效率远超纯Python方案
• 注意：若输入values本身不是NumPy数组，存在一定的类型转换开销，需根据实际场景权衡

方案对比 #

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