在python中，有没有更好的方法可以迭代两个列表来查找项之间的关系？

Question

我模拟ip列表和子网dict作为输入：

# ip address list
ip_list = [
'192.168.1.151', '192.168.10.191', '192.168.6.127', 
'192.168.2.227', '192.168.2.5', '192.168.3.237', 
'192.168.6.188', '192.168.7.209', '192.168.9.10',
# Edited: add some /28, /16 case
'192.168.12.39', '192.168.12.58', '10.63.11.1', '10.63.102.69',
]

# subnet dict
netsets = {
'192.168.1.0/24': 'subnet-A',     # {subnet: subnet's name} 
'192.168.10.0/24': 'subnet-B', 
'192.168.2.0/24': 'subnet-C', 
'192.168.3.0/24': 'subnet-C',
'192.168.6.0/24': 'subnet-D', 
'192.168.7.0/24': 'subnet-D', 
'192.168.9.0/24': 'subnet-E',
# Edited: add some /28, /16 case
'192.168.12.32/28': 'subnet-F',
'192.168.12.48/28': 'subnet-G',
'10.63.0.0/16': 'subnet-I',
}

然后，ip_list中的每个ip地址都需要找到子网的名称。在

我们假设每个ip地址都可以在netsets中找到对应的子网。在

输出如下：

^{pr2}$

我使用netaddr计算CIDR，以下是我的代码：

from netaddr import IPAddress, IPNetwork

def netaddr_test(ips, netsets):
    for ip in ips:
        for subnet, name in netsets.iteritems():
            if IPAddress(ip) in IPNetwork(subnet):
                print ip, '\t',  name
                break

netaddr_test(ip_list, netsets)

但是这段代码太慢了，迭代太多了。时间的复杂性是O（n**2）。在

一旦我们有数万个ip要迭代，这段代码花费的时间太多了。在

有没有更好的办法来解决这个问题？在

Answer 1

我建议避免在for循环中创建新实例。这不会降低复杂性（它会增加复杂性），但会加快netaddr_test，特别是当它被多次调用时。示例：

def _init(ips, netsets):
    """Initialize all objects"""
    new_ips = []
    new_subs = {}
    for ip in ips:
         new_ips.append(IPAddress(ip))

    for subnet, info in netsets.iteritems():

        new_subs[subnet] = {'name': info, 'subnet': IPNetwork(subnet)}

    return new_ips, new_subs

def netaddr_test(ips, netsets):
    for ip in ips:
        for stringnet, info in netsets.iteritems():
            if ip in info['subnet']:
                print ip, '\t',  info['name']
                break

ni, ns = _init(ip_list, netsets)
netaddr_test(ni, ns)

更新：用测试了上面的代码

^{pr2}$

结果：

# Original
$ time python /tmp/test.py > /dev/null

real    0m0.357s
user    0m0.345s
sys     0m0.012s

# Modified
$ time python /tmp/test2.py > /dev/null

real    0m0.126s
user    0m0.122s
sys     0m0.005s

现在，我从未使用过netaddr，所以我不确定它如何在内部处理子网。在您的例子中，您可以将子网视为一个IP范围，每个IP都是uint_32，因此您可以将所有内容转换为整数：

 # IPs now are 
 ip_list_int = [3232235927, 3232238271, ...]

 netsets_expanded = {
     '192.168.1.0/24': {'name': 'subnet-A', 'start': 3232235776, 'end': 3232236031}

netaddr可用于转换上述格式的数据。一旦到达，您的netaddr_test变成（并且仅适用于整数比较）：

def netaddr_test(ips, netsets):
    for ip in ips:
        for subnet, subinfo in netsets.iteritems():
            if ip >= subinfo['start'] and ip < subinfo['end']:
                print ip, '\t',  subinfo.name
                break