高效检测重叠网络

Question

我知道如何检测重叠的网络。有两种方法可以做到这一点:使用netaddr的"IPNetwork in IPNetwork“或ipaddress的"overlaps”方法。问题是如何以最有效的方式找到阵列中的重叠网络。

目前，我使用以下代码：

networks = {
    IPNetwork('10.1.0.0/24'): 'net2',
    IPNetwork('10.0.0.0/8'): 'net1',
    IPNetwork('10.0.0.0/16'): 'net3',
    IPNetwork('10.0.0.0/24'): 'net4',
    IPNetwork('192.168.0.0/16'): 'net5',
    IPNetwork('192.168.0.0/23'): 'net6',
    IPNetwork('192.168.1.0/24'): 'net7',
    IPNetwork('172.16.0.0/12'): 'net8'
}

net = sorted([key for key in networks.keys()])
for pi in range(0, len(net)-1):
    for si in range(pi+1, len(net)):
        if net[si] in net[pi]:
            print(f'{net[si]} ({networks[net[si]]}) overlaps with '
                  f'{net[pi]} ({networks[net[pi]]})')

它做了这项工作，但使用了许多迭代(例如，对于8个条目，有7+6+5+= 28个比较)，我正在寻找一种更有效的方法。

Answer 1

这将处理您的所有情况，但它可能不会找到每个重复项，例如，给定(a, a', a'', a''', b)，它不会显示该(a''' overlaps a')。如果你真的对主要的超集感兴趣，那么这段代码可以简化

from netaddr.ip import IPNetwork
from collections import namedtuple

Network = namedtuple("Network", "name ip")

networks = {
    IPNetwork('10.1.0.0/24'): 'net2',
    IPNetwork('10.0.0.0/8'): 'net1',
    IPNetwork('10.0.0.0/16'): 'net3',
    IPNetwork('10.0.0.0/24'): 'net4',
    IPNetwork('192.168.0.0/16'): 'net5',
    IPNetwork('192.168.0.0/23'): 'net6',
    IPNetwork('192.168.1.0/24'): 'net7',
    IPNetwork('172.16.0.0/12'): 'net8'
}

print("original")
net = sorted([key for key in networks.keys()])
for pi in range(0, len(net)-1):
    for si in range(pi+1, len(net)):
        if net[si] in net[pi]:
            print(f'{net[si]} ({networks[net[si]]}) overlaps with '
                  f'{net[pi]} ({networks[net[pi]]})')

nets = sorted([Network(v, k) for k, v in networks.items()], key=lambda a: a.ip)

print()
print("faster")
aa = None
first = True
for a, b in zip(nets[0:-1], nets[1:]):
  if aa is None:
    aa = a
  if b.ip in aa.ip:
    print(f'{b.ip} ({b.name}) overlaps with {aa.ip} ({aa.name})')
    if not first and aa != a and b.ip in a.ip: 
      # it's already a subset of an earlier one...
      # only if you care about secondary overlaps
      print(f'{b.ip} ({b.name}) overlaps with {a.ip} ({a.name})')
    # aa = a
  elif b.ip in a.ip:
    print(f'{b.ip} ({b.name}) overlaps with {a.ip} ({a.name})')
    aa = a
  else:
    # print(f'! {b.ip} ({b.name}) overlaps with {aa.ip} ({aa.name})')
    aa = None
  first = False