python - 如何有效地检查给定的 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(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"