固定重叠范围下千万级元组列表分类的性能优化问询

我们有一组可重叠的数值范围（规则：tuple[0] <= n < tuple[1]），示例如下：

ranges = [(70, 80), (80, 120), (120, 130), (120, 2000), (1990, 2000), (2000, 2040), (2040, 2050)]

输入是元组列表，每个元组的第二个元素决定其所属的一个或多个范围，示例：

tuples = [('a', 71), ('b', 79), ('c', 82), ('d', 121), ('e', 1991), ('f', 2010), ('g', 2045), ('h', 3000)]

需要将元组按所属范围归类，结果格式要求如下（ranges[i]对应members[i]）：

members = [{71: 'a', 79: 'b'}, {82: 'c'}, {121: 'd'}, {121: 'd', 1991: 'e'}, {1991: 'e'}, {2010: 'f'}, {2045: 'g'}]

当前通过构建number_to_members字典映射数值到所属范围的members字典，代码如下：

members = [{} for _ in ranges]
number_to_members = defaultdict(list)

for i,(x0,x1) in enumerate(ranges):
    for x in range(x0,x1):
        number_to_members[x].append(members[i])

for c,n in tuples:
    if n in number_to_members:
        for m in number_to_members[n]:
            m[n] = c

实际场景中，需要使用同一组范围对数千万个不同的元组列表进行分类，当前实现每次处理都要生成number_to_members，开销极大，需要优化。

更新后的实际运行示例：

from collections import defaultdict
  
ranges = [(70, 80), (80, 120), (120, 130), (120, 2000), (1990, 2000), (2000, 2040), (2040, 2050)]

inputs = [
    [('a', 71), ('b', 79), ('c', 82), ('d', 121), ('e', 1991), ('f', 2010), ('g', 2045), ('h', 3000)],
    [('x', 75), ('y', 78), ('z', 1995)]
]

members = [{} for _ in ranges]
number_to_members = defaultdict(list)

for i,(x0,x1) in enumerate(ranges):
    for x in range(x0,x1):
        number_to_members[x].append(members[i])

for tuples in inputs:
    for c,n in tuples:
        if n in number_to_members:
            for m in number_to_members[n]:
                m[n] = c
    print(members)

输出结果：

[{71: 'a', 79: 'b'}, {82: 'c'}, {121: 'd'}, {121: 'd', 1991: 'e'}, {1991: 'e'}, {2010: 'f'}, {2045: 'g'}]
[{71: 'a', 79: 'b', 75: 'x', 78: 'y'}, {82: 'c'}, {121: 'd'}, {121: 'd', 1991: 'e', 1995: 'z'}, {1991: 'e', 1995: 'z'}, {2010: 'f'}, {2045: 'g'}]

核心思路是预编译范围匹配规则，避免为每个数值创建映射，而是对每个输入的数值n直接判断它属于哪些范围索引，再更新对应members字典。

方案1：预存范围列表，对每个n遍历匹配（适合范围数量少的场景） #

提前把范围列表存好，处理每个输入的n时，直接遍历所有范围判断是否满足x0 <= n < x1，如果满足就更新对应members[i]：

from collections import defaultdict

ranges = [(70, 80), (80, 120), (120, 130), (120, 2000), (1990, 2000), (2000, 2040), (2040, 2050)]
inputs = [
    [('a', 71), ('b', 79), ('c', 82), ('d', 121), ('e', 1991), ('f', 2010), ('g', 2045), ('h', 3000)],
    [('x', 75), ('y', 78), ('z', 1995)]
]

# 预存范围的索引和区间
range_list = list(enumerate(ranges))

for tuples in inputs:
    members = [{} for _ in ranges]
    for c, n in tuples:
        for idx, (x0, x1) in range_list:
            if x0 <= n < x1:
                members[idx][n] = c
    print(members)

如果范围数量不多（比如示例中的7个），这种方法的开销远小于预生成超大字典，尤其适合千万级输入的场景。

方案2：区间索引优化（适合范围数量多、数值跨度大的场景） #

如果范围数量多，可以先提取所有区间端点，排序后构建分段索引，快速定位可能包含n的范围，减少遍历次数：

from collections import defaultdict

ranges = [(70, 80), (80, 120), (120, 130), (120, 2000), (1990, 2000), (2000, 2040), (2040, 2050)]
inputs = [
    [('a', 71), ('b', 79), ('c', 82), ('d', 121), ('e', 1991), ('f', 2010), ('g', 2045), ('h', 3000)],
    [('x', 75), ('y', 78), ('z', 1995)]
]

# 提取所有端点并排序
endpoints = sorted({x for r in ranges for x in r})
# 构建端点到范围索引的映射：每个区间[ep, next_ep)对应的所有范围索引
ep_to_ranges = {}
for i in range(len(endpoints)-1):
    current_ep = endpoints[i]
    next_ep = endpoints[i+1]
    # 收集所有包含[current_ep, next_ep)的范围索引
    ep_to_ranges[(current_ep, next_ep)] = [idx for idx, (x0, x1) in enumerate(ranges) if x0 <= current_ep and x1 >= next_ep]

for tuples in inputs:
    members = [{} for _ in ranges]
    for c, n in tuples:
        # 找到n所在的端点区间
        for (ep_start, ep_end), range_indices in ep_to_ranges.items():
            if ep_start <= n < ep_end:
                # 遍历该区间对应的所有范围索引
                for idx in range_indices:
                    members[idx][n] = c
                break
        # 处理超出所有范围的n（比如3000），直接跳过
    print(members)

这种方法通过减少每次匹配的范围数量，进一步提升大数量范围场景下的效率。

方案3：使用bisect模块快速定位（更高效的区间查找） #

利用bisect模块快速找到n在端点列表中的位置，从而定位可能的范围：

import bisect
from collections import defaultdict

ranges = [(70, 80), (80, 120), (120, 130), (120, 2000), (1990, 2000), (2000, 2040), (2040, 2050)]
inputs = [
    [('a', 71), ('b', 79), ('c', 82), ('d', 121), ('e', 1991), ('f', 2010), ('g', 2045), ('h', 3000)],
    [('x', 75), ('y', 78), ('z', 1995)]
]

# 预存范围列表和排序后的端点
range_list = list(enumerate(ranges))
endpoints = sorted({x for r in ranges for x in r})

for tuples in inputs:
    members = [{} for _ in ranges]
    for c, n in tuples:
        # 找到第一个大于n的端点索引
        pos = bisect.bisect_right(endpoints, n)
        if pos == 0 or pos > len(endpoints):
            continue
        # 检查所有包含该区间的范围
        for idx, (x0, x1) in range_list:
            if x0 <= n < x1:
                members[idx][n] = c
    print(members)

bisect的二分查找能快速缩小范围，结合遍历匹配，在范围数量适中时效率最优。

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