如何有效地检查给定的IP地址是否属于Python中的IP子网

Question

我有大约200,000个IP地址和10,000个子网(1.1.1.1/24(。对于每个IP地址，我需要检查它是否属于这些子网之一，但是由于它是一个很大的数据集，而且我的计算能力较小，我希望为此有效实现。

在搜索时，我发现的一种方法是(https://stackoverflow.com/a/820124/7995937(：

from netaddr import IPNetwork, IPAddress
if IPAddress("192.168.0.1") in IPNetwork("192.168.0.0/24"):
     print "Yay!"

但是，由于我必须循环超过200,000个IP地址，对于每个地址循环，超过10,000个子网，我不确定这是否有效。我的第一个怀疑是，在ipnetwork((中检查" ipaddress(("只是线性扫描，还是以某种方式进行了优化？

我想到的另一个解决方案是在IP子网中包含的所有IP(约13,000,000 IP，无重复(，然后对其进行排序。如果我这样做，那么在200,000个IP地址的循环中，我只需要在较大的IP地址上对每个IP进行二进制搜索。

for ipMasked in ipsubnets:  # Here ipsubnets is the list of all subnets
        setUnmaskedIPs = [str(ip) for ip in IPNetwork(ipMasked)]
        ip_list = ip_list + setUnmaskedIPs
ip_list = list(set(ip_list))  # To eliminate duplicates
ip_list.sort()

我可以以以下方式执行二进制搜索：

for ip in myIPList:  # myIPList is the list of 200,000 IPs
    if bin_search(ip,ip_list):
        print('The ip is present')

这种方法比另一种方法更有效？还是还有其他更有效的方法来执行此任务？

Answer 1

好吧，所以排序为O(nlogn(，如果13,000,000，您最终会做O(1300000000log(13000000((。然后，您将迭代200000 IP并在13000000的该排序列表上进行二进制搜索O(logn(。我真诚地怀疑最好的解决方案。我建议您使用地图

from netaddr import IPNetwork, IPAddress
l_ip_address = map(IPAddress, list_of_ip_address)
l_ip_subnet = map(IPNetwork, list_of_subnets)
if any(x in y for x in l_ip_address for y in l_ip_subnet):
    print "FOUND"

Answer 2

这可能不是最佳可能的解决方案，但我建议使用集合而不是列表。设置已优化用于检查集合中是否存在任何给定值，因此您正在用一个操作替换二进制搜索。而不是：

ip_list = list(set(ip_list))

只是做：

ip_set = set(ip_list)

然后您的代码的另一部分变为：

for ip in myIPList:  # myIPList is the list of 200,000 IPs
    if ip in ip_set:
        print('The ip is present')

编辑：，并且为了使事情更有效，您也可以跳过创建一个中间列表：

ip_set = set()
for ipMasked in ipsubnets: 
    ip_set.update([str(ip) for ip in IPNetwork(ipMasked)])

Answer 3

您的IP地址在子网中，如果该地址的n个领先位与N位子网之一的n个领先位相匹配。因此，首先列出一个空集的列表。将每个子网编码为一个32位整数，并用屏蔽的后方掩盖。例如，1.2.3.4/23等于(0x01020304＆amp; 0xfffffe00(等于0x01020200。将此号码添加到列表中的23套件，即subnets[23]。继续使用所有子网。

要查看IP地址是否在您的子网中，请以与32位编号ipaddr相同的方式对IP地址进行编码，然后(类似于未经测试的代码(

for N in range( 32, 0, -1)
    mask = ( 0xffffffff >> (32-N) ) << (32-N)
    if (ipaddr & mask) in subnets[N] :
        # have found ipaddr in one of our subnets
        break # or do whatever...
else
    # have not found  ipaddr

在最糟糕的O(log n(中查找一个数字，其中n中的n中的n中的n中的n。对于不在子网集中的IP地址的最坏情况下，此代码最多可以执行32次。如果预计大多数地址将存在，则将有一种优化的优化来测试最先进的设置。那可能是

for N in ( 24, 16, 8, 29, 23, 28, 27, 26, 25, 22, 15, 21 ... )

，也可以在运行时计算最佳序列。