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

我有一组约200,000个IP地址和10,000个子网（1.1.1.1/24）。对于每个IP地址，我需要检查它是否属于这些子网之一，但由于它是一个如此庞大的数据集，而且我的计算能力较低，所以我希望为此进行有效的实施。如何有效地检查给定的IP地址是否属于Python中的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!"

但因为我有循环这个超过20万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')

是这种方法比其他方法更有效？或者还有没有其他更有效的方式来执行这项任务？

来源

2017-05-30 Arjun Balgovind

如前所述，最快的是使用集合。关于它的其他主题： https://stackoverflow.com/questions/5993621/fastest-way-to-search-a-list-in-python –

把一个IPv4字符串变成一个32位的int是微不足道的，所以如果我必须创建一个类似于我可能在内部使用整数和二元运算符的库，这将非常有效。像往常一样，您应该先测量一下是否确实存在性能问题。 – polku

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

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)])

来源

2017-05-30 12:46:40

好吧，所以排序需要O（nlogn），如果是13,000,000，你最终会做O（13000000log（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"

来源

2017-05-30 13:09:33

你能详细说明一下地图的功能吗？如果我们在l_ip_address中使用'x和在l_ip_subnet中使用'y循环，它是如何提高复杂度的？ –

地图从IP地址字符串列表中创建IPAddress类型的另一个列表。因此，它可以节省您每次在循环中将字符串转换为IPAddress的次数。 –

你的IP地址，如果N领先的N位子网之一的该地址匹配ñ领先的比特位。因此，首先列出空集。将每个子网编码为一个32位整数，尾随位被屏蔽掉。例如，1.2.3.4/23等于（0x01020304 & 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（logN）中，集合中元素的数量为N.对于不在子网组中的IP地址的最坏情况，此代码最多可以执行32次。如果预计大部分地址都存在，那么首先进行最优先测试的优化。这可能是

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

或者你可以计算在运行时的最佳序列。

来源

2017-05-30 13:49:05 nigel222

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

回答

相关问题