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

Question

我有一个由大约200,000个IP地址和10,000个形如(1.1.1.1/24)的子网组成的集合。对于每个IP地址，我需要检查它是否属于这些子网之一，但由于数据集很大且计算能力较低，因此我希望有一个高效的实现方式。

在搜索时，我找到了一种方法(链接：https://dev59.com/8HRA5IYBdhLWcg3wzhRY#820124)。

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个子网，因此我不确定这是否有效。我的第一个疑问是，“IPAddress() in IPNetwork()”只是线性扫描还是以某种方式进行了优化？

我想到的另一个解决方案是创建包含所有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')

这种方法是否比其他方法更高效？或者有没有其他更高效的方法来执行这个任务？

- Arjun Balgovind

---

如前所述，最快的方法是使用集合。关于此的其他主题： https://dev59.com/BG025IYBdhLWcg3wc1xM - Łukasz Szczesiak

将IPv4字符串转换为32位整数非常简单，因此如果我必须创建这样的库，我可能会在内部使用整数和二进制运算符，这将非常高效。像往常一样，您应该先进行测量以查看是否真的存在性能问题。 - polku

Answer 1

这可能不是最好的解决方案，但我建议使用集合而不是列表。集合在检查给定值是否存在时进行了优化，因此您可以用单个操作替换二分搜索。而不是：

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

- Błotosmętek

Answer 2

好的，所以排序需要O(nlogn)的时间复杂度，在1300万的情况下，你最终会得到O(13000000log(13000000))的时间复杂度。然后你要遍历200000个IP，并在13000000个元素的已排序列表上执行O(logn)的二分查找。

我真的怀疑这是最好的解决方案。我建议你使用map。

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"

- Ishan Bhatt

---

你能详细说明一下 map 到底是做什么的吗？如果我们要在 x in l_ip_address 和 y in l_ip_subnet 上进行循环，它是如何改进复杂性的呢？ - Arjun Balgovind

map从IP地址字符串列表创建另一个IPAddress类型的列表。因此，它可以在循环中节省将字符串转换为IPAddress的时间。 - Ishan Bhatt

Answer 3

如果一个IP地址的N个前导位与N位子网中的一个匹配，则该IP地址在子网中。因此，首先要创建一个空集列表。将每个子网编码为32位整数，并屏蔽掉尾部位。例如，1.2.3.4/23等于(0x01020304&0xfffffe00)等于0x01020200。将此数字添加到列表中的第23个集合中，即subnets[23]。继续处理所有子网。

要查看IP地址是否在您的子网中，请将IP地址编码为32位数字ipaddr，然后（类似但未经测试的代码）

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是集合中元素的数量。对于IP地址不在子网集合中的最坏情况，此代码最多执行32次。如果预计大多数地址都存在，则可以通过优化先测试具有最多元素的集合来提高效率。

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

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

- nigel222