Python如何从子网列表中查找所有顶层最大超网的最优实现方案

需求说明 #

从给定的子网列表中，筛选出所有未被列表内其他子网包含的最大规模顶层超网，示例如下：

• 输入：subnetList = ['10.10.0.0/16', '10.10.10.10/32', '192.168.56.0/24', '10.0.0.0/8']
• 预期输出：['10.0.0.0/8', '192.168.56.0/24']

原实现存在的问题 #

当前的两层循环实现时间复杂度为O(n²)，当子网列表规模较大时执行效率较低，且存在重复判断逻辑。

优化实现方案 #

优化思路 #

1. 先将所有输入子网转换为ipaddress对象并去重
2. 按子网前缀长度从小到大排序（前缀长度越小，子网覆盖范围越大，优先处理大范围子网）
3. 遍历排序后的子网，只要当前子网未被已经筛选出的任何顶层超网包含，就将其加入结果集

该逻辑的核心是：优先加入的都是更大范围的超网，后续的小范围子网如果被已有结果覆盖就直接跳过，未被覆盖则本身就是新的顶层超网

优化代码 #

import ipaddress

def get_top_supernets(subnet_list):
    # 去重并转换为ip_network对象
    nets = {ipaddress.ip_network(s, strict=False) for s in subnet_list}
    # 按前缀长度从小到大排序，优先处理大子网
    sorted_nets = sorted(nets, key=lambda x: x.prefixlen)
    top_nets = []
    for net in sorted_nets:
        # 检查当前子网是否被已有的顶层超网包含
        is_subnet = any(net.subnet_of(top_net) for top_net in top_nets)
        if not is_subnet:
            top_nets.append(net)
    # 转换为字符串格式返回
    return [str(net) for net in top_nets]

# 测试
inputS = ['172.16.0.0/16' ,'10.10.0.0/16', '10.10.10.10/32', '172.16.1.0/24', '10.10.10.0/24', '172.16.10.10/32', '192.168.56.0/24', '10.0.0.0/8']
print(get_top_supernets(inputS))

测试输出 #

['10.0.0.0/8', '172.16.0.0/16', '192.168.56.0/24']

完全符合预期结果。

方案优势 #

• 时间复杂度更低：最差为O(n*m)，m为顶层超网的数量，通常远小于输入子网总数n，子网数量越多性能优势越明显
• 逻辑清晰易读，无冗余判断
• 加入了strict=False参数，兼容输入包含主机位非0的子网（比如10.10.10.10/32这种主机地址格式的子网）

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