如何高效拆分重叠范围？面向百万级IP数据的技术问询

问题背景 #

需要一种高效的重叠范围拆分方法，现有同类方案无法满足需求。需处理百万级IP地址范围（IPv4数值可达2^{32-1，IPv6可达2}128-1），要求输出中任意两个范围无重叠，且相邻（一个起始值等于另一个结束值+1）的范围数据必不同。

核心转换规则 #

1. 不同数据的重叠范围拆分 #

当两个范围数据不同时，拆分重叠区域，保留非重叠部分：

(0, 100, 'A'), (0, 20, 'B') -> (0, 20, 'B'), (21, 100, 'A')
(0, 100, 'A'), (20, 50, 'B') -> (0, 19, 'A'), (20, 50, 'B'), (51, 100, 'A')
(0, 100, 'A'), (50, 100, 'B') -> (0, 49, 'A'), (50, 100, 'B')
(0, 100, 'A'), (200, 300, 'B') -> (0, 100, 'A'), (200, 300, 'B')
(0, 100, 'A'), (50, 300, 'B') -> (0, 49, 'A'), (50, 300, 'B')

2. 相同数据的重叠/相邻范围合并 #

当两个范围数据相同时，合并重叠或相邻的区域：

(0, 100, 'A'), (0, 20, 'A') -> (0, 100, 'A')
(0, 100, 'A'), (20, 50, 'A') -> (0, 100, 'A')
(0, 100, 'A'), (50, 100, 'A') -> (0, 100, 'A')
(0, 100, 'A'), (200, 300, 'A') -> (0, 100, 'A'), (200, 300, 'A')
(0, 100, 'A'), (101, 300, 'A') -> (0, 300, 'A')
(0, 100, 'A'), (50, 300, 'A') -> (0, 300, 'A')

测试用例 #

输入：

[(0, 16, 'red'), (0, 4, 'green'), (2, 9, 'blue'), (2, 7, 'cyan'), (4, 9, 'purple'), (6, 8, 'magenta'), (9, 14, 'yellow'), (11, 13, 'orange'), (18, 21, 'green'), (22, 25, 'green')]

预期输出：

[(0, 1, 'green'), (2, 3, 'cyan'), (4, 5, 'purple'), (6, 8, 'magenta'), (9, 10, 'yellow'), (11, 13, 'orange'), (14, 14, 'yellow'), (15, 16, 'red'), (18, 25, 'green')]

现有规则实现代码 #

以下Python函数编码了上述拆分与合并规则：

def subtract(A, B):
    (As, Ae, _), (Bs, Be, Bd) = A, B
    if As > Be or Bs > Ae:
        return [[Bs, Be, Bd]]
    result = []
    if As > Bs:
        result.append([Bs, As - 1, Bd])
    if Ae < Be:
        result.append([Ae + 1, Be, Bd])
    return result


def join(A, B):
    (As, Ae, Ad), (Bs, Be, Bd) = A, B
    if Bs > As:
        As, Ae, Bs, Be = Bs, Be, As, Ae
    if Bs <= As and Ae <= Be:
        return [[Bs, Be, Bd]]
    return [[Bs, Ae, Bd]] if As <= Be + 1 else [[Bs, Be, Bd], [As, Ae, Ad]]

性能瓶颈与优化目标 #

• 此前实现的高效函数仅能处理特定约束场景，无法覆盖通用需求；暴力实现（如brute_force_discretize）效率极低，无法处理百万级数据。
• 针对make_generic_case(4096, 65536, 16)生成的测试用例，当前最优实现solve处理耗时约2.14ms，单条数据耗时约0.52微秒。需优化至单条数据耗时0.25-0.4微秒，且输出结果与brute_force_discretize完全一致。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος