Better exclude_address function in ipaddress.py

ipaddress.py の address_exclude から始めて、既存の subnets() と summarize_address_range() の経路を読みます。提案されている整数範囲アプローチを現在の動作と比較し、示されているネットワーク結果を維持しながら、報告されているパフォーマンス問題に対処します。

Feature or enhancement

Increase the speed of exclude_address by treating IPs as integer ranges making exclude_address O(1).

Pitch

Currently exclude_address will take a subnet and split it by calling subnets()

import ipaddress
>>> ip = ipaddress.IPv4Network('10.0.0.0/8')
>>> [i for i in ip.subnets()]
[IPv4Network('10.0.0.0/9'), IPv4Network('10.128.0.0/9')]

each time it is split, it checks which one contains the subnet being excluded and splits again.
This ends up being a lot of work.

Instead I propose we can use the fact that IPs are represented as integers behind the scene

For a given subnet, it can be thought of as an integer range between its network and broadcast address

>>> ip.network_address._ip
167772160
>>> ip.broadcast_address._ip
184549375

Given these can be treated as an integer range, excluding is just removing the range integers you wish to exclude

>>> [i for i in ipaddress.summarize_address_range(
    ipaddress.IPv4Address(
        ip.network_address._ip),
        ipaddress.IPv4Address(exclude_ip.network_address._ip-1
))]
[IPv4Network('10.0.0.0/22')]

>>> [i for i in ipaddress.summarize_address_range(
    ipaddress.IPv4Address(
        exclude_ip.broadcast_address._ip)+1,
        ipaddress.IPv4Address(ip.broadcast_address._ip
))]
[IPv4Network('10.0.5.0/24'), IPv4Network('10.0.6.0/23'), IPv4Network('10.0.8.0/21'), IPv4Network('10.0.16.0/20'), IPv4Network('10.0.32.0/19'), IPv4Network('10.0.64.0/18'), IPv4Network('10.0.128.0/17'), IPv4Network('10.1.0.0/16'), IPv4Network('10.2.0.0/15'), IPv4Network('10.4.0.0/14'), IPv4Network('10.8.0.0/13'), IPv4Network('10.16.0.0/12'), IPv4Network('10.32.0.0/11'), IPv4Network('10.64.0.0/10'), IPv4Network('10.128.0.0/9')]

>>> sorted([i for i in ip.address_exclude(
    ipaddress.IPv4Network('10.0.4.0/24'
))])
[IPv4Network('10.0.0.0/22'), IPv4Network('10.0.5.0/24'), IPv4Network('10.0.6.0/23'), IPv4Network('10.0.8.0/21'), IPv4Network('10.0.16.0/20'), IPv4Network('10.0.32.0/19'), IPv4Network('10.0.64.0/18'), IPv4Network('10.0.128.0/17'), IPv4Network('10.1.0.0/16'), IPv4Network('10.2.0.0/15'), IPv4Network('10.4.0.0/14'), IPv4Network('10.8.0.0/13'), IPv4Network('10.16.0.0/12'), IPv4Network('10.32.0.0/11'), IPv4Network('10.64.0.0/10'), IPv4Network('10.128.0.0/9')]

Previous discussion

https://discuss.python.org/t/ipaddress-py-exclude-address-speed-up/19445